Paper 2016/882 Original: eprint.iacr.org/2016/882 ↗

MSKT-ORAM: A Constant Bandwidth ORAM without Homomorphic Encryption

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.