International Association
for Cryptologic Research

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.