TSKT-ORAM: A Two-Server k -ary Tree Oblivious RAM without Homomorphic Encryption

Jinsheng Zhang, Qiumao Ma, Wensheng Zhang and Daji Qiao
Additional contact information
Jinsheng Zhang: Department of Computer Science, Iowa State University, Ames, IA 50011, USA
Qiumao Ma: Department of Computer Science, Iowa State University, Ames, IA 50011, USA
Wensheng Zhang: Department of Computer Science, Iowa State University, Ames, IA 50011, USA
Daji Qiao: Department of Electric and Computer Engineering, Iowa State University, Ames, IA 50011, USA

Future Internet, 2017, vol. 9, issue 4, 1-22

Abstract: This paper proposes TSKT-oblivious RAM (ORAM), an efficient multi-server ORAM construction, to protect a client’s access pattern to outsourced data. TSKT-ORAM organizes each of the server storages as a k -ary tree and adopts XOR-based private information retrieval (PIR) and a novel delayed eviction technique to optimize both the data query and data eviction process. TSKT-ORAM is proven to protect the data access pattern privacy with a failure probability of 2 - 80 when system parameter k ≥ 128 . Meanwhile, given a constant-size local storage, when N (i.e., the total number of outsourced data blocks) ranges from 2 16 – 2 34 , the communication cost of TSKT-ORAM is only 22–46 data blocks. Asymptotic analysis and practical comparisons are conducted to show that TSKT-ORAM incurs lower communication cost, storage cost and access delay in practical scenarios than the compared state-of-the-art ORAM schemes.

Keywords: cloud computing; storage; access pattern protection; oblivious RAM (search for similar items in EconPapers)
JEL-codes: O3 (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/1999-5903/9/4/57/pdf (application/pdf)
https://www.mdpi.com/1999-5903/9/4/57/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jftint:v:9:y:2017:i:4:p:57-:d:113446

Access Statistics for this article

Future Internet is currently edited by Ms. Grace You

More articles in Future Internet from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().