Revisiting Square Root ORAM - Efficient Random Access in Multi-Party Computation

Explore a 14-minute conference talk presented at the 2016 IEEE Symposium on Security & Privacy that delves into improving the efficiency of random access in multi-party computation. Learn about a modified version of the classical square-root Oblivious RAM (ORAM) by Goldreich and Ostrovsky, which offers significant improvements over existing schemes. Discover how this approach achieves over 100 times lower initialization cost and provides benefits for as few as 8 blocks of data. Understand the implications of this research for various applications, including Gale-Shapley stable matching and the scrypt key derivation function, where the proposed scheme outperforms alternative approaches across a wide range of parameters, often by several orders of magnitude.