Paper 2014/624

KT-ORAM: A Bandwidth-efficient ORAM Built on K-ary Tree of PIR Nodes

Jinsheng Zhang and Qiumao Ma and Wensheng Zhang and Daji Qiao

Abstract

This paper proposes KT-ORAM, a new hybrid ORAM-PIR construction, to protect a client's access pattern to outsourced data. KT-ORAM organizes the server storage as a $k$-ary tree with each node acting as a fully-functional PIR storage, and adopts a novel delayed eviction technique to optimize the eviction process. KT-ORAM is proved to protect the data access pattern privacy at a failure probability negligible in $N$ ($N$ is the number of exported data blocks), when system parameter $k=\log N$. Under the same configuration, KT-ORAM has an asymptotical communication cost of $O(\frac{\log N}{\log\log N}\cdot B)$ when the recursion level on meta data is of $O(1)$ depth, which can be achieved if block size $B=N^{\epsilon}$ ($0<\epsilon<1$), or $O(\frac{\log^2 N}{\log\log N}\cdot B)$ when the number of recursion levels is $O(\log N)$. The costs of KT-ORAM are compared with those of several state-of-the-art ORAMs. The results show that, KT-ORAM achieves the best communication, storage and client-side computational efficiency simultaneously, at the price of requiring $O(\frac{\log^2N}{\log\log N}\cdot B)$ computational cost at the storage server for each data query. \\ {\bf Key words:} Cloud storage, Access pattern privacy, Oblivious RAM, and PIR.