We present TWORAM, 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 M obliviously and returns encrypted 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 scheme of Stefanov et al. [34]. TWORAM gives rise to interesting applications, and in particular to a 4-round symmetric searchable encryption scheme where search is sub-linear 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 M.
展开▼
