research-article

Path ORAM: an extremely simple oblivious RAM protocol

Authors:

Marten van Dijk,

Christopher Fletcher,

Srinivas DevadasAuthors Info & Claims

CCS '13: Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security

Pages 299 - 310

https://doi.org/10.1145/2508859.2516660

Published: 04 November 2013 Publication History

Abstract

We present Path ORAM, an extremely simple Oblivious RAM protocol with a small amount of client storage. Partly due to its simplicity, Path ORAM is the most practical ORAM scheme for small client storage known to date. We formally prove that Path ORAM requires log^2 N / log X bandwidth overhead for block size B = X log N. For block sizes bigger than Omega(log^2 N), Path ORAM is asymptotically better than the best known ORAM scheme with small client storage. Due to its practicality, Path ORAM has been adopted in the design of secure processors since its proposal.

References

[1]

Personal communication with Kai-Min Chung, 2013.

[2]

M. Ajtai. Oblivious rams without cryptogrpahic assumptions. In Proceedings of the 42nd ACM symposium on Theory of computing, STOC'10, pages 181--190, 2010.

Digital Library

[3]

D. Asonov and J.-C. Freytag. Almost optimal private information retrieval. In PET, 2003.

Digital Library

[4]

D. Boneh, D. Mazieres, and R. A. Popa. Remote oblivious storage: Making oblivious RAM practical. Manuscript, http://dspace.mit.edu/bitstream/handle/1721.1/62006/ MIT-CSAIL-TR-2011-018.pdf, 2011.

[5]

K.-M. Chung, Z. Liu, and R. Pass. Statistically-secure oram with O (log2 n) overhead. http://arxiv.org/abs/1307.3699, 2013.

[6]

K.-M. Chung and R. Pass. A simple oram. https://eprint.iacr.org/2013/243.pdf, 2013.

[7]

I. Damgard, S. Meldgaard, and J. B. Nielsen. Perfectly secure oblivious RAM without random oracles. In TCC, 2011.

Digital Library

[8]

I. Damgard, S. Meldgaard, and J. B. Nielsen. Perfectly secure oblivious ram without random oracles. In TCC, pages 144--163, 2011.

Digital Library

[9]

C. Fletcher, M. van Dijk, and S. Devadas. Secure Processor Architecture for Encrypted Computation on Untrusted Programs. In Proceedings of the 7th ACM CCS Workshop on Scalable Trusted Computing, pages 3--8, Oct. 2012.

Digital Library

[10]

C. W. Fletcher. Ascend: An architecture for performing secure computation on encrypted data. In MIT CSAIL CSG Technical Memo 508, April 2013.

[11]

C. Gentry, K. Goldman, S. Halevi, C. Julta, M. Raykova, and D. Wichs. Optimizing oram and using it efficiently for secure computation. In PETS, 2013.

[12]

O. Goldreich. Towards a theory of software protection and simulation by oblivious rams. In STOC, 1987.

Digital Library

[13]

O. Goldreich and R. Ostrovsky. Software protection and simulation on oblivious rams. J. ACM, 1996.

Digital Library

[14]

M. T. Goodrich and M. Mitzenmacher. Privacy-preserving access of outsourced data via oblivious RAM simulation. In ICALP, 2011.

Digital Library

[15]

M. T. Goodrich, M. Mitzenmacher, O. Ohrimenko, and R. Tamassia. Oblivious ram simulation with efficient worst-case access overhead. In Proceedings of the 3rd ACM workshop on Cloud computing security workshop, CCSW'11, pages 95--100, New York, NY, USA, 2011. ACM.

Digital Library

[16]

M. T. Goodrich, M. Mitzenmacher, O. Ohrimenko, and R. Tamassia. Practical oblivious storage. In CODASPY, 2012.

Digital Library

[17]

M. T. Goodrich, M. Mitzenmacher, O. Ohrimenko, and R. Tamassia. Privacy-preserving group data access via stateless oblivious RAM simulation. In SODA, 2012.

Digital Library

[18]

M. T. Goodrich, M. Mitzenmacher, O. Ohrimenko, and R. Tamassia. Privacy-preserving group data access via stateless oblivious ram simulation. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, pages 157--167. SIAM, 2012.

Digital Library

[19]

M. Harchol-Balter. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press, 2013.

Digital Library

[20]

A. Iliev and S. W. Smith. Protecting client privacy with trusted computing at the server. IEEE Security and Privacy, 3(2):20--28, Mar. 2005.

Digital Library

[21]

M. Islam, M. Kuzu, and M. Kantarcioglu. Access pattern disclosure on searchable encryption: Ramification, attack and mitigation. In Network and Distributed System Security Symposium (NDSS), 2012.

[22]

E. Kushilevitz, S. Lu, and R. Ostrovsky. On the (in)security of hash-based oblivious RAM and a new balancing scheme. In SODA, 2012.

Digital Library

[23]

J. R. Lorch, B. Parno, J. W. Mickens, M. Raykova, and J. Schiffman. Shroud: Ensuring private access to large-scale data in the data center. FAST, 2013:199--213, 2013.

[24]

M. Maas, E. Love, E. Stefanov, M. Tiwari, E. Shi, K. Asanovic, J. Kubiatowicz, and D. Song. Phantom: Practical oblivious computation in a secure processor. ACM CCS, 2013.

Digital Library

[25]

R. Ostrovsky. Efficient computation on oblivious rams. In STOC, 1990.

Digital Library

[26]

R. Ostrovsky and V. Shoup. Private information storage (extended abstract). In STOC, pages 294{303, 1997.

Digital Library

[27]

B. Pinkas and T. Reinman. Oblivious RAM revisited. In CRYPTO, 2010.

Digital Library

[28]

L. Ren, C. Fletcher, X. Yu, M. van Dijk, and S. Devadas. Integrity verification for path oblivious-ram. In Proceedings of the 17th IEEE High Performance Extreme Computing Conference, September 2013.

[29]

L. Ren, X. Yu, C. Fletcher, M. van Dijk, and S. Devadas. Design space exploration and optimization of path oblivious ram in secure processors. In Proceedings of the Int'l Symposium on Computer Architecture, pages 571--582, June 2013. Available at Cryptology ePrint Archive, Report 2012/76.

Digital Library

[30]

E. Shi, T.-H. H. Chan, E. Stefanov, and M. Li. Oblivious RAM with O((logN)3) worst-case cost. In ASIACRYPT, pages 197{214, 2011.

Digital Library

[31]

S. W. Smith and D. Safford. Practical server privacy with secure coprocessors. IBM Syst. J., 40(3):683{695, Mar. 2001.

Digital Library

[32]

E. Stefanov and E. Shi. Path o-ram: An extremely simple oblivious ram protocol. CoRR, abs/1202.5150, 2012.

[33]

E. Stefanov and E. Shi. ObliviStore: High performance oblivious cloud storage. In IEEE Symposium on Security and Privacy, 2013.

Digital Library

[34]

E. Stefanov, E. Shi, and D. Song. Towards practical oblivious RAM. In NDSS, 2012.

[35]

P. Williams and R. Sion. Usable PIR. In NDSS, 2008.

[36]

P. Williams and R. Sion. Round-optimal access privacy on outsourced storage. In CCS, 2012.

Digital Library

[37]

P. Williams, R. Sion, and B. Carbunar. Building castles out of mud: practical access pattern privacy and correctness on untrusted storage. In CCS, 2008.

Digital Library

[38]

P. Williams, R. Sion, and A. Tomescu. Privatefs: A parallel oblivious file system. In CCS, 2012.

Digital Library

Cited By

Xie HGuo YMiao YJia X(2025)Access-Pattern Hiding Search Over Encrypted Databases by Using Distributed Point FunctionsIEEE Transactions on Computers10.1109/TC.2024.350428874:3(1066-1078)Online publication date: Mar-2025
https://doi.org/10.1109/TC.2024.3504288
Jiang QQi SYang XQi YWang JLu YAn BChang E(2025)Reducing Paging and Exit Overheads in Intel SGX for Oblivious Conjunctive Keyword SearchIEEE Transactions on Computers10.1109/TC.2023.328185774:3(776-789)Online publication date: Mar-2025
https://doi.org/10.1109/TC.2023.3281857
Lee KAshok MMaji SAgrawal RJoshi AYan MEmer JChandrakasan A(2025)Secure Machine Learning Hardware: Challenges and Progress [Feature]IEEE Circuits and Systems Magazine10.1109/MCAS.2024.350937625:1(8-34)Online publication date: Sep-2026
https://doi.org/10.1109/MCAS.2024.3509376
Show More Cited By

Index Terms

Path ORAM: an extremely simple oblivious RAM protocol
1. Security and privacy
2. Social and professional topics
  1. Computing / technology policy
    1. Computer crime

Recommendations

Path ORAM: An Extremely Simple Oblivious RAM Protocol
Distributed Computing, Cryptography, Distributed Computing, Cryptography, Coding Theory, Automata Theory, Complexity Theory, Programming Languages, Algorithms, Invited Paper Foreword and Databases

We present Path ORAM, an extremely simple Oblivious RAM protocol with a small amount of client storage. Partly due to its simplicity, Path ORAM is the most practical ORAM scheme known to date with small client storage. We formally prove that Path ORAM ...
Three-Party ORAM for Secure Computation
Proceedings, Part I, of the 21st International Conference on Advances in Cryptology -- ASIACRYPT 2015 - Volume 9452

An Oblivious RAM ORAM protocol [13] allows a client to retrieve $${\mathrm {N}}$$-th element of a data array $${\mathsf {D}}$$ stored by the server s.t. the server learns no information about $${\mathrm {N}}$$. A related notion is that of an ORAM for ...
Onion Ring ORAM: Efficient Constant Bandwidth Oblivious RAM from (Leveled) TFHE
CCS '19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security

Oblivious RAM (ORAM) is a cryptographic primitive that allows a client to hide access pattern to its data encrypted and stored at a remote server. Traditionally, ORAM algorithms assume the server acts purely as a storage device. Under this assumption, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '13: Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security

November 2013

1530 pages

ISBN:9781450324779

DOI:10.1145/2508859

General Chair:
Ahmad-Reza Sadeghi
TU Darmstadt, CASED, Intel ICRI-SC, Germany
,
Program Chairs:
Virgil Gligor
Carnegie Mellon University, USA
,
Moti Yung
Columbia University, USA

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 November 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS'13

Sponsor:

SIGSAC

CCS'13: 2013 ACM SIGSAC Conference on Computer and Communications Security

November 4 - 8, 2013

Berlin, Germany

Acceptance Rates

CCS '13 Paper Acceptance Rate 105 of 530 submissions, 20%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

525
Total Citations
View Citations
2,608
Total Downloads

Downloads (Last 12 months)127
Downloads (Last 6 weeks)65

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xie HGuo YMiao YJia X(2025)Access-Pattern Hiding Search Over Encrypted Databases by Using Distributed Point FunctionsIEEE Transactions on Computers10.1109/TC.2024.350428874:3(1066-1078)Online publication date: Mar-2025
https://doi.org/10.1109/TC.2024.3504288
Jiang QQi SYang XQi YWang JLu YAn BChang E(2025)Reducing Paging and Exit Overheads in Intel SGX for Oblivious Conjunctive Keyword SearchIEEE Transactions on Computers10.1109/TC.2023.328185774:3(776-789)Online publication date: Mar-2025
https://doi.org/10.1109/TC.2023.3281857
Lee KAshok MMaji SAgrawal RJoshi AYan MEmer JChandrakasan A(2025)Secure Machine Learning Hardware: Challenges and Progress [Feature]IEEE Circuits and Systems Magazine10.1109/MCAS.2024.350937625:1(8-34)Online publication date: Sep-2026
https://doi.org/10.1109/MCAS.2024.3509376
Li SJing XWang YXu XZhang ZWang J(2025)Practical Searchable Encryption Scheme Against Response Identity AttacksInformation Sciences10.1016/j.ins.2025.121975(121975)Online publication date: Feb-2025
https://doi.org/10.1016/j.ins.2025.121975
Weiss M(2025)Conditional Lower Bounds for Oblivious RAMEncyclopedia of Cryptography, Security and Privacy10.1007/978-3-030-71522-9_1786(414-417)Online publication date: 8-Jan-2025
https://doi.org/10.1007/978-3-030-71522-9_1786
Ren L(2025)Oblivious RAM-Based Secure ProcessorsEncyclopedia of Cryptography, Security and Privacy10.1007/978-3-030-71522-9_1553(1724-1727)Online publication date: 8-Jan-2025
https://doi.org/10.1007/978-3-030-71522-9_1553
Mondal PChamani JDemertzis IPapadopoulos DBalzarotti DXu W(2024)I/O-efficient dynamic searchable encryption meets forward & backward privacyProceedings of the 33rd USENIX Conference on Security Symposium10.5555/3698900.3699042(2527-2544)Online publication date: 14-Aug-2024
https://dl.acm.org/doi/10.5555/3698900.3699042
Appan AHeath DRen LLuo BLiao XXu JKirda ELie D(2024)Oblivious Single Access Machines - A New Model for Oblivious ComputationProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690352(3080-3094)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690352
Lim HKim JLee HLuo BLiao XXu JKirda ELie D(2024)uMMU: Securing Data Confidentiality with Unobservable Memory SubsystemProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690340(2993-3007)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690340
Sha MCai YWang SPhan LLi FTan K(2024)Object-oriented Unified Encrypted Memory Management for Heterogeneous Memory ArchitecturesProceedings of the ACM on Management of Data10.1145/36549582:3(1-29)Online publication date: 30-May-2024
https://doi.org/10.1145/3654958
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten