The Library
Revisiting square-root ORAM : efficient random access in multi-party computation
Tools
Tools
Tools
Zahur, Samee, Wang, Xiao, Raykova, Mariana, Gascon, Adrià, Doerner, Jack, Evans, David and Katz, Jonathan (2016) Revisiting square-root ORAM : efficient random access in multi-party computation. In: IEEE Symposium on Security and Privacy, San Jose, CA, USA, 22-26 May 2016 pp. 218-234.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
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.
| Item Type: | Conference Item (Paper) | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
| Publisher: | IEEE Computer Society | ||||||||
| Official Date: | 2016 | ||||||||
| Dates: |
|
||||||||
| Page Range: | pp. 218-234 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||||
| Conference Paper Type: | Paper | ||||||||
| Title of Event: | IEEE Symposium on Security and Privacy | ||||||||
| Type of Event: | Conference | ||||||||
| Location of Event: | San Jose, CA, USA | ||||||||
| Date(s) of Event: | 22-26 May 2016 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
