MSKT ORAM: A Constant Bandwidth ORAM without Homomorphic Encryption
This paper proposes MSKT ORAM, an efficient multiple server ORAM construction, to protect a client's access pattern to outsourced data. MSKT ORAM organizes each of the server storage as a k ary tree and adopts XOR based PIR and a novel delayed eviction technique to optimize both the data query and data eviction process. MSKT ORAM is proved to protect the data access pattern privacy at a failure probability of 2 80 when k 128. Meanwhile, given constant local storage, when N (i.e. the total number of outsourced data blocks) ranges from 2 to 2 and data block size B 20 KB, the communication cost of MSKT ORAM is only 22 to 46 data blocks. Asymptotical analysis and detailed implementation comparisons are conducted to show that MSKT ORAM achieves better communication, storage and access delay in practical scenario over the compared state of the art ORAM schemes.
IACR Cryptol. ePrint Arch.