Paper 2017/590

Constant bandwidth ORAM with small block size using PIR operations

Linru Zhang, Gongxian Zeng, Yuechen Chen, Siu-Ming Yiu, Nairen Cao, and Zheli Liu

Abstract

Recently, server-with-computation model has been applied in Oblivious RAM scheme to achieve constant communication (constant number of blocks). However, existing works either result in large block size O(log^6N), or have some security flaws. Furthermore, a lower bound of sub-logarithmic bandwidth was given if we do not use expensive fully homomorphic operations. The question of \whether constant bandwidth with smaller block size without fully homomorphic operations is achievable" remains open. In this paper, we provide an affirmative answer. We propose a constant bandwidth ORAM scheme with block size O(log^3N) using only additive homomorphic operations. Our scheme is secure under the standard model. Technically, we design a non-trivial oblivious clear algorithm with very small bandwidth to improve the eviction algorithm in ORAM for which the lower bound proof does not apply. As an additional benefit, we are able to reduce the server storage due to the reduction in bucket size.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
ORAMconstant communication overheadoblivious clear algorithm
Contact author(s)
smyiu @ cs hku hk
History
2017-06-20: received
Short URL
https://ia.cr/2017/590
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/590,
      author = {Linru Zhang and Gongxian Zeng and Yuechen Chen and Siu-Ming Yiu and Nairen Cao and Zheli Liu},
      title = {Constant bandwidth ORAM with small block size using PIR operations},
      howpublished = {Cryptology ePrint Archive, Paper 2017/590},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/590}},
      url = {https://eprint.iacr.org/2017/590}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.