TY - GEN
T1 - Revisiting Square-Root ORAM
T2 - 2016 IEEE Symposium on Security and Privacy, SP 2016
AU - Zahur, Samee
AU - Wang, Xiao
AU - Raykova, Mariana
AU - Gascon, Adria
AU - Doerner, Jack
AU - Evans, David
AU - Katz, Jonathan
PY - 2016/8/16
Y1 - 2016/8/16
N2 - Hiding memory access patterns is required for secure computation, but remains prohibitively expensive for many interesting applications. Prior work has either developed custom algorithms that minimize the need for data-dependant memory access, or proposed the use of Oblivious RAM (ORAM) to provide a general-purpose solution. However, most ORAMs are designed for client-server scenarios, and provide only asymptotic benefits in secure computation. Even the best prior schemes show concrete benefits over naïve linear scan only for array sizes greater than 100. This immediately implies each ORAM access is 100 times slower than a single access at a known location. Even then, prior evaluations ignore the substantial initialization cost of existing schemes. We show 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. Specifically, we show a design that has over 100x lower initialization cost, and provides benefits over linear scan for just 8 blocks of data. For all benchmark applications we tried, including Gale-Shapley stable matching and the scrypt key derivation function, our scheme outperforms alternate approaches across a wide range of parameters, often by several orders of magnitude.
AB - Hiding memory access patterns is required for secure computation, but remains prohibitively expensive for many interesting applications. Prior work has either developed custom algorithms that minimize the need for data-dependant memory access, or proposed the use of Oblivious RAM (ORAM) to provide a general-purpose solution. However, most ORAMs are designed for client-server scenarios, and provide only asymptotic benefits in secure computation. Even the best prior schemes show concrete benefits over naïve linear scan only for array sizes greater than 100. This immediately implies each ORAM access is 100 times slower than a single access at a known location. Even then, prior evaluations ignore the substantial initialization cost of existing schemes. We show 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. Specifically, we show a design that has over 100x lower initialization cost, and provides benefits over linear scan for just 8 blocks of data. For all benchmark applications we tried, including Gale-Shapley stable matching and the scrypt key derivation function, our scheme outperforms alternate approaches across a wide range of parameters, often by several orders of magnitude.
UR - http://www.scopus.com/inward/record.url?scp=84987596928&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84987596928&partnerID=8YFLogxK
U2 - 10.1109/SP.2016.21
DO - 10.1109/SP.2016.21
M3 - Conference contribution
AN - SCOPUS:84987596928
T3 - Proceedings - 2016 IEEE Symposium on Security and Privacy, SP 2016
SP - 218
EP - 234
BT - Proceedings - 2016 IEEE Symposium on Security and Privacy, SP 2016
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 23 May 2016 through 25 May 2016
ER -