**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.

**Category / Keywords: **cryptographic protocols / oblivious transfer, information hiding

**Date: **received 13 Aug 2014, last revised 19 Mar 2015

**Contact author: **alexzjs at iastate edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20150320:013712 (All versions of this report)

**Short URL: **ia.cr/2014/624

[ Cryptology ePrint archive ]