TSKT-ORAM: A two-server k-ary tree ORAM for access pattern protection in cloud storage
Jinsheng Zhang, Qiumao Ma, Wensheng Zhang, Daji Qiao · 2016
This paper proposes TSKT-ORAM, a two-server k-ary tree-based Oblivious RAM construction, to hide a client's access pattern to outsourced data. TSKT-ORAM is proved to hide the access pattern with a failure probability of 2-λ, where k = logN (N is the number of outsourced data items) and λ is a security parameter. Under the same configuration, TSKT-ORAM has an asymptotical communication cost of O( logN/log logN·B) (B is the size of a data block) if the number of recursion levels on meta data is O(1), or O( log2N/ log logN·B) if the number of recursion levels is O(logN). Asymptotical analysis and detailed implementation-based comparisons are conducted to compare the performance of TSKT-ORAM with state-of-the-art ORAM schemes.