Paper 2016/882

MSKT-ORAM: A Constant Bandwidth ORAM without Homomorphic Encryption

Jinsheng Zhang, Qiumao Ma, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Oblivious RAMdata privacy
Contact author(s)
alexzjs @ iastate edu
History
2017-01-03: revised
2016-09-14: received
See all versions
Short URL
https://ia.cr/2016/882
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/882,
      author = {Jinsheng Zhang and Qiumao Ma and Wensheng Zhang and Daji Qiao},
      title = {MSKT-ORAM: A Constant Bandwidth ORAM without Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2016/882},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/882}},
      url = {https://eprint.iacr.org/2016/882}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.