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

This paper proposes KT-ORAM, a new hybrid ORAM-PIR con-struction, 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 delayed eviction technique to optimize the eviction pro-cess. KT-ORAM is proved to preserve the data access pattern pri-vacy with a negligibly-small failure probability of O(N − logN). KT-ORAM requires only a constant-size local storage at the client side, and has an asymptotical communication cost of O ( log 2 N log logN (the best known asymptotical result of ORAM [17]) when k = logN. The communication cost of KT-ORAM is also compared with two state-of-the-art ORAM constructions, B-ORAM [17] and P-PIR [20], 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