Document Open Access Logo

Succinct Oblivious RAM

Authors Taku Onodera, Tetsuo Shibuya

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.52.pdf
  • Filesize: 0.56 MB
  • 16 pages

Document Identifiers

Author Details

Taku Onodera
Tetsuo Shibuya

Cite As Get BibTex

Taku Onodera and Tetsuo Shibuya. Succinct Oblivious RAM. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.52

Abstract

As online storage services become increasingly common, it is important that users' private information is protected from database access pattern analyses. Oblivious RAM (ORAM) is a cryptographic primitive that enables users to perform arbitrary database accesses without revealing any information about the access pattern to the server. Previous ORAM studies focused mostly on reducing the access overhead. Consequently, the access overhead of the state-of-the-art ORAM constructions are almost at practical levels in certain application scenarios such as secure processors. However, we assume that the server space usage could become a new important issue in the coming big-data era. To enable large-scale computation in security-aware settings, it is necessary to rethink the ORAM server space cost using big-data standards.
In this paper, we introduce "succinctness" as a theoretically tractable and practically relevant criterion of the ORAM server space efficiency in the big-data era. We, then, propose two succinct ORAM constructions that also exhibit state-of-the-art performance in terms of the bandwidth blowup and the user space. We also give non-asymptotic analyses and simulation results which indicate that the proposed ORAM constructions are practically effective.

Subject Classification

Keywords
  • Oblivious RAM
  • Succinct data structure
  • Balls-into-bins

Metrics

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

References

  1. Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. Balanced allocations. SIAM J. Comput., 29(1):180-200, 1999. URL: http://dx.doi.org/10.1137/S0097539795288490.
  2. David Benoit, Erik D. Demaine, J. Ian Munro, Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. Representing trees of higher degree. Algorithmica, 43(4):275-292, 2005. URL: http://dx.doi.org/10.1007/s00453-004-1146-6.
  3. Petra Berenbrink, Artur Czumaj, Angelika Steger, and Berthold Vöcking. Balanced allocations: the heavily loaded case. In F. Frances Yao and Eugene M. Luks, editors, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 745-754. ACM, 2000. URL: http://dx.doi.org/10.1145/335305.335411.
  4. 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 Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12-6, 2015, pages 837-849. ACM, 2015. URL: http://dx.doi.org/10.1145/2810103.2813649.
  5. Kai-Min Chung, Zhenming Liu, and Rafael Pass. Statistically-secure ORAM with õ(log^2 n) overhead. In Palash Sarkar and Tetsu Iwata, editors, Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014, Proceedings, Part II, volume 8874 of Lecture Notes in Computer Science, pages 62-81. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-45608-8_4.
  6. David R. Clark and J. Ian Munro. Efficient suffix trees on secondary storage. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '96, pages 383-391, Philadelphia, PA, USA, 1996. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=313852.314087.
  7. 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, Tel Aviv, Israel, January 10-13, 2016, Proceedings, Part II, volume 9563 of Lecture Notes in Computer Science, pages 145-174. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-662-49099-0_6.
  8. Paolo Ferragina, Fabrizio Luccio, Giovanni Manzini, and S. Muthukrishnan. Structuring labeled trees for optimal succinctness, and beyond. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pages 184-196. IEEE Computer Society, 2005. URL: http://dx.doi.org/10.1109/SFCS.2005.69.
  9. Paolo Ferragina and Giovanni Manzini. Indexing compressed text. J. ACM, 52(4):552-581, 2005. URL: http://dx.doi.org/10.1145/1082036.1082039.
  10. Paolo Ferragina, Giovanni Manzini, Veli Mäkinen, and Gonzalo Navarro. Compressed representations of sequences and full-text indexes. ACM Trans. Algorithms, 3(2):20, 2007. URL: http://dx.doi.org/10.1145/1240233.1240243.
  11. Christopher W. Fletcher, Marten van Dijk, and Srinivas Devadas. A secure processor architecture for encrypted computation on untrusted programs. In Proceedings of the 7th ACM Workshop on Scalable Trusted Computing, STC '12, pages 3-8, New York, NY, USA, 2012. ACM. URL: http://dx.doi.org/10.1145/2382536.2382540.
  12. 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 Özcan Özturk, Kemal Ebcioglu, and Sandhya Dwarkadas, editors, Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '15, Istanbul, Turkey, March 14-18, 2015, pages 103-116. ACM, 2015. URL: http://dx.doi.org/10.1145/2694344.2694353.
  13. Craig Gentry, Kenny A. Goldman, Shai Halevi, Charanjit S. Jutla, Mariana Raykova, and Daniel Wichs. Optimizing ORAM and using it efficiently for secure computation. In Emiliano De Cristofaro and Matthew K. Wright, editors, Privacy Enhancing Technologies - 13th International Symposium, PETS 2013, Bloomington, IN, USA, July 10-12, 2013. Proceedings, volume 7981 of Lecture Notes in Computer Science, pages 1-18. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39077-7_1.
  14. 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, 1987, New York, New York, USA, pages 182-194. ACM, 1987. URL: http://dx.doi.org/10.1145/28395.28416.
  15. Alexander Golynski, J. Ian Munro, and S. Srinivasa Rao. Rank/select operations on large alphabets: A tool for text indexing. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, SODA '06, pages 368-373, Philadelphia, PA, USA, 2006. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1109557.1109599.
  16. Michael T. Goodrich and Michael Mitzenmacher. Privacy-preserving access of outsourced data via oblivious ram simulation. In Proceedings of the 38th International Conference on Automata, Languages and Programming - Volume Part II, ICALP'11, pages 576-587, Berlin, Heidelberg, 2011. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=2027223.2027282.
  17. Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter. High-order entropy-compressed text indexes. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '03, pages 841-850, Philadelphia, PA, USA, 2003. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=644108.644250.
  18. Wing-Kai Hon, Rahul Shah, Sharma V. Thankachan, and Jeffrey Scott Vitter. Space-efficient frameworks for top-k string retrieval. J. ACM, 61(2):9:1-9:36, 2014. URL: http://dx.doi.org/10.1145/2590774.
  19. Guy Jacobson. Space-efficient static trees and graphs. In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 549-554. IEEE Computer Society, 1989. URL: http://dx.doi.org/10.1109/SFCS.1989.63533.
  20. Guy Joseph Jacobson. Succinct Static Data Structures. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, USA, 1988. Google Scholar
  21. Jesper Jansson, Kunihiko Sadakane, and Wing-Kin Sung. Ultra-succinct representation of ordered trees. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, pages 575-584, Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1283383.1283445.
  22. 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 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, pages 143-156. SIAM, 2012. URL: http://dx.doi.org/10.1137/1.9781611973099.13.
  23. 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 Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS'13, Berlin, Germany, November 4-8, 2013, pages 311-324. ACM, 2013. URL: http://dx.doi.org/10.1145/2508859.2516692.
  24. Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press, New York, NY, USA, 2nd edition, 2017. Google Scholar
  25. J. Ian Munro and Venkatesh Raman. Succinct representation of balanced parentheses and static trees. SIAM J. Comput., 31(3):762-776, 2001. URL: http://dx.doi.org/10.1137/S0097539799364092.
  26. J. Ian Munro, Venkatesh Raman, and S. Srinivasa Rao. Space efficient suffix trees. J. Algorithms, 39(2):205-222, 2001. URL: http://dx.doi.org/10.1006/jagm.2000.1151.
  27. Gonzalo Navarro and Yakov Nekrich. Optimal dynamic sequence representations. SIAM J. Comput., 43(5):1781-1806, 2014. URL: http://dx.doi.org/10.1137/130908245.
  28. Gonzalo Navarro and Kunihiko Sadakane. Fully functional static and dynamic succinct trees. ACM Trans. Algorithms, 10(3):16:1-16:39, 2014. URL: http://dx.doi.org/10.1145/2601073.
  29. Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. J. Algorithms, 51(2):122-144, 2004. URL: http://dx.doi.org/10.1016/j.jalgor.2003.12.002.
  30. Benny Pinkas and Tzachy Reinman. Oblivious ram revisited. In Proceedings of the 30th Annual Conference on Advances in Cryptology, CRYPTO'10, pages 502-519, Berlin, Heidelberg, 2010. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=1881412.1881447.
  31. Rajeev Raman and S. Srinivasa Rao. Succinct dynamic dictionaries and trees. In Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger, editors, Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings, volume 2719 of Lecture Notes in Computer Science, pages 357-368. Springer, 2003. URL: http://dx.doi.org/10.1007/3-540-45061-0_30.
  32. Ling Ren, Christopher Fletcher, Albert Kwon, Emil Stefanov, Elaine Shi, Marten van Dijk, and Srinivas Devadas. Constants count: Practical improvements to oblivious ram. In 24th USENIX Security Symposium, pages 415-430, Washington, D.C., 2015. USENIX Association. URL: https://www.usenix.org/conference/usenixsecurity15/technical-sessions/presentation/ren-ling.
  33. 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. SIGARCH Comput. Archit. News, 41(3):571-582, 2013. URL: http://dx.doi.org/10.1145/2508148.2485971.
  34. Kunihiko Sadakane. Succinct representations of Lcp information and improvements in the compressed suffix arrays. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '02, pages 225-232, Philadelphia, PA, USA, 2002. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=545381.545410.
  35. Kunihiko Sadakane and Roberto Grossi. Squeezing succinct data structures into entropy bounds. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, SODA '06, pages 1230-1239, Philadelphia, PA, USA, 2006. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1109557.1109693.
  36. Elaine Shi, T.-H. Hubert Chan, Emil Stefanov, and Mingfei Li. Oblivious RAM with o((logn)3) worst-case cost. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology - ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings, volume 7073 of Lecture Notes in Computer Science, pages 197-214. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-25385-0_11.
  37. Emil Stefanov, Elaine Shi, and Dawn Xiaodong Song. Towards practical oblivious ram. In 19th Annual Network and Distributed System Security Symposium, 2012. URL: http://www.internetsociety.org/towards-practical-oblivious-ram.
  38. 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 Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS'13, Berlin, Germany, November 4-8, 2013, pages 299-310. ACM, 2013. URL: http://dx.doi.org/10.1145/2508859.2516660.
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