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 preserve a client's access pattern to his/her outsourced data. The construction organizes the server storage as a $k$-ary tree with each node acting as a fully-functional PIR storage, and adopts a novel \emph{delayed eviction} technique to optimize the eviction process. KT-ORAM is proved to preserve the data access pattern privacy with a negligibly-small failure probability of $O(N^{-\log N})$. KT-ORAM requires only a constant-size local storage at the client side, and has an asymptotical communication cost of $O(\frac{\log^2 N}{\log\log N})$ (the best known asymptotical result of ORAM~\cite{Kush12}) when $k=\log N$. The communication cost of KT-ORAM is also compared with two state-of-the-art ORAM constructions, B-ORAM~\cite{Kush12} and P-PIR~\cite{MaBl14}, which share the same assumption of constant-size client-side storage as KT-ORAM, in practical scenarios. The results show that, KT-ORAM outperforms these constructions.