Document Open Access Logo

Differentially Oblivious Database Joins: Overcoming the Worst-Case Curse of Fully Oblivious Algorithms

Authors Shumo Chu, Danyang Zhuo, Elaine Shi, T-H. Hubert Chan

PDF
Thumbnail PDF

File

LIPIcs.ITC.2021.19.pdf
  • Filesize: 0.83 MB
  • 24 pages

Document Identifiers

Author Details

Shumo Chu
  • University of California, Santa Barbara, CA, USA
Danyang Zhuo
  • Duke University, Durham, NC, USA
Elaine Shi
  • Carnegie Mellon University, Pittsburgh, PA, USA
T-H. Hubert Chan
  • The University of Hong Kong, Hong Kong

Funding

T-H. Hubert Chan is partially supported by the Hong Kong RGC under the grants 17200418 and 17201220. Elaine Shi is partially funded by NSF under award numbers 1601879 and 2128519, a faculty award from JP Morgan, an ONR YIP award, and a Packard Fellowship.

Acknowledgements

We gratefully acknowledge helpful discussions and insightful feedback with Zhao Song and Lianke Qin.

Cite AsGet BibTex

Shumo Chu, Danyang Zhuo, Elaine Shi, and T-H. Hubert Chan. Differentially Oblivious Database Joins: Overcoming the Worst-Case Curse of Fully Oblivious Algorithms. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITC.2021.19

Abstract

Numerous high-profile works have shown that access patterns to even encrypted databases can leak secret information and sometimes even lead to reconstruction of the entire database. To thwart access pattern leakage, the literature has focused on oblivious algorithms, where obliviousness requires that the access patterns leak nothing about the input data. In this paper, we consider the Join operator, an important database primitive that has been extensively studied and optimized. Unfortunately, any fully oblivious Join algorithm would require always padding the result to the worst-case length which is quadratic in the data size N. In comparison, an insecure baseline incurs only O(R + N) cost where R is the true result length, and in the common case in practice, R is relatively short. As a typical example, when R = O(N), any fully oblivious algorithm must inherently incur a prohibitive, N-fold slowdown relative to the insecure baseline. Indeed, the (non-private) database and algorithms literature invariably focuses on studying the instance-specific rather than worst-case performance of database algorithms. Unfortunately, the stringent notion of full obliviousness precludes the design of efficient algorithms with non-trivial instance-specific performance. To overcome this worst-case performance barrier of full obliviousness and enable algorithms with good instance-specific performance, we consider a relaxed notion of access pattern privacy called (ε, δ)-differential obliviousness (DO), originally proposed in the seminal work of Chan et al. (SODA'19). Rather than insisting that the access patterns leak no information whatsoever, the relaxed DO notion requires that the access patterns satisfy (ε, δ)-differential privacy. We show that by adopting the relaxed DO notion, we can obtain efficient database Join mechanisms whose instance-specific performance approximately matches the insecure baseline, while still offering a meaningful notion of privacy to individual users. Complementing our upper bound results, we also prove new lower bounds regarding the performance of any DO Join algorithm. Differential obliviousness (DO) is a new notion and is a relatively unexplored territory. Following the pioneering investigations by Chan et al. and others, our work is among the very first to formally explore how DO can help overcome the worst-case performance curse of full obliviousness; moreover, we motivate our work with database applications. Our work shows new evidence why DO might be a promising notion, and opens up several exciting future directions.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Security and privacy → Cryptography
  • Information systems → Join algorithms
  • Theory of computation → Design and analysis of algorithms
  • Security and privacy → Mathematical foundations of cryptography
Keywords
  • differentially oblivious
  • database join
  • instance-specific performance

Metrics

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

Related Versions

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. Google Scholar
  2. Archita Agarwal, Maurice Herlihy, Seny Kamara, and Tarik Moataz. Encrypted databases for differential privacy. Proc. Priv. Enhancing Technol., 2019(3):170-190, 2019. URL: https://doi.org/10.2478/popets-2019-0042.
  3. Alok Aggarwal and S. Vitter, Jeffrey. The Input/Output Complexity of Sorting and Related Problems. Commun. ACM, 31(9):1116-1127, September 1988. URL: https://doi.org/10.1145/48529.48535.
  4. M. Ajtai, J. Komlós, and E. Szemerédi. An O(n log n) sorting network. In STOC, 1983. Google Scholar
  5. Prabhanjan Ananth, Xiong Fan, and Elaine Shi. Towards attribute-based encryption for rams from LWE: sub-linear decryption, and more. In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8-12, 2019, Proceedings, Part I, volume 11921 of Lecture Notes in Computer Science, pages 112-141. Springer, 2019. Google Scholar
  6. Arvind Arasu, Spyros Blanas, Ken Eguro, Raghav Kaushik, Donald Kossmann, Ravishankar Ramamurthy, and Ramarathnam Venkatesan. Orthogonal security with cipherbase. In CIDR, 2013. Google Scholar
  7. Arvind Arasu and Raghav Kaushik. Oblivious query processing. In Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014, pages 26-37. OpenProceedings.org, 2014. Google Scholar
  8. Yuriy Arbitman, Moni Naor, and Gil Segev. De-amortized cuckoo hashing: Provable worst-case performance and experimental results. In ICALP, 2009. Google Scholar
  9. Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, and J. Ian Munro. An optimal cache-oblivious priority queue and its application to graph algorithms. SIAM Journal on Computing, 36(6):1672-1695, 2007. URL: https://doi.org/10.1137/S0097539703428324.
  10. Gilad Asharov, T.-H. Hubert Chan, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. Bucket oblivious sort: An extremely simple oblivious sort. In Martin Farach-Colton and Inge Li Gørtz, editors, 3rd Symposium on Simplicity in Algorithms, SOSA@SODA, pages 8-14. SIAM, 2020. Google Scholar
  11. Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, Enoch Peserico, and Elaine Shi. OptORAMa: Optimal Oblivious RAM. In Advances in Cryptology - EUROCRYPT 2020, 2020. To appear. See also: URL: https://eprint.iacr.org/2018/892.
  12. Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, and Elaine Shi. Oblivious parallel tight compaction. In Information-Theoretic Cryptography (ITC), 2020. Google Scholar
  13. Albert Atserias, Martin Grohe, and Dániel Marx. Size bounds and query plans for relational joins. In FOCS, page 739–748, USA, 2008. IEEE Computer Society. Google Scholar
  14. Sumeet Bajaj and Radu Sion. Trusteddb: A trusted hardware-based database with privacy and data confidentiality. IEEE Trans. on Knowl. and Data Eng., 26(3):752–765, 2014. Google Scholar
  15. Victor Balcer and Salil P. Vadhan. Differential privacy on finite computers. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference (ITCS), volume 94, pages 43:1-43:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  16. Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. J. ACM, 64(6):40:1-40:58, 2017. Google Scholar
  17. Amos Beimel, Kobbi Nissim, and Mohammad Zaheri. Exploring differential obliviousness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, volume 145 of LIPIcs, pages 65:1-65:20, 2019. Google Scholar
  18. Andreas Björklund, Rasmus Pagh, Virginia Vassilevska Williams, and Uri Zwick. Listing Triangles. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), volume 8572 of Lecture Notes in Computer Science, pages 223-234. Springer International Publishing, 2014. Google Scholar
  19. Jeremiah Blocki, Anupam Datta, and Joseph Bonneau. Differentially private password frequency lists. In NDSS, 2016. Google Scholar
  20. Elette Boyle, Kai-Min Chung, and Rafael Pass. Large-scale secure computation: Multi-party computation for (parallel) RAM programs. In Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II, volume 9216 of Lecture Notes in Computer Science, pages 742-762. Springer, 2015. Google Scholar
  21. Elette Boyle, Kai-Min Chung, and Rafael Pass. Oblivious parallel ram. In Theory of Cryptography Conference (TCC), 2015. Google Scholar
  22. Mark Bun, Kobbi Nissim, and Uri Stemmer. Simultaneous private learning of multiple concepts. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS), pages 369-380, 2016. Google Scholar
  23. Ran Canetti, Yilei Chen, Justin Holmgren, and Mariana Raykova. Adaptive succinct garbled RAM or: How to delegate your database. In Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part II, volume 9986 of Lecture Notes in Computer Science, pages 61-90, 2016. Google Scholar
  24. David Cash, Paul Grubbs, Jason Perry, and Thomas Ristenpart. Leakage-abuse attacks against searchable encryption. In ACM CCS, page 668–679, 2015. Google Scholar
  25. David Cash, Joseph Jaeger, Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel-Catalin Rosu, and Michael Steiner. Dynamic searchable encryption in very-large databases: Data structures and implementation. In 21st Annual Network and Distributed System Security Symposium, NDSS 2014, San Diego, California, USA, February 23-26, 2014. The Internet Society, 2014. Google Scholar
  26. David Cash, Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel-Catalin Rosu, and Michael Steiner. Highly-scalable searchable symmetric encryption with support for boolean queries. In CRYPTO, 2013. Google Scholar
  27. Hubert Chan, Kai-Min Chung, and Elaine Shi. On the depth of oblivious parallel oram. manuscript, 2017. Google Scholar
  28. 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), page 2448–2467, USA, 2019. Society for Industrial and Applied Mathematics. Google Scholar
  29. T.-H. Hubert Chan and Elaine Shi. Circuit OPRAM: unifying statistically and computationally secure ORAMs and OPRAMs. In Theory of Cryptography Conference, (TCC), 2017. Google Scholar
  30. T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. TISSEC, 14(3):26, 2011. Google Scholar
  31. Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved parameterized upper bounds for vertex cover. In In MFCS, 2006. Google Scholar
  32. Yu-Chi Chen, Sherman S. M. Chow, Kai-Min Chung, Russell W. F. Lai, Wei-Kai Lin, and Hong-Sheng Zhou. Cryptography for parallel RAM from indistinguishability obfuscation. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 179-190. ACM, 2016. Google Scholar
  33. Shumo Chu, Magdalena Balazinska, and Dan Suciu. From theory to practice: Efficient join query evaluation in a parallel database system. In SIGMOD Conference, pages 63-78. ACM, 2015. Google Scholar
  34. Shumo Chu, Danyang Zhuo, Elaine Shi, and T-H. Hubert Chan (randomized author ordering). Differentially oblivious database joins: Overcoming the worst-case curse of fully oblivious algorithms. Online full version of this paper. Cryptology ePrint Archive, Report 2021/593, 2021. URL: https://eprint.iacr.org/2021/593.
  35. Natacha Crooks, Matthew Burke, Ethan Cecchetti, Sitar Harel, Rachit Agarwal, and Lorenzo Alvisi. Obladi: Oblivious serializable transactions in the cloud. In OSDI, page 727–743, USA, 2018. USENIX Association. Google Scholar
  36. Reza Curtmola, Juan A. Garay, Seny Kamara, and Rafail Ostrovsky. Searchable symmetric encryption: improved definitions and efficient constructions. In ACM Conference on Computer and Communications Security, pages 79-88, 2006. Google Scholar
  37. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer Publishing Company, Incorporated, 1st edition, 2015. Google Scholar
  38. Erik D. Demaine. Cache-oblivious algorithms and data structures. In Lecture Notes from the EEF Summer School on Massive Data Sets. BRICS, BRICS, University of Aarhus, Denmark, June 27-July 1 2002. Google Scholar
  39. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC, 2006. Google Scholar
  40. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-407, 2014. URL: http://dblp.uni-trier.de/db/journals/fttcs/fttcs9.html#DworkR14.
  41. Saba Eskandarian and Matei Zaharia. Oblidb: Oblivious query processing for secure databases. Proc. VLDB Endow., 13(2):169-183, 2019. Google Scholar
  42. J. Flum and M. Grohe. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag, Berlin, Heidelberg, 2006. Google Scholar
  43. Matteo Frigo, Charles E Leiserson, Harald Prokop, and Sridhar Ramachandran. Cache-oblivious algorithms. In Foundations of Computer Science, 1999. 40th Annual Symposium on, pages 285-297. IEEE, 1999. Google Scholar
  44. Hector Garcia-Molina, Jeffrey D. Ullman, and Jennifer Widom. Database systems - the complete book (2. ed.). Pearson Education, 2009. Google Scholar
  45. Craig Gentry, Shai Halevi, Steve Lu, Rafail Ostrovsky, Mariana Raykova, and Daniel Wichs. Garbled ram revisited. In EUROCRYPT, pages 405-422, 2014. Google Scholar
  46. Craig Gentry, Shai Halevi, Mariana Raykova, and Daniel Wichs. Outsourcing private ram computation. In STOC, 2014. Google Scholar
  47. O. Goldreich. Towards a theory of software protection and simulation by oblivious RAMs. In STOC, 1987. Google Scholar
  48. Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious RAMs. J. ACM, 1996. Google Scholar
  49. Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich. How to run turing machines on encrypted data. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part II, volume 8043 of Lecture Notes in Computer Science, pages 536-553. Springer, 2013. Google Scholar
  50. S. Dov Gordon, Jonathan Katz, Vladimir Kolesnikov, Fernando Krell, Tal Malkin, Mariana Raykova, and Yevgeniy Vahlis. Secure two-party computation in sublinear (amortized) time. In CCS, 2012. Google Scholar
  51. Paul Grubbs, Marie-Sarah Lacharité, Brice Minaud, and Kenneth G. Paterson. Learning to reconstruct: Statistical learning theory and encrypted database attacks. In 2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019, pages 1067-1083. IEEE, 2019. Google Scholar
  52. Paul Grubbs, Richard McPherson, Muhammad Naveed, Thomas Ristenpart, and Vitaly Shmatikov. Breaking web applications built on top of encrypted data. In ACM CCS, page 1353–1364, 2016. Google Scholar
  53. Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release. In TCC, volume 7194, pages 339-356, 2012. Google Scholar
  54. Moritz Hardt and Guy N. Rothblum. A multiplicative weights mechanism for privacy-preserving data analysis. In FOCS, pages 61-70, 2010. Google Scholar
  55. Xiao Hu and Ke Yi. Instance and output optimal parallel algorithms for acyclic joins. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), page 450–463, 2019. Google Scholar
  56. Mohammad Islam, Mehmet Kuzu, and Murat Kantarcioglu. Access pattern disclosure on searchable encryption: Ramification, attack and mitigation. In Network and Distributed System Security Symposium (NDSS), 2012. Google Scholar
  57. Stanislaw Jarecki, Charanjit Jutla, Hugo Krawczyk, Marcel C. Rosu, and Michael Steiner. Outsourced symmetric private information retrieval. In ACM Conference on Computer and Communications Security (CCS), 2013. Google Scholar
  58. Yael Tauman Kalai and Omer Paneth. Delegating RAM computations. In Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part II, volume 9986 of Lecture Notes in Computer Science, pages 91-118, 2016. Google Scholar
  59. Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O'Neill. Generic attacks on secure outsourced databases. In ACM CCS, page 1329–1340, 2016. Google Scholar
  60. Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O'Neill. Accessing data while preserving privacy. CoRR, abs/1706.01552, 2017. Google Scholar
  61. Mahmoud Abo Khamis, Hung Q. Ngo, Christopher Ré, and Atri Rudra. Joins via geometric resolutions: Worst-case and beyond. In PODS, pages 213-228. ACM, 2015. Google Scholar
  62. Ilan Komargodski and Elaine Shi. Differentially oblivious turing machines. In ITCS, 2021. Google Scholar
  63. Evgenios M. Kornaropoulos, Charalampos Papamanthou, and Roberto Tamassia. The state of the uniform: Attacks on encrypted databases beyond the uniform query distribution. In 2020 IEEE Symposium on Security and Privacy, SP 2020, San Francisco, CA, USA, May 18-21, 2020, pages 1223-1240. IEEE, 2020. Google Scholar
  64. Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas. Releasing search queries and clicks privately. In Proceedings of the 18th International Conference on World Wide Web (WWW), pages 171-180, 2009. Google Scholar
  65. Ios Kotsogiannis, Yuchao Tao, Xi He, Maryam Fanaeepour, Ashwin Machanavajjhala, Michael Hay, and Gerome Miklau. Privatesql: A differentially private sql query engine. Proc. VLDB Endow., 12(11):1371–1384, 2019. Google Scholar
  66. Ios Kotsogiannis, Yuchao Tao, Ashwin Machanavajjhala, Gerome Miklau, and Michael Hay. Architecting a differentially private SQL engine. In CIDR, 2019. Google Scholar
  67. Wei-Kai Lin, Elaine Shi, and Tiancheng Xie. Can we overcome the n log n barrier for oblivious sorting? In SODA, 2019. Google Scholar
  68. Sahar Mazloom and S. Dov Gordon. Secure computation with differentially private access patterns. In CCS, 2018. Google Scholar
  69. Shay Moran and Amir Yehudayoff. A note on average-case sorting. Order, 33:23-28, 2015. Google Scholar
  70. Muhammad Naveed, Seny Kamara, and Charles V. Wright. Inference attacks on property-preserving encrypted databases. In ACM CCS, page 644–655, 2015. Google Scholar
  71. Hung Q. Ngo, Dung T. Nguyen, Christopher Ré, and Atri Rudra. Beyond worst-case analysis for joins with minesweeper. In PODS, pages 234-245. ACM, 2014. Google Scholar
  72. Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. J. Algorithms, 51(2):122-144, 2004. Google Scholar
  73. Vasilis Pappas, Mariana Raykova, Binh Vo, Steven M. Bellovin, and Tal Malkin. Private search in the real world. In Annual Computer Security Applications Conference (ACSAC), 2011. Google Scholar
  74. Raluca Ada Popa, Catherine M. S. Redfield, Nickolai Zeldovich, and Hari Balakrishnan. Cryptdb: Protecting confidentiality with encrypted query processing. In SOSP, page 85–100, New York, NY, USA, 2011. Association for Computing Machinery. Google Scholar
  75. Vijaya Ramachandran and Elaine Shi. Data oblivious algorithms for multicores. https://eprint.iacr.org/2020/947.pdf, 2020.
  76. Vijaya Ramachandran and Elaine Shi. Data oblivious algorithms for multicores. In SPAA, 2021. Google Scholar
  77. Tim Roughgarden. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2020. Google Scholar
  78. Leonard D. Shapiro. Join processing in database systems with large main memories. ACM Trans. Database Syst., 11(3):239-264, 1986. Google Scholar
  79. Micha Sharir and Mark H. Overmars. A simple output-sensitive algorithm for hidden surface removal. ACM Trans. Graph., 11(1):1–11, 1992. Google Scholar
  80. Elaine Shi, John Bethencourt, T-H. Hubert Chan, Dawn Song, and Adrian Perrig. Multi-dimensional range query over encrypted data. In IEEE Symposium on Security and Privacy, pages 350-364, 2007. Google Scholar
  81. Elaine Shi, T.-H. Hubert Chan, Emil Stefanov, and Mingfei Li. Oblivious RAM with O((log N)³) worst-case cost. In ASIACRYPT, 2011. Google Scholar
  82. Dawn Xiaodong Song, David Wagner, and Adrian Perrig. Practical techniques for searches on encrypted data. In Proceedings of the 2000 IEEE Symposium on Security and Privacy, Washington, DC, USA, 2000. IEEE Computer Society. Google Scholar
  83. Emil Stefanov, Charalampos Papamanthou, and Elaine Shi. Practical dynamic searchable symmetric encryption with small leakage. In Network and Distributed System Security Symposium (NDSS), 2014. Google Scholar
  84. Ananda Theertha Suresh. Differentially private anonymized histograms. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alché-Buc, Emily B. Fox, and Roman Garnett, editors, NeurIPS, pages 7969-7979, 2019. Google Scholar
  85. Salil Vadhan. The complexity of differential privacy. In Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich, pages 347-450, Cham, 2017. Springer International Publishing. URL: https://doi.org/10.1007/978-3-319-57048-8_7.
  86. Jeffrey Scott Vitter. External Memory Algorithms and Data Structures: Dealing with Massive Data. ACM Comput. Surv., 33(2):209-271, June 2001. URL: https://doi.org/10.1145/384192.384193.
  87. Sameer Wagh, Paul Cuff, and Prateek Mittal. Differentially private oblivious RAM. PoPETs, 2018(4):64-84, 2018. Google Scholar
  88. Xiao Shaun Wang, T-H. Hubert Chan, and Elaine Shi. Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound. In CCS, 2015. Google Scholar
  89. Mihalis Yannakakis. Algorithms for acyclic database schemes. In VLDB, page 82–94, 1981. Google Scholar
  90. Wenting Zheng, Ankur Dave, Jethro G. Beekman, Raluca Ada Popa, Joseph E. Gonzalez, and Ion Stoica. Opaque: An oblivious and encrypted distributed analytics platform. In NSDI, 2017. 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