Cryptology ePrint Archive: Report 2016/882

MSKT-ORAM: A Constant Bandwidth ORAM without Homomorphic Encryption

Jinsheng Zhang and Qiumao Ma and Wensheng Zhang and Daji Qiao

Abstract: This paper proposes MSKT-ORAM, an efficient multiple server ORAM construction, to protect a client’s access pattern to outsourced data. MSKT-ORAM organizes each of the server storage as a k-ary tree and adopts XOR based PIR and a novel delayed eviction technique to optimize both the data query and data eviction process. MSKT-ORAM is proved to protect the data access pattern privacy at a failure probability of $2^{80}$ when $k\geq 128$. Meanwhile, given constant local storage, when $N$ (i.e., the total number of outsourced data blocks) ranges from $2^{16}$ to $2^{34}$ and data block size $B\geq 20$KB, the communication cost of MSKT-ORAM is only $22$ to $46$ data blocks. Asymptotical analysis and detailed implementation comparisons are conducted to show that MSKT-ORAM achieves better communication, storage and access delay in practical scenario over the compared state-of-the-art ORAM schemes.

Category / Keywords: cryptographic protocols / Oblivious RAM, data privacy

Date: received 7 Sep 2016, last revised 2 Jan 2017

Contact author: alexzjs at iastate edu

Available format(s): PDF | BibTeX Citation

Version: 20170103:060059 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]