Paper 2017/590 Original: eprint.iacr.org/2017/590 ↗
Constant bandwidth ORAM with small block size using PIR operations
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.
- History
- 2017-06-20: last updated
- 2017-06-20: published
- Short URL
- https://ia.cr/2017/590
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2017/590}
}