research-article

Oblivious Data Structures

Authors:

Xiao Shaun Wang,

T-H. Hubert Chan,

Yan HuangAuthors Info & Claims

CCS '14: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security

Pages 215 - 226

https://doi.org/10.1145/2660267.2660314

Published: 03 November 2014 Publication History

Abstract

We design novel, asymptotically more efficient data structures and algorithms for programs whose data access patterns exhibit some degree of predictability. To this end, we propose two novel techniques, a pointer-based technique and a locality-based technique. We show that these two techniques are powerful building blocks in making data structures and algorithms oblivious. Specifically, we apply these techniques to a broad range of commonly used data structures, including maps, sets, priority-queues, stacks, deques; and algorithms, including a memory allocator algorithm, max-flow on graphs with low doubling dimension, and shortest-path distance queries on weighted planar graphs. Our oblivious counterparts of the above outperform the best known ORAM scheme both asymptotically and in practice.

References

[1]

Hardware AES showdown - via padlock vs intel AES-NI vs AMD hexacore. http://grantmcwilliams.com/tech/technology/item/532-hardware-aes-showdown-via-padlock-vs-intel-aes-ni-vsamd-hexacore.

[2]

Askarov, A., Zhang, D., and Myers, A. C. Predictive black-box mitigation of timing channels. In CCS (2010), pp. 297--307.

Digital Library

[3]

Assouad, P. Plongements lipschitziens dans Rn. Bull. Soc. Math. France 111, 4 (1983), 429--448.

[4]

Bar-Yossef, Z., and Gurevich, M. Random sampling from a search engine's index. J. ACM (2008).

Digital Library

[5]

Bellare, M., Hoang, V. T., Keelveedhi, S., and Rogaway, P. Efficient garbling from a fixed-key blockcipher. In S & P (2013).

Digital Library

[6]

Berg, M. d., Cheong, O., Kreveld, M. v., and Overmars, M. Computational Geometry: Algorithms and Applications. 2008.

Digital Library

[7]

Blanton, M., Steele, A., and Aliasgari, M. Data-oblivious graph algorithms for secure computation and outsourcing. In ASIACCS (2013).

Digital Library

[8]

Blelloch, G. E., and Golovin, D. Strongly history-independent hashing with applications. In FOCS (2007).

Digital Library

[9]

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

[10]

Clarkson, K. L. Nearest neighbor queries in metric spaces. Discrete Comput. Geom. 22, 1 (1999), 63--93.

[11]

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

Digital Library

[12]

Eppstein, D., Goodrich, M. T., and Tamassia, R. Privacy-preserving data-oblivious geometric algorithms for geographic data. In GIS (2010).

Digital Library

[13]

Fletcher, C. W., Dijk, M. v., and Devadas, S. A secure processor architecture for encrypted computation on untrusted programs. In STC (2012).

Digital Library

[14]

Ford, Jr., L. R., and Fulkerson, D. R. Maximal ow through a network. In Canadian Journal of Mathematics (1956).

[15]

Gentry, C., Goldman, K. A., Halevi, S., Jutla, C. S., Raykova, M., and Wichs, D. Optimizing ORAM and using it effciently for secure computation. In PETS (2013).

[16]

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

Digital Library

[17]

Goldreich, O., and Ostrovsky, R. Software protection and simulation on oblivious RAMs. J. ACM (1996).

Digital Library

[18]

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

Digital Library

[19]

Goodrich, M. T., Mitzenmacher, M., Ohrimenko, O., and Tamassia, R. Oblivious RAM simulation with effcient worst-case access overhead. In CCSW (2011).

Digital Library

[20]

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

Digital Library

[21]

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

[22]

Goodrich, M. T., Ohrimenko, O., and Tamassia, R. Data-oblivious graph drawing model and algorithms. CoRR abs/1209.0756 (2012).

[23]

Gordon, S. D., Katz, J., Kolesnikov, V., Krell, F., Malkin, T., Raykova, M., and Vahlis, Y. Secure two-party computation in sublinear (amortized) time. In CCS (2012).

Digital Library

[24]

Gupta, A., Krauthgamer, R., and Lee, J. R. Bounded geometries, fractals, and low-distortion embeddings. In FOCS (2003), pp. 534--543.

Digital Library

[25]

Huang, Y., Evans, D., Katz, J., and Malka, L. Faster Secure Two-Party Computation Using Garbled Circuits. In USENIX Security Symposium (2011).

Digital Library

[26]

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

[27]

Keller, M., and Scholl, P. Effcient, oblivious data structures for mpc. Cryptology ePrint Archive, Report 2014/137, 2014. http://eprint.iacr.org/.

[28]

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

[29]

Lipton, R. J., and Tarjan, R. E. A Separator Theorem for Planar Graphs. SIAM Journal on Applied Mathematics (1979).

[30]

Liu, C., Hicks, M., and Shi, E. Memory trace oblivious program execution. In CSF (2013).

Digital Library

[31]

Liu, C., Huang, Y., Shi, E., Katz, J., and Hicks, M. Automating effcient RAM-model secure computation. In IEEE S & P (May 2014).

Digital Library

[32]

Lu, S., and Ostrovsky, R. Distributed oblivious RAM for secure two-party computation. In TCC (2013).

Digital Library

[33]

Lu, S., and Ostrovsky, R. How to garble ram programs. In EUROCRYPT (2013).

[34]

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

[35]

Micciancio, D. Oblivious data structures: applications to cryptography. In STOC (1997), ACM.

Digital Library

[36]

Mitchell, J. C., and Zimmerman, J. Data-Oblivious Data Structures. In STACS (2014).

[37]

Nikolaenko, V., Ioannidis, S., Weinsberg, U., Joye, M., Taft, N., and Boneh, D. Privacy-preserving matrix factorization. In CCS (2013).

Digital Library

[38]

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

Digital Library

[39]

Pippenger, N., and Fischer, M. J. Relations among complexity measures. In J. ACM (1979).

Digital Library

[40]

Ren, L., Fletcher, C., Yu, X., Kwon, A., van Dijk, M., and Devadas, S. Unified oblivious-ram: Improving recursive oram with locality and pseudorandomness. Cryptology ePrint Archive, Report 2014/205, 2014. http://eprint.iacr.org/.

[41]

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

Digital Library

[42]

Stefanov, E., and Shi, E. Oblivistore: High performance oblivious cloud storage. In IEEE Symposium on Security and Privacy (S & P) (2013).

Digital Library

[43]

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

[44]

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

[45]

Suh, G. E., Clarke, D., Gassend, B., van Dijk, M., and Devadas, S. Aegis: architecture for tamper-evident and tamper-resistant processing. In ICS (2003).

Digital Library

[46]

Thekkath, D. L. C., Mitchell, M., Lincoln, P., Boneh, D., Mitchell, J., and Horowitz, M. Architectural support for copy and tamper resistant software. SIGOPS Oper. Syst. Rev. (2000).

Digital Library

[47]

Toft, T. Secure data structures based on multi-party computation. In PODC (2011), pp. 291--292.

Digital Library

[48]

Wang, X. S., Nayak, K., Liu, C., Chan, T.-H. H., Shi, E., Stefanov, E., and Huang, Y. Oblivious data structures. Cryptology ePrint Archive, Report 2014/185, 2014. http://eprint.iacr.org/.

Digital Library

[49]

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

[50]

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

Digital Library

[51]

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

Digital Library

[52]

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

Digital Library

[53]

Zahur, S., and Evans, D. Circuit structures for improving effciency of security and privacy tools. In S&P (2013).

Digital Library

[54]

Zhang, D., Askarov, A., and Myers, A. C. Predictive mitigation of timing channels in interactive systems. In CCS (2011), pp. 563--574.

Digital Library

[55]

Zhang, D., Askarov, A., and Myers, A. C. Language-based control and mitigation of timing channels. In PLDI (2012), pp. 99--110.

Digital Library

[56]

Zhuang, X., Zhang, T., and Pande, S. Hide: An infrastructure for effciently protecting information leakage on the address bus. SIGARCH Comput. Archit. News 32, 5 (Oct. 2004), 72--84.

Digital Library

Cited By

Ehrmanntraut VMeyer UAyday EVaidya J(2024)Privacy-Preserving Breadth-First-Search and Maximal FlowProceedings of the 23rd Workshop on Privacy in the Electronic Society10.1145/3689943.3695041(73-97)Online publication date: 20-Nov-2024
https://dl.acm.org/doi/10.1145/3689943.3695041
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
Attrapadung NIsayama KSadakane KTozawa KLuo BLiao XXu JKirda ELie D(2024)Secure Parallel Computation with Oblivious State TransitionsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690315(3008-3022)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690315
Show More Cited By

Index Terms

Oblivious Data Structures
1. Hardware
  1. Communication hardware, interfaces and storage
2. Networks

Recommendations

Cache-oblivious data structures for massive data sets
Faster randomized consensus with an oblivious adversary

Two new algorithms are given for randomized consensus in a shared-memory model with an oblivious adversary. Each is based on a new construction of a conciliator, an object that guarantees termination and validity, but that only guarantees agreement with ...
Efficient Oblivious Permutation via the Waksman Network
ASIA CCS '22: Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security

Memory accesses to data stored on an untrusted server are known to leak information, even if the data is encrypted. The oblivious permutation (OP) is a key primitive for algorithms and protocols that are designed to hide these client accesses to the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '14: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security

November 2014

1592 pages

ISBN:9781450329576

DOI:10.1145/2660267

General Chair:
Gail-Joon Ahn
Arizona State University, USA
,
Program Chairs:
Moti Yung
Google -- Columbia University, USA
,
Ninghui Li
Purdue University, USA

Copyright © 2014 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: 03 November 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

CCS'14

Sponsor:

SIGSAC

CCS'14: 2014 ACM SIGSAC Conference on Computer and Communications Security

November 3 - 7, 2014

Arizona, Scottsdale, USA

Acceptance Rates

CCS '14 Paper Acceptance Rate 114 of 585 submissions, 19%;

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

128
Total Citations
View Citations
1,411
Total Downloads

Downloads (Last 12 months)150
Downloads (Last 6 weeks)37

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ehrmanntraut VMeyer UAyday EVaidya J(2024)Privacy-Preserving Breadth-First-Search and Maximal FlowProceedings of the 23rd Workshop on Privacy in the Electronic Society10.1145/3689943.3695041(73-97)Online publication date: 20-Nov-2024
https://dl.acm.org/doi/10.1145/3689943.3695041
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
Attrapadung NIsayama KSadakane KTozawa KLuo BLiao XXu JKirda ELie D(2024)Secure Parallel Computation with Oblivious State TransitionsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690315(3008-3022)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690315
Song XZheng YBai JDong CLiu ZChang EQuek TGao DZhou JCardenas A(2024)DISCO: Dynamic Searchable Encryption with Constant StateProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3637674(1724-1738)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3637674
Chang ZXie DWang SLi FShen Y(2024)Towards Practical Oblivious Join ProcessingIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.331003836:4(1829-1842)Online publication date: Apr-2024
https://doi.org/10.1109/TKDE.2023.3310038
Zheng YXu PWang MXu WWang WChen TJin H(2024)Themis: Robust and Light-Client Dynamic Searchable Symmetric EncryptionIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.346397119(8802-8816)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3463971
Tiruye BBiernacki LAdem TMola PAustin T(2024)Octal: Efficient Automatic Data-Oblivious Program Transformations to Eliminate Side-Channel Leakage2024 IEEE Secure Development Conference (SecDev)10.1109/SecDev61143.2024.00018(129-139)Online publication date: 7-Oct-2024
https://doi.org/10.1109/SecDev61143.2024.00018
Wei SHarris AZhu YRamrakhyani PLin CTiwari M(2024)Tail Victims in Termination Timing Channel Defenses Beyond Cryptographic Kernels2024 International Symposium on Secure and Private Execution Environment Design (SEED)10.1109/SEED61283.2024.00012(11-22)Online publication date: 16-May-2024
https://doi.org/10.1109/SEED61283.2024.00012
Cao XLi YBogatov DLiu JRen K(2024)Secure and Practical Functional Dependency Discovery in Outsourced Databases2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00134(1645-1658)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00134
Gao BJia SDong JRen P(2024)XPORAM: A Practical Multi-client ORAM Against Malicious AdversariesInformation Security and Cryptology10.1007/978-981-97-0942-7_20(397-417)Online publication date: 26-Feb-2024
https://doi.org/10.1007/978-981-97-0942-7_20
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