Secure computation with RAMs: revisiting square root ORAM and low leakage secure Boolean queries

Speaker: Mariana Raykova (Yale University, USA)

Date: 22 August 2017

Time: 14:00 – 15:00

Venue: The Alan Turing Institute.

Watch event video online.

Hiding memory access patterns is required for secure computation, but remains prohibitively expensive for many interesting applications. This talk presents two works addressing this question: a new oblivious RAM (ORAM) construction and a secure computation scheme using ORAM in the context of Boolean database queries.
Many prior works have developed ORAM solutions, which provide asymptotic benefits for secure computation, but require large database sizes to improve the concrete efficiency of naïve linear scan. The talk presents a new construction that shows how the classical square-root ORAM of Goldreich and Ostrovsky can be modified to overcome these problems, even though it is asymptotically worse than the best known schemes.
The presentation also covers a new encrypted search scheme that reduces the leakage of current Boolean queries solutions. This solution is based on a hybrid approach, which integrates ORAM techniques with the efficient search index structure of the Blind Seer system.


Mariana Raykova is an Assistant Professor at Yale University with research focus in cryptography and security. She obtained her PhD from Columbia University in 2012 and was a postdoc at the cryptography group at IBM Research Watson. Prior to joining Yale she was a research scientist for two years at SRI. Her work develops new cryptographic techniques that facilitate the use of private data while protecting the privacy of the data and guaranteeing verifiability. Her research interests include secure computation, verifiable computation and obfuscation. Beyond constructing new cryptographic protocols, her work also focuses on implementations that leverage the newly developed cryptographic tools and optimize the efficiency of the resulting systems both at algorithmic and systems level aiming for realistic loads.