Article

Constants count: practical improvements to oblivious RAM

Authors:

Christopher Fletcher,

Marten Van Dijk,

Srinivas DevadasAuthors Info & Claims

SEC'15: Proceedings of the 24th USENIX Conference on Security Symposium

Pages 415 - 430

Published: 12 August 2015 Publication History

Abstract

Oblivious RAM (ORAM) is a cryptographic primitive that hides memory access patterns as seen by untrusted storage. This paper proposes Ring ORAM, the most bandwidth-efficient ORAM scheme for the small client storage setting in both theory and practice. Ring ORAM is the first tree-based ORAM whose bandwidth is independent of the ORAM bucket size, a property that unlocks multiple performance improvements. First, Ring ORAM's overall bandwidth is 2.3× to 4× better than Path ORAM, the prior-art scheme for small client storage. Second, if memory can perform simple untrusted computation, Ring ORAM achieves constant online bandwidth (∼ 60× improvement over Path ORAM for practical parameters). As a case study, we show Ring ORAM speeds up program completion time in a secure processor by 1.5× relative to Path ORAM. On the theory side, Ring ORAM features a tighter and significantly simpler analysis than Path ORAM.

References

[1]

BONEH, D., MAZIERES, D., AND POPA, R. A. Remote oblivious storage: Making oblivious RAM practical. Manuscript, http://dspace.mit.edu/bitstream/ handle/1721.1/62006/MIT-CSAIL-TR-2011-018.pdf, 2011.

[2]

DAMGÅRD, I., MELDGAARD, S., AND NIELSEN, J. B. Perfectly secure oblivious RAM without random oracles. In TCC (2011).

Digital Library

[3]

DAUTRICH, J., STEFANOV, E., AND SHI, E. Burst oram: Minimizing oram response times for bursty access patterns. In USENIX (2014).

Digital Library

[4]

DEVADAS, S., VAN DIJK, M., FLETCHER, C. W., REN, L., SHI, E., AND WICHS, D. Onion oram: A constant bandwidth blowup oblivious ram. Cryptology ePrint Archive, 2015. http://eprint.iacr.org/2015/005.

[5]

FLETCHER, C., REN, L., KWON, A., VAN DIJK, M., AND DEVADAS, S. Freecursive oram: [nearly] free recursion and integrity verification for position-based oblivious ram. In ASPLOS (2015).

Digital Library

[6]

FLETCHER, C., REN, L., KWON, A., VAN DIJK, M., STEFANOV, E., SERPANOS, D., AND DEVADAS, S. A low-latency, low-area hardware oblivious ram controller. In FCCM (2015).

[7]

FLETCHER, C., REN, L., YU, X., VAN DIJK, M., KHAN, O., AND DEVADAS, S. Suppressing the oblivious ram timing channel while making information leakage and program efficiency trade-offs. In HPCA (2014).

[8]

FLETCHER, C., VAN DIJK, M., AND DEVADAS, S. Secure Processor Architecture for Encrypted Computation on Untrusted Programs. In STC (2012).

Digital Library

[9]

GENTRY, C., GOLDMAN, K. A., HALEVI, S., JUTLA, C. S., RAYKOVA, M., AND WICHS, D. Optimizing oram and using it efficiently for secure computation. In PET (2013).

[10]

GOLDREICH, O. Towards a theory of software protection and simulation on oblivious rams. In STOC (1987).

Digital Library

[11]

GOLDREICH, O., AND OSTROVSKY, R. Software protection and simulation on oblivious rams. In J. ACM (1996).

Digital Library

[12]

GOODRICH, M. T., AND MITZENMACHER, M. Privacy-preserving access of outsourced data via oblivious ram simulation. In ICALP (2011).

Digital Library

[13]

GOODRICH, M. T., MITZENMACHER, M., OHRIMENKO, O., AND TAMASSIA, R. Privacy-preserving group data access via stateless oblivious RAM simulation. In SODA (2012).

Digital Library

[14]

ISLAM, M., KUZU, M., AND KANTARCIOGLU, M. Access pattern disclosure on searchable encryption: Ramification, attack and mitigation. In NDSS (2012).

[15]

KUSHILEVITZ, E., LU, S., AND OSTROVSKY, R. On the (in) security of hash-based oblivious ram and a new balancing scheme. In SODA (2012).

Digital Library

[16]

LIU, C., HARRIS, A., MAAS, M., HICKS, M., TIWARI, M., AND SHI, E. Ghostrider: A hardware-software system for memory trace oblivious computation. In ASPLOS (2015).

Digital Library

[17]

LORCH, J. R., PARNO, B., MICKENS, J.W., RAYKOVA, M., AND SCHIFFMAN, J. Shroud: Ensuring private access to large-scale data in the data center. In FAST (2013).

Digital Library

[18]

MAAS, M., LOVE, E., STEFANOV, E., TIWARI, M., SHI, E., ASANOVIC, K., KUBIATOWICZ, J., AND SONG, D. Phantom: Practical oblivious computation in a secure processor. In CCS (2013).

Digital Library

[19]

MAYBERRY, T., BLASS, E.-O., AND CHAN, A. H. Efficient private file retrieval by combining oram and pir. In NDSS (2014).

[20]

OSTROVSKY, R. Efficient computation on oblivious rams. In STOC (1990).

Digital Library

[21]

OSTROVSKY, R., AND SHOUP, V. Private information storage (extended abstract). In STOC (1997).

Digital Library

[22]

REN, L., YU, X., FLETCHER, C., VAN DIJK, M., AND DEVADAS, S. Design space exploration and optimization of path oblivious ram in secure processors. In ISCA (2013).

Digital Library

[23]

SHI, E., CHAN, T.-H. H., STEFANOV, E., AND LI, M. Oblivious ram with o((logn)³) worst-case cost. In Asiacrypt (2011).

Digital Library

[24]

STEFANOV, E., AND SHI, E. Oblivistore: High performance oblivious cloud storage. In S&P (2013).

Digital Library

[25]

STEFANOV, E., SHI, E., AND SONG, D. Towards practical oblivious RAM. In NDSS (2012).

[26]

STEFANOV, E., VAN DIJK, M., SHI, E., CHAN, T.- H. H., FLETCHER, C., REN, L., YU, X., AND DEVADAS, S. Path oram: An extremely simple oblivious ram protocol. Cryptology ePrint Archive, 2013. http: //eprint.iacr.org/2013/280.

Digital Library

[27]

STEFANOV, E., VAN DIJK, M., SHI, E., FLETCHER, C., REN, L., YU, X., AND DEVADAS, S. Path oram: An extremely simple oblivious ram protocol. In CCS (2013).

Digital Library

[28]

WANG, X. S., CHAN, T.-H. H., AND SHI, E. Circuit oram: On tightness of the goldreich-ostrovsky lower bound. Cryptology ePrint Archive, 2014. http:// eprint.iacr.org/2014/672.

[29]

WILLIAMS, P., AND SION, R. Single round access privacy on outsourced storage. In CCS (2012).

Digital Library

[30]

WILLIAMS, P., SION, R., AND TOMESCU, A. Privatefs: A parallel oblivious file system. In CCS (2012).

Digital Library

[31]

YU, X., FLETCHER, C. W., REN, L., VAN DIJK, M., AND DEVADAS, S. Generalized external interaction with tamper-resistant hardware with bounded information leakage. In CCSW (2013).

Digital Library

[32]

ZHUANG, X., ZHANG, T., AND PANDE, S. HIDE: an infrastructure for efficiently protecting information leakage on the address bus. In ASPLOS (2004).

Digital Library

Cited By

Tinoco AGao SShi ECalandrino JTroncoso C(2023)ENIGMAPProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620463(4033-4050)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620463
Maiyya SVemula SAgrawal DEl Abbadi AKerschbaum F(2023)Waffle: An Online Oblivious Datastore for Protecting Data Access PatternsProceedings of the ACM on Management of Data10.1145/36267601:4(1-25)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626760
Asharov GKomargodski IMichelson YMeng WJensen CCremers CKirda E(2023)FutORAMa: A Concretely Efficient Hierarchical Oblivious RAMProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623125(3313-3327)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623125
Show More Cited By

Recommendations

Generalized Non-Interactive Oblivious Transfer Using Count-Limited Objects with Applications to Secure Mobile Agents
Financial Cryptography and Data Security

Oblivious transfer (OT) is a fundamental primitive used in many cryptographic protocols, including general secure function evaluation (SFE) protocols. However, interaction is a primary feature of any OT protocol. In this paper, we show how to remove the ...
Split, count, and share: a differentially private set intersection cardinality estimation protocol
UAI '23: Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence

We describe a simple two-party protocol in which each party contributes a set as input. The output of the protocol is an estimate of the cardinality of the intersection of the two input sets. We show that our protocol is efficient and secure. We show that ...
Maliciously Secure MPC From Semi-Honest 2PC in the Server-Aided Model
Secure multi-party computation (MPC) provides provable security guarantees for many privacy critical applications. The semi-honest MPC protocols are secure against semi-honest adversaries who can only observe the protocol execution, while the maliciously ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

SEC'15: Proceedings of the 24th USENIX Conference on Security Symposium

August 2015

1072 pages

ISBN:9781931971232

Editor:
Jaeyeon Jung
Microsoft Research

Sponsors

USENIX Assoc: USENIX Assoc

Publisher

USENIX Association

United States

Publication History

Published: 12 August 2015

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tinoco AGao SShi ECalandrino JTroncoso C(2023)ENIGMAPProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620463(4033-4050)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620463
Maiyya SVemula SAgrawal DEl Abbadi AKerschbaum F(2023)Waffle: An Online Oblivious Datastore for Protecting Data Access PatternsProceedings of the ACM on Management of Data10.1145/36267601:4(1-25)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626760
Asharov GKomargodski IMichelson YMeng WJensen CCremers CKirda E(2023)FutORAMa: A Concretely Efficient Hierarchical Oblivious RAMProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623125(3313-3327)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623125
Kuang JShen MLu YXiao NOshana R(2022)Exploiting data locality in memory for ORAM to reduce memory access overheadsProceedings of the 59th ACM/IEEE Design Automation Conference10.1145/3489517.3530547(703-708)Online publication date: 10-Jul-2022
https://dl.acm.org/doi/10.1145/3489517.3530547
Holland WOhrimenko OWirth ASuga YSakurai KDing XSako K(2022)Efficient Oblivious Permutation via the Waksman NetworkProceedings of the 2022 ACM on Asia Conference on Computer and Communications Security10.1145/3488932.3497761(771-783)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1145/3488932.3497761
Liu GLi KXiao ZWang RSalapura VZahran MChong FTang L(2022)PS-ORAMProceedings of the 49th Annual International Symposium on Computer Architecture10.1145/3470496.3527425(188-203)Online publication date: 18-Jun-2022
https://dl.acm.org/doi/10.1145/3470496.3527425
Burkhalter LHithnawi AViand AShafagh HRatnasamy SBhagwan RPorter G(2020)TimeCryptProceedings of the 17th Usenix Conference on Networked Systems Design and Implementation10.5555/3388242.3388302(835-850)Online publication date: 25-Feb-2020
https://dl.acm.org/doi/10.5555/3388242.3388302
Lin WShi EXie TChan T(2019)Can we overcome the n log n barrier for oblivious sorting?Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310583(2419-2438)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310583
Ordean MRyan MGalindo DKerschbaum FMashatan ANiu JLee A(2019)CAOSProceedings of the 24th ACM Symposium on Access Control Models and Technologies10.1145/3322431.3325101(13-24)Online publication date: 28-May-2019
https://dl.acm.org/doi/10.1145/3322431.3325101
Chen HChillotti IRen LCavallaro LKinder JWang XKatz J(2019)Onion Ring ORAMProceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security10.1145/3319535.3354226(345-360)Online publication date: 6-Nov-2019
https://dl.acm.org/doi/10.1145/3319535.3354226
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten