Document Open Access Logo

Exploring Differential Obliviousness

Authors Amos Beimel, Kobbi Nissim, Mohammad Zaheri

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.65.pdf
  • Filesize: 0.61 MB
  • 20 pages

Document Identifiers

Author Details

Amos Beimel
  • Dept. of Computer Science, Ben-Gurion University, Israel
Kobbi Nissim
  • Dept. of Computer Science, Georgetown University, Washington, D.C., USA
Mohammad Zaheri
  • Dept. of Computer Science, Georgetown University, Washington, D.C., USA

Funding

Work supported by NSF grant No. 1565387 TWC: Large: Collaborative: Computing Over Distributed Sensitive Data. A.B. is additionally supported by ISF grant no. 152/17, a grant from the Cyber Security Research Center at Ben-Gurion University, and ERC grant 742754 (project NTSC).

Cite As Get BibTex

Amos Beimel, Kobbi Nissim, and Mohammad Zaheri. Exploring Differential Obliviousness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 65:1-65:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.65

Abstract

In a recent paper, Chan et al. [SODA '19] proposed a relaxation of the notion of (full) memory obliviousness, which was introduced by Goldreich and Ostrovsky [J. ACM '96] and extensively researched by cryptographers. The new notion, differential obliviousness, requires that any two neighboring inputs exhibit similar memory access patterns, where the similarity requirement is that of differential privacy. Chan et al. demonstrated that differential obliviousness allows achieving improved efficiency for several algorithmic tasks, including sorting, merging of sorted lists, and range query data structures.
In this work, we continue the exploration of differential obliviousness, focusing on algorithms that do not necessarily examine all their input. This choice is motivated by the fact that the existence of logarithmic overhead ORAM protocols implies that differential obliviousness can yield at most a logarithmic improvement in efficiency for computations that need to examine all their input. In particular, we explore property testing, where we show that differential obliviousness yields an almost linear improvement in overhead in the dense graph model, and at most quadratic improvement in the bounded degree model. We also explore tasks where a non-oblivious algorithm would need to explore different portions of the input, where the latter would depend on the input itself, and where we show that such a behavior can be maintained under differential obliviousness, but not under full obliviousness. Our examples suggest that there would be benefits in further exploring which class of computational tasks are amenable to differential obliviousness.

Subject Classification

ACM Subject Classification
  • Security and privacy → Privacy-preserving protocols
Keywords
  • Differential Obliviousness
  • Differential Privacy
  • Oblivious RAM
  • Graph Property Testing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Eldar Fischer, Michael Krivelevich, and Mario Szegedy. Efficient Testing of Large Graphs. Combinatorica, 20(4):451-476, 2000. URL: https://doi.org/10.1007/s004930070001.
  2. Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, and Elaine Shi. OptORAMa: Optimal Oblivious RAM. IACR Cryptology ePrint Archive, 2018:892, 2018. URL: https://eprint.iacr.org/2018/892.
  3. Marina Blanton, Aaron Steele, and Mehrdad Aliasgari. Data-oblivious graph algorithms for secure computation and outsourcing. In Kefei Chen, Qi Xie, Weidong Qiu, Ninghui Li, and Wen-Guey Tzeng, editors, 8th ACM Symposium on Information, Computer and Communications Security, ASIA CCS '13, pages 207-218. ACM, 2013. URL: https://doi.org/10.1145/2484313.2484341.
  4. David Cash, Paul Grubbs, Jason Perry, and Thomas Ristenpart. Leakage-Abuse Attacks Against Searchable Encryption. In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, 2015, pages 668-679. ACM, 2015. Google Scholar
  5. T.-H. Hubert Chan, Kai-Min Chung, Bruce M. Maggs, and Elaine Shi. Foundations of Differentially Oblivious Algorithms. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 2448-2467. SIAM, 2019. Google Scholar
  6. Srinivas Devadas, Marten van Dijk, Christopher W. Fletcher, Ling Ren, Elaine Shi, and Daniel Wichs. Onion ORAM: A Constant Bandwidth Blowup Oblivious RAM. In Eyal Kushilevitz and Tal Malkin, editors, Theory of Cryptography - 13th International Conference, TCC 2016-A, volume 9563 of Lecture Notes in Computer Science, pages 145-174. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-49099-0_6.
  7. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, volume 3876 of Lecture Notes in Computer Science, pages 265-284. Springer, 2006. URL: https://doi.org/10.1007/11681878_14.
  8. David Eppstein, Michael T. Goodrich, and Roberto Tamassia. Privacy-preserving data-oblivious geometric algorithms for geographic data. In Divyakant Agrawal, Pusheng Zhang, Amr El Abbadi, and Mohamed F. Mokbel, editors, 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, ACM-GIS 2010, pages 13-22. ACM, 2010. URL: https://doi.org/10.1145/1869790.1869796.
  9. Ronald Fagin, Amnon Lotem, and Moni Naor. Optimal Aggregation Algorithms for Middleware. In Peter Buneman, editor, Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 102-113. ACM, 2001. Google Scholar
  10. Oded Goldreich. Towards a Theory of Software Protection and Simulation by Oblivious RAMs. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 182-194. ACM, 1987. URL: https://doi.org/10.1145/28395.28416.
  11. Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781108135252.
  12. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property Testing and its Connection to Learning and Approximation. J. ACM, 45(4):653-750, 1998. URL: https://doi.org/10.1145/285055.285060.
  13. Oded Goldreich and Rafail Ostrovsky. Software Protection and Simulation on Oblivious RAMs. J. ACM, 43(3):431-473, 1996. URL: https://doi.org/10.1145/233551.233553.
  14. Oded Goldreich and Dana Ron. Property Testing in Bounded Degree Graphs. Algorithmica, 32(2):302-343, 2002. Google Scholar
  15. M. T. Goodrich, O. Ohrimenko, and R. Tamassia. Data-oblivious graph drawing model and algorithms. CoRR, 2012. Google Scholar
  16. Michael T. Goodrich. Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, pages 684-693. ACM, 2014. URL: https://doi.org/10.1145/2591796.2591830.
  17. Michael T. Goodrich and Joseph A. Simons. Data-Oblivious Graph Algorithms in Outsourced External Memory. In Zhao Zhang, Lidong Wu, Wen Xu, and Ding-Zhu Du, editors, Combinatorial Optimization and Applications - 8th International Conference, COCOA 2014, volume 8881 of Lecture Notes in Computer Science, pages 241-257. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-12691-3_19.
  18. Moritz Hardt and Guy N. Rothblum. A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, pages 61-70. IEEE Computer Society, 2010. Google Scholar
  19. Xi He, Ashwin Machanavajjhala, Cheryl Flynn, and Divesh Srivastava. Composing Differential Privacy and Secure Computation: A Case Study on Scaling Private Record Linkage. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS '17, pages 1389-1406. ACM, 2017. URL: https://doi.org/10.1145/3133956.3134030.
  20. Mohammad Saiful Islam, Mehmet Kuzu, and Murat Kantarcioglu. Inference attack against encrypted range queries on outsourced databases. In Elisa Bertino, Ravi S. Sandhu, and Jaehong Park, editors, Fourth ACM Conference on Data and Application Security and Privacy, CODASPY'14, pages 235-246. ACM, 2014. URL: https://doi.org/10.1145/2557547.2557561.
  21. Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O'Neill. Generic Attacks on Secure Outsourced Databases. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 1329-1340. ACM, 2016. URL: https://doi.org/10.1145/2976749.2978386.
  22. Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O'Neill. Accessing Data while Preserving Privacy. CoRR, abs/1706.01552, 2017. URL: http://arxiv.org/abs/1706.01552.
  23. Marie-Sarah Lacharité, Brice Minaud, and Kenneth G. Paterson. Improved Reconstruction Attacks on Encrypted Data Using Range Query Leakage. In 2018 IEEE Symposium on Security and Privacy, SP 2018, pages 297-314. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/SP.2018.00002.
  24. Kasper Green Larsen and Jesper Buus Nielsen. Yes, There is an Oblivious RAM Lower Bound! In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, volume 10992 of Lecture Notes in Computer Science, pages 523-542. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-96881-0_18.
  25. Wei-Kai Lin, Elaine Shi, and Tiancheng Xie. Can We Overcome the n log n Barrier for Oblivious Sorting? In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 2419-2438. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.148.
  26. Chang Liu, Xiao Shaun Wang, Kartik Nayak, Yan Huang, and Elaine Shi. ObliVM: A Programming Framework for Secure Computation. In 2015 IEEE Symposium on Security and Privacy, SP 2015, pages 359-376. IEEE Computer Society, 2015. Google Scholar
  27. Sahar Mazloom and S. Dov Gordon. Secure Computation with Differentially Private Access Patterns. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, October 15-19, 2018, pages 490-507. ACM, 2018. URL: https://doi.org/10.1145/3243734.3243851.
  28. Tarik Moataz, Travis Mayberry, and Erik-Oliver Blass. Constant Communication ORAM with Small Blocksize. In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 862-873. ACM, 2015. Google Scholar
  29. Muhammad Naveed, Seny Kamara, and Charles V. Wright. Inference Attacks on Property-Preserving Encrypted Databases. In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security 2015, pages 644-655. ACM, 2015. Google Scholar
  30. Rafail Ostrovsky. Efficient Computation on Oblivious RAMs. In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 514-523. ACM, 1990. URL: https://doi.org/10.1145/100216.100289.
  31. Giuseppe Persiano and Kevin Yeo. Lower Bounds for Differentially Private RAMs. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2019, Part I, volume 11476 of Lecture Notes in Computer Science, pages 404-434. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-17653-2_14.
  32. Sofya Raskhodnikova and Adam D. Smith. A Note on Adaptivity in Testing Properties of Bounded Degree Graphs. Electronic Colloquium on Computational Complexity (ECCC), 13(089), 2006. URL: http://eccc.hpi-web.de/eccc-reports/2006/TR06-089/index.html.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact