More Web Proxy on the site http://driver.im/

research-article

Single round access privacy on outsourced storage

Authors:

Peter Williams,

Radu SionAuthors Info & Claims

CCS '12: Proceedings of the 2012 ACM conference on Computer and communications security

Pages 293 - 304

https://doi.org/10.1145/2382196.2382229

Published: 16 October 2012 Publication History

Abstract

We present SR-ORAM¹, the first single-round-trip polylogarithmic time Oblivious RAM that requires only logarithmic client storage. Taking only a single round trip to perform a query, SR-ORAM has an online communication / computation cost of O(log n log log n), and an offline, overall amortized per-query communication cost of O(log² n log log n), requiring under 2 round trips. The client folds an entire interactive sequence of Oblivious RAM requests into a single query object that the server can unlock incrementally, to satisfy a query without learning its result. This results in an Oblivious RAM secure against an actively malicious adversary, with unprecedented speeds in accessing large data sets over high-latency links. We show this to be the most efficient storage-free-client Oblivious RAM to date for today's Internet-scale network latencies.

References

[1]

M. Ajtai, J. Komlos, and E. Szemeredi. An O(n log n) sorting network. In Proceedings of the 25th ACM Symposium on Theory of Computing, pages 1--9, 1983.

Digital Library

[2]

Dimitri Asonov. Querying Databases Privately: A New Approach to Private Information Retrieval. Springer Verlag, 2004.

Digital Library

[3]

B. H. Bloom. Space/time trade-offs in hash coding with allowable errors. Commun. ACM, 13(7):422--426, 1970.

Digital Library

[4]

Dan Boneh, David Maziéres, and Raluca Ada Popa. Remote oblivious storage: Making Oblivious RAM practical. Technical report, MIT, 2011. MIT-CSAIL-TR-2011-018 March 30, 2011.

[5]

Ivan Damgard, Sigurd Meldgaard, and Jesper Nielsen. Perfectly secure Oblivious RAM without random oracles. In Theory of Cryptography, volume 6597 of Lecture Notes in Computer Science, pages 144--163. 2011.

Digital Library

[6]

Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on Oblivious RAMs. Journal of the ACM, 45:431--473, May 1996.

Digital Library

[7]

Michael Goodrich and Michael Mitzenmacher. Mapreduce parallel cuckoo hashing and Oblivious RAM simulations. In 38th International Colloquium on Automata, Languages and Programming (ICALP), 2011.

[8]

Michael Goodrich, Michael Mitzenmacher, Olga Ohrimenko, and Roberto Tamassia. Oblivious RAM simulation with efficient worst-case access overhead. In ACM Cloud Computing Security Workshop at CCS (CCSW), 2011.

Digital Library

[9]

Michael T. Goodrich. Randomized shellsort: A simple oblivious sorting algorithm. In Proceedings 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010.

Digital Library

[10]

Michael T. Goodrich, Michael Mitzenmacher, Olga Ohrimenko, and Roberto Tamassia. Practical oblivious storage. In Proceedings of the second ACM conference on Data and Application Security and Privacy, CODASPY '12, pages 13--24, New York, NY, USA, 2012. ACM.

Digital Library

[11]

IBM. IBM 4764 PCI-X Cryptographic Coprocessor (PCIXCC). Online at http://www-03.ibm.com/security/cryptocards/pcixcc/overview.shtml, 2006.

[12]

A. Iliev and S.W. Smith. Private information storage with logarithmic-space secure hardware. In Proceedings of i-NetSec 04: 3rd Working Conference on Privacy and Anonymity in Networked and Distributed Systems, pages 201--216, 2004.

[13]

Eyal Kushilevitz, Steve Lu, and Rafail Ostrovsky. On the (in)security of hash-based oblivious RAM and a new balancing scheme. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, pages 143--156. SIAM, 2012.

Digital Library

[14]

Benny Pinkas and Tzachy Reinman. Oblivious RAM revisited. In CRYPTO, pages 502--519, 2010.

Digital Library

[15]

Sean W. Smith and David Safford. Practical server privacy with secure coprocessors. IBM Systems Journal, 40(3):683--695, 2001.

Digital Library

[16]

Emil Stefanov, Elaine Shi, and Dawn Song. Towards Practical Oblivious RAM. In Proceedings of the Network and Distributed System Security Symposium (NDSS), 2012.

[17]

Shuhong Wang, Xuhua Ding, Robert H. Deng, and Feng Bao. Private information retrieval using trusted hardware. In Proceedings of the European Symposium on Research in Computer Security ESORICS, pages 49--64, 2006.

Digital Library

[18]

Peter Williams and Radu Sion. SR-ORAM: Single round-trip Oblivious RAM. In Industrial Track of ACNS, 2012.

[19]

Peter Williams, Radu Sion, and Bogdan Carbunar. Building castles out of mud: practical access pattern privacy and correctness on untrusted storage. In ACM Conference on Computer and Communications Security (CCS), pages 139--148, 2008.

Digital Library

Cited By

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
Holland WOhrimenko OWirth AQuek TGao DZhou JCardenas A(2024)Single Round-trip Hierarchical ORAM via Succinct IndicesProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3656290(1644-1659)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3656290
P. B. Niranjane (2023)Load Balancing Using Oblivious RAM for Privacy-Preserving Access to Big Data in CloudInternational Journal of Scientific Research in Science and Technology10.32628/IJSRST523102140(885-889)Online publication date: 10-Apr-2023
https://doi.org/10.32628/IJSRST523102140
Show More Cited By

Index Terms

Single round access privacy on outsourced storage

Recommendations

PrivateFS: a parallel oblivious file system
CCS '12: Proceedings of the 2012 ACM conference on Computer and communications security

PrivateFS is an oblivious file system that enables access to remote storage, while keeping both the file contents and client access patterns secret. PrivateFS is based on a new parallel Oblivious RAM mechanism (PD-ORAM)---instead of waiting for the ...
Practical Oblivious Outsourced Storage

In this article we introduce a technique, guaranteeing access pattern privacy against a computationally bounded adversary, in outsourced data storage, with communication and computation overheads orders of magnitude better than existing approaches. In ...
Distributed oblivious RAM for secure two-party computation
TCC'13: Proceedings of the 10th theory of cryptography conference on Theory of Cryptography

We present a new method for secure two-party Random Access Memory (RAM) program computation that does not require taking a program and first turning it into a circuit. The method achieves logarithmic overhead compared to an insecure program execution.

...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '12: Proceedings of the 2012 ACM conference on Computer and communications security

October 2012

1088 pages

ISBN:9781450316514

DOI:10.1145/2382196

General Chair:
Ting Yu
North Carolina State University, USA
,
Program Chairs:
George Danezis
Microsoft Research Cambridge, UK
,
Virgil Gligor
Carnegie Mellon University, USA

Copyright © 2012 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 ACM 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: 16 October 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS'12

Sponsor:

SIGSAC

CCS'12: the ACM Conference on Computer and Communications Security

October 16 - 18, 2012

North Carolina, Raleigh, USA

Acceptance Rates

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

73
Total Citations
View Citations
809
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)2

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Holland WOhrimenko OWirth AQuek TGao DZhou JCardenas A(2024)Single Round-trip Hierarchical ORAM via Succinct IndicesProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3656290(1644-1659)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3656290
P. B. Niranjane (2023)Load Balancing Using Oblivious RAM for Privacy-Preserving Access to Big Data in CloudInternational Journal of Scientific Research in Science and Technology10.32628/IJSRST523102140(885-889)Online publication date: 10-Apr-2023
https://doi.org/10.32628/IJSRST523102140
Ji KZhang BLu TRen K(2023)Multi-Party Private Function Evaluation for RAMIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.323645718(1252-1267)Online publication date: 2023
https://doi.org/10.1109/TIFS.2023.3236457
Qi SWei WCheng JZheng YSu ZZhang JQi Y(2022)Secure and Efficient Item Traceability for Cloud-Aided IIoTACM Transactions on Sensor Networks10.1145/352274018:4(1-24)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3522740
Raoufi MZhang YYang J(2022)IR-ORAM: Path Access Type Based Memory Intensity Reduction for Path-ORAM2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA53966.2022.00034(360-372)Online publication date: Apr-2022
https://doi.org/10.1109/HPCA53966.2022.00034
Hazay CLilintal M(2021)Gradual GRAM and secure computation for RAM programsJournal of Computer Security10.3233/JCS-200107(1-33)Online publication date: 29-Oct-2021
https://doi.org/10.3233/JCS-200107
Zhang W(2021)A Practical Oblivious Cloud Storage System based on TEE and Client Gateway2021 18th International Conference on Privacy, Security and Trust (PST)10.1109/PST52912.2021.9647827(1-6)Online publication date: 13-Dec-2021
https://doi.org/10.1109/PST52912.2021.9647827
Weiss MWichs D(2021)Is There an Oblivious RAM Lower Bound for Online Reads?Journal of Cryptology10.1007/s00145-021-09392-134:3Online publication date: 11-May-2021
https://doi.org/10.1007/s00145-021-09392-1
Cash DDrucker AHoover A(2020)A Lower Bound for One-Round Oblivious RAMTheory of Cryptography10.1007/978-3-030-64375-1_16(457-485)Online publication date: 9-Dec-2020
https://doi.org/10.1007/978-3-030-64375-1_16
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.

Media

Figures

Other

Tables

View Table of Contents