Document Open Access Logo

Differentially Oblivious Turing Machines

Authors Ilan Komargodski , Elaine Shi

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.68.pdf
  • Filesize: 0.55 MB
  • 19 pages

Document Identifiers

Author Details

Ilan Komargodski
  • The Hebrew University in Jerusalem, Israel
  • NTT Research, Palo Alto, CA, USA
Elaine Shi
  • Cornell University, Ithaca, NY, USA
  • Carnegie Mellon University, Pittsburgh, PA, USA

Funding

  • Komargodski, Ilan: Supported by an Alon Young Faculty Fellowship and by an ISF grant (No. 1774/20).
  • Shi, Elaine: Supported by an NSF grant (award number CNS-1601879), an Office of Naval Research Young Investigator Program Award, and a Packard Fellowship.

Acknowledgements

We thank the reviewers of ITCS 2021 for their feedback. We thank Hubert Chan and Kai-Min Chung for useful discussions.

Cite AsGet BibTex

Ilan Komargodski and Elaine Shi. Differentially Oblivious Turing Machines. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 68:1-68:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITCS.2021.68

Abstract

Oblivious RAM (ORAM) is a machinery that protects any RAM from leaking information about its secret input by observing only the access pattern. It is known that every ORAM must incur a logarithmic overhead compared to the non-oblivious RAM. In fact, even the seemingly weaker notion of differential obliviousness, which intuitively "protects" a single access by guaranteeing that the observed access pattern for every two "neighboring" logical access sequences satisfy (ε,δ)-differential privacy, is subject to a logarithmic lower bound. In this work, we show that any Turing machine computation can be generically compiled into a differentially oblivious one with only doubly logarithmic overhead. More precisely, given a Turing machine that makes N transitions, the compiled Turing machine makes O(N ⋅ log log N) transitions in total and the physical head movements sequence satisfies (ε,δ)-differential privacy (for a constant ε and a negligible δ). We additionally show that Ω(log log N) overhead is necessary in a natural range of parameters (and in the balls and bins model). As a corollary, we show that there exist natural data structures such as stack and queues (supporting online operations) on N elements for which there is a differentially oblivious implementation on a Turing machine incurring amortized O(log log N) overhead per operation, while it is known that any oblivious implementation must consume Ω(log N) operations unconditionally even on a RAM. Therefore, we obtain the first unconditional separation between obliviousness and differential obliviousness in the most natural setting of parameters where ε is a constant and δ is negligible. Before this work, such a separation was only known in the balls and bins model. Note that the lower bound applies in the RAM model while our upper bound is in the Turing machine model, making our separation stronger.

Subject Classification

ACM Subject Classification
  • Theory of computation → Turing machines
Keywords
  • Differential privacy
  • Turing machines
  • obliviousness

Metrics

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

References

  1. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. Google Scholar
  2. Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, Enoch Peserico, and Elaine Shi. OptORAMa: Optimal oblivious RAM. In Advances in Cryptology - EUROCRYPT, pages 403-432, 2020. Google Scholar
  3. Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, and Elaine Shi. Oblivious parallel tight compaction. In 1st Conference on Information-Theoretic Cryptography, ITC, pages 11:1-11:23, 2020. Google Scholar
  4. Amos Beimel, Kobbi Nissim, and Mohammad Zaheri. Exploring differential obliviousness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 65:1-65:20, 2019. Google Scholar
  5. Vincent Bindschaedler, Muhammad Naveed, Xiaorui Pan, XiaoFeng Wang, and Yan Huang. Practicing oblivious access on cloud storage: the gap, the fallacy, and the new way forward. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 837-849. ACM, 2015. Google Scholar
  6. Elette Boyle and Moni Naor. Is there an oblivious RAM lower bound? In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, ITCS, pages 357-368, 2016. Google Scholar
  7. T.-H. Hubert Chan, Kai-Min Chung, Bruce M. Maggs, and Elaine Shi. Foundations of differentially oblivious algorithms. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2448-2467. SIAM, 2019. Google Scholar
  8. T.-H. Hubert Chan, Yue Guo, Wei-Kai Lin, and Elaine Shi. Oblivious hashing revisited, and applications to asymptotically efficient ORAM and OPRAM. In Advances in Cryptology - ASIACRYPT, pages 660-690, 2017. Google Scholar
  9. T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. In Automata, Languages and Programming, 37th International Colloquium, ICALP, pages 405-417, 2010. Google Scholar
  10. T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur., 14(3):26:1-26:24, 2011. Google Scholar
  11. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC, pages 265-284, 2006. Google Scholar
  12. Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC, pages 715-724. ACM, 2010. Google Scholar
  13. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-407, 2014. Google Scholar
  14. Christopher W Fletcher, Marten van Dijk, and Srinivas Devadas. A secure processor architecture for encrypted computation on untrusted programs. In Proceedings of the seventh ACM workshop on Scalable trusted computing, pages 3-8. ACM, 2012. Google Scholar
  15. Christopher W. Fletcher, Ling Ren, Albert Kwon, Marten van Dijk, and Srinivas Devadas. Freecursive ORAM: [nearly] free recursion and integrity verification for position-based oblivious RAM. In Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS, pages 103-116. ACM, 2015. Google Scholar
  16. Craig Gentry, Shai Halevi, Charanjit Jutla, and Mariana Raykova. Private database access with he-over-oram architecture. In International Conference on Applied Cryptography and Network Security, pages 172-191. Springer, 2015. Google Scholar
  17. Oded Goldreich. Towards a theory of software protection and simulation by oblivious rams. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, STOC, pages 182-194, 1987. Google Scholar
  18. Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious RAMs. J. ACM, 1996. Google Scholar
  19. Michael T. Goodrich and Michael Mitzenmacher. Privacy-preserving access of outsourced data via oblivious RAM simulation. In Automata, Languages and Programming - 38th International Colloquium, ICALP, pages 576-587, 2011. Google Scholar
  20. Juris Hartmanis and Richard E Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117:285-306, 1965. Google Scholar
  21. F. C. Hennie. One-tape, off-line turing machine computations. Inf. Control., 8(6):553-578, 1965. Google Scholar
  22. F. C. Hennie and Richard Edwin Stearns. Two-tape simulation of multitape turing machines. J. ACM, 13(4):533-546, 1966. Google Scholar
  23. Riko Jacob, Kasper Green Larsen, and Jesper Buus Nielsen. Lower bounds for oblivious data structures. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2439-2447. SIAM, 2019. Google Scholar
  24. 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, pages 143-156, 2012. Google Scholar
  25. Kasper Green Larsen and Jesper Buus Nielsen. Yes, there is an oblivious RAM lower bound! In Advances in Cryptology - CRYPTO, pages 523-542, 2018. Google Scholar
  26. Wei-Kai Lin, Elaine Shi, and Tiancheng Xie. Can we overcome the n log n barrier for oblivious sorting? In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2419-2438, 2019. Google Scholar
  27. Chang Liu, Xiao Shaun Wang, Kartik Nayak, Yan Huang, and Elaine Shi. ObliVM: A programming framework for secure computation. In IEEE Symposium on Security and Privacy, 2015. Google Scholar
  28. Steve Lu and Rafail Ostrovsky. Distributed oblivious RAM for secure two-party computation. In Theory of Cryptography, pages 377-396. Springer, 2013. Google Scholar
  29. Martin Maas, Eric Love, Emil Stefanov, Mohit Tiwari, Elaine Shi, Krste Asanovic, John Kubiatowicz, and Dawn Song. PHANTOM: practical oblivious computation in a secure processor. In 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS, pages 311-324, 2013. Google Scholar
  30. Rafail Ostrovsky. Efficient computation on oblivious rams. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 514-523, 1990. Google Scholar
  31. Rafail Ostrovsky and Victor Shoup. Private information storage (extended abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, STOC, pages 294-303, 1997. Google Scholar
  32. Sarvar Patel, Giuseppe Persiano, Mariana Raykova, and Kevin Yeo. Panorama: Oblivious RAM with logarithmic overhead. In FOCS, 2018. Google Scholar
  33. Sarvar Patel, Giuseppe Persiano, and Kevin Yeo. What storage access privacy is achievable with small overhead? In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS, pages 182-199, 2019. Google Scholar
  34. Giuseppe Persiano and Kevin Yeo. Lower bounds for differentially private rams. In Advances in Cryptology - EUROCRYPT 2019, pages 404-434, 2019. Google Scholar
  35. Nicholas Pippenger and Michael J. Fischer. Relations among complexity measures. J. ACM, 26(2):361-381, 1979. Google Scholar
  36. Ling Ren, Xiangyao Yu, Christopher W. Fletcher, Marten van Dijk, and Srinivas Devadas. Design space exploration and optimization of path oblivious RAM in secure processors. In The 40th Annual International Symposium on Computer Architecture, ISCA, pages 571-582. ACM, 2013. Google Scholar
  37. Elaine Shi, T.-H. Hubert Chan, Emil Stefanov, and Mingfei Li. Oblivious RAM with O((log N)³) worst-case cost. In Advances in Cryptology - ASIACRYPT, pages 197-214, 2011. Google Scholar
  38. Emil Stefanov and Elaine Shi. Oblivistore: High performance oblivious cloud storage. In 2013 IEEE Symposium on Security and Privacy, pages 253-267. IEEE, 2013. Google Scholar
  39. Emil Stefanov, Elaine Shi, and Dawn Xiaodong Song. Towards practical oblivious RAM. In 19th Annual Network and Distributed System Security Symposium, NDSS, 2012. Google Scholar
  40. Emil Stefanov, Marten van Dijk, Elaine Shi, Christopher W. Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. Path ORAM: an extremely simple oblivious RAM protocol. In ACM SIGSAC Conference on Computer and Communications Security, CCS, pages 299-310, 2013. Google Scholar
  41. Xiao Wang, T.-H. Hubert Chan, and Elaine Shi. Circuit ORAM: on tightness of the goldreich-ostrovsky lower bound. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS, pages 850-861, 2015. Google Scholar
  42. Xiao Shaun Wang, Yan Huang, T.-H. Hubert Chan, Abhi Shelat, and Elaine Shi. SCORAM: oblivious RAM for secure computation. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pages 191-202, 2014. Google Scholar
  43. Xiao Shaun Wang, Kartik Nayak, Chang Liu, T.-H. Hubert Chan, Elaine Shi, Emil Stefanov, and Yan Huang. Oblivious data structures. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS, pages 215-226, 2014. Google Scholar
  44. Peter Williams, Radu Sion, and Alin Tomescu. Privatefs: A parallel oblivious file system. In ACM Conference on Computer and Communications Security (CCS), 2012. Google Scholar
  45. Samee Zahur, Xiao Shaun Wang, Mariana Raykova, Adria Gascón, Jack Doerner, David Evans, and Jonathan Katz. Revisiting square-root ORAM: efficient random access in multi-party computation. In IEEE Symposium on Security and Privacy, S& P, pages 218-234, 2016. Google Scholar
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 Imprint Privacy Contact