Cryptology ePrint Archive: Report 2017/590

Constant bandwidth ORAM with small block size using PIR operations

Linru Zhang and Gongxian Zeng and Yuechen Chen and Siu-Ming Yiu and 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.

Category / Keywords: cryptographic protocols / ORAM, constant communication overhead, oblivious clear algorithm

Date: received 18 Jun 2017

Contact author: smyiu at cs hku hk

Available format(s): PDF | BibTeX Citation

Version: 20170620:154513 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]