View article

We present , an asymptotically efficient oblivious RAM (ORAM) protocol providing oblivious access (read and write) 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 encrypted information containing the desired value . The cost of is only a multiplicative factor of security parameter higher than the tree-based ORAM schemes such as the path ORAM scheme of Stefanov et al. [34].

gives rise to interesting applications, and in particular to a 4-round symmetric searchable encryption scheme where search is sublinear in the worst case and the search pattern is not leaked—the access pattern can also be concealed assuming the documents are stored in the obliviously accessed memory .