Article

Privacy-preserving access of outsourced data via oblivious RAM simulation

Authors:

Michael T. Goodrich,

Michael MitzenmacherAuthors Info & Claims

ICALP'11: Proceedings of the 38th international conference on Automata, languages and programming - Volume Part II

Pages 576 - 587

Published: 04 July 2011 Publication History

Abstract

We describe schemes for the oblivious RAM simulation problem with a small logarithmic or polylogarithmic amortized increase in access times, with a very high probability of success, while keeping the external storage to be of size O(n).

References

[1]

Ajtai, M.: Oblivious RAMs without cryptographic assumptions. In: Proc. of the 42nd ACM Symp. on Theory of Computing (STOC), pp. 181-190. ACM, New York (2010).

Digital Library

[2]

Damgård, I., Meldgaard, S., Nielsen, J.B.: Perfectly secure oblivious RAM without random oracles. Cryptology ePrint Archive, Report 2010/108 (2010), http://eprint.iacr.org/

[3]

Drmota, M., Kutzelnigg, R.: A precise analysis of cuckoo hashing (2008) (preprint), http://www.dmg.tuwien.ac.at/drmota/cuckoohash.pdf

Digital Library

[4]

Feldman, J., Muthukrishnan, S., Sidiropoulos, A., Stein, C., Svitkina, Z.: On distributing symmetric streaming computations. In: ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 710-719 (2008).

Digital Library

[5]

Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious RAMs. J. ACM 43(3), 431-473 (1996).

Digital Library

[6]

Goodrich, M., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Privacy-preserving group data access via stateless oblivious RAM simulation (unpublished manuscript).

[7]

Goodrich, M.T., Mitzenmacher, M.: MapReduce Parallel Cuckoo Hashing and Oblivious RAM Simulations. ArXiv e-prints, Eprint 1007.1259v1 (July 2010).

[8]

Goodrich, M.T., Mitzenmacher, M.: Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation. ArXiv e-prints, Eprint 1007.1259v2 (April 2011).

[9]

Karloff, H., Suri, S., Vassilvitskii, S.: A model of computation for MapReduce. In: Proc. ACM-SIAM Sympos. Discrete Algorithms (SODA), pp. 938-948 (2010).

Digital Library

[10]

Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: cuckoo hashing with a stash. SIAM J. Comput. 39, 1543-1561 (2009).

Digital Library

[11]

Lee, D.-L., Batcher, K.E.: A multiway merge sorting network. IEEE Trans. on Parallel and Distributed Systems 6(2), 211-215 (1995).

Digital Library

[12]

McDiarmid, C.: Concentration. In: Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., Reed, B. (eds.) Probabilistic Methods for Algorithmic Discrete Mathematics, pp. 195-248. Springer, Berlin (1998).

[13]

Pagh, R., Rodler, F.: Cuckoo hashing. Journal of Algorithms 52, 122-144 (2004).

Digital Library

[14]

Pinkas, B., Reinman, T.: Oblivious RAM revisited. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 502-519. Springer, Heidelberg (2010).

Digital Library

[15]

Williams, P., Sion, R.: Usable pir. In: NDSS. The Internet Society, San Diego (2008).

[16]

Williams, P., Sion, R., Carbunar, B.: Building castles out of mud: practical access pattern privacy and correctness on untrusted storage. In: 15th ACM Conf. on Computer and Communications Security (CCS), pp. 139-148 (2008).

Digital Library

Cited By

Balle BBell JGascón AMeng WJensen CCremers CKirda E(2023)Amplification by Shuffling without ShufflingProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623215(2292-2305)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623215
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
Chan TChung KMaggs BShi E(2022)Foundations of Differentially Oblivious AlgorithmsJournal of the ACM10.1145/355598469:4(1-49)Online publication date: 26-Aug-2022
https://dl.acm.org/doi/10.1145/3555984
Show More Cited By

Index Terms

Privacy-preserving access of outsourced data via oblivious RAM simulation
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

OptORAMa: Optimal Oblivious RAM
Oblivious RAM (ORAM), first introduced in the ground-breaking work of Goldreich and Ostrovsky (STOC ’87 and J. ACM ’96) is a technique for provably obfuscating programs’ access patterns, such that the access patterns leak no information about the programs’...
Privacy-preserving group data access via stateless oblivious RAM simulation
SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms

Motivated by cloud computing applications, we study the problem of providing privacy-preserving access to an outsourced honest-but-curious data repository for a group of trusted users. We show how to achieve efficient privacy-preserving data access ...
OptORAMa: Optimal Oblivious RAM
Advances in Cryptology – EUROCRYPT 2020
Abstract
Oblivious RAM (ORAM), first introduced in the ground-breaking work of Goldreich and Ostrovsky (STOC ’87 and J. ACM ’96) is a technique for provably obfuscating programs’ access patterns, such that the access patterns leak no information about the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ICALP'11: Proceedings of the 38th international conference on Automata, languages and programming - Volume Part II

July 2011

665 pages

ISBN:9783642220111

Editors:
Luca Aceto
Reykjavik University, School of Computer Science, Reykjavík, Iceland
,
Monika Henzinger
Universität Wien, Fakultät für Informatik, Wien, Österreich
,
Jiří Sgall
Charles University, Department of Applied Mathematics, Praha 1, Czech Republic

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 04 July 2011

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

56
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Balle BBell JGascón AMeng WJensen CCremers CKirda E(2023)Amplification by Shuffling without ShufflingProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623215(2292-2305)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623215
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
Chan TChung KMaggs BShi E(2022)Foundations of Differentially Oblivious AlgorithmsJournal of the ACM10.1145/355598469:4(1-49)Online publication date: 26-Aug-2022
https://dl.acm.org/doi/10.1145/3555984
Jafargholi ZLarsen KSimkin MMarx D(2021)Optimal oblivious priority queuesProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458205(2366-2383)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458205
Gong LLiu ZLiu LXu JOgihara MYang T(2021)Space- and computationally-efficient set reconciliation via parity bitmap sketch (PBS)Proceedings of the VLDB Endowment10.14778/3436905.343690614:4(458-470)Online publication date: 22-Feb-2021
https://dl.acm.org/doi/10.14778/3436905.3436906
Apostolaki MSingla AVanbever L(2021)Performance-Driven Internet Path SelectionProceedings of the ACM SIGCOMM Symposium on SDN Research (SOSR)10.1145/3482898.3483366(41-53)Online publication date: 11-Oct-2021
https://dl.acm.org/doi/10.1145/3482898.3483366
Dotan MPignolet YSchmid STochner SZohar A(2021)Survey on Blockchain NetworkingACM Computing Surveys10.1145/345316154:5(1-34)Online publication date: 25-May-2021
https://dl.acm.org/doi/10.1145/3453161
Chan TChung KMaggs BShi EChan T(2019)Foundations of differentially oblivious algorithmsProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310585(2448-2467)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310585
Jacob RLarsen KNielsen JChan T(2019)Lower bounds for oblivious data structuresProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310584(2439-2447)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310584
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
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents