TWORAM: Round-Optimal Oblivious RAM with Applications to Searchable Encryption

Abstract. We presentTWORAM, the first efficient round-optimal oblivious RAM (ORAM) scheme. TWORAM provides oblivious access of a memory index y in exactly two rounds: The client prepares an encrypted query encapsulating y and sends it to the server. The server accesses memory obliviously and returns en-crypted information containing the desired value M[y]. The cost of TWORAM is only a multiplicative factor of security parameter higher than the tree-based ORAM schemes such as the path ORAM of Stefanov et al. (CCS, 2013).TWORAM gives rise to interesting applications, and in particular to the first fully-secure searchable symmetric encryption scheme where search is sublinear and search pattern is not leaked—access pattern can also be concealed if we assume the doc-uments are stored in the obliviously accessed memory M.