{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T20:58:04Z","timestamp":1791493084955,"version":"4.3.4"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,8,26]],"date-time":"2022-08-26T00:00:00Z","timestamp":1661472000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CNS-1314857, CNS-1514261, CNS-1544613, CNS-1561209, CNS-1601879, CNS-1617676"],"award-info":[{"award-number":["CNS-1314857, CNS-1514261, CNS-1544613, CNS-1561209, CNS-1601879, CNS-1617676"]}]},{"name":"Office of Naval Research Young Investigator Program Award"},{"name":"DARPA Safeware"},{"name":"Hong Kong RGC","award":["17200418 and 17201220"],"award-info":[{"award-number":["17200418 and 17201220"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,8,31]]},"abstract":"<jats:p>\n            It is well-known that a program\u2019s memory access pattern can leak information about its input. To thwart such leakage, most existing works adopt the technique of\n            <jats:bold>oblivious RAM (ORAM)<\/jats:bold>\n            simulation. Such an obliviousness notion has stimulated much debate. Although ORAM techniques have significantly improved over the past few years, the concrete overheads are arguably still undesirable for real-world systems \u2014 part of this overhead is in fact inherent due to a well-known logarithmic ORAM lower bound by Goldreich and Ostrovsky. To make matters worse, when the program\u2019s runtime or output length depend on secret inputs, it may be necessary to perform worst-case padding to achieve full obliviousness and thus incur possibly super-linear overheads.\n          <\/jats:p>\n          <jats:p>Inspired by the elegant notion of differential privacy, we initiate the study of a new notion of access pattern privacy, which we call \u201c (\u03f5 , \u03b4) -differential obliviousness\u201d. We separate the notion of (\u03f5 , \u03b4) -differential obliviousness from classical obliviousness by considering several fundamental algorithmic abstractions including sorting small-length keys, merging two sorted lists, and range query data structures (akin to binary search trees). We show that by adopting differential obliviousness with reasonable choices of \u03f5 and \u03b4 , not only can one circumvent several impossibilities pertaining to full obliviousness, one can also, in several cases, obtain meaningful privacy with little overhead relative to the non-private baselines (i.e., having privacy \u201cwith little extra overhead\u201d). On the other hand, we show that for very demanding choices of \u03f5 and \u03b4 , the same lower bounds for oblivious algorithms would be preserved for (\u03f5, \u03b4) -differential obliviousness.<\/jats:p>","DOI":"10.1145\/3555984","type":"journal-article","created":{"date-parts":[[2022,8,10]],"date-time":"2022-08-10T12:20:09Z","timestamp":1660134009000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Foundations of Differentially Oblivious Algorithms"],"prefix":"10.1145","volume":"69","author":[{"given":"T.-H. Hubert","family":"Chan","sequence":"first","affiliation":[{"name":"University of Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kai-Min","family":"Chung","sequence":"additional","affiliation":[{"name":"Academia Sinica, Taipei, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bruce","family":"Maggs","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,8,26]]},"reference":[{"key":"e_1_3_3_2_2","volume-title":"STOC","author":"Ajtai M.","year":"1983","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di. 1983. An \\( O(N \\log N) \\) sorting network. In STOC."},{"key":"e_1_3_3_3_2","volume-title":"HASP","author":"Anati Ittai","year":"2013","unstructured":"Ittai Anati, Shay Gueron, Simon P. Johnson, and Vincent R. Scarlata. 2013. Innovative technology for CPU based attestation and sealing. In HASP."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1580"},{"key":"e_1_3_3_5_2","article-title":"Oblivious Computation with Data Locality","author":"Asharov Gilad","year":"2017","unstructured":"Gilad Asharov, T.-H. Hubert Chan, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. 2017. Oblivious Computation with Data Locality. Cryptology ePrint Archive 2017\/772.","journal-title":"Cryptology ePrint Archive 2017\/772"},{"key":"e_1_3_3_6_2","volume-title":"STOC","author":"Asharov Gilad","year":"2016","unstructured":"Gilad Asharov, Moni Naor, Gil Segev, and Ido Shahaf. 2016. Searchable symmetric encryption: Optimal locality in linear space via two-dimensional balanced allocations. In STOC."},{"key":"e_1_3_3_7_2","volume-title":"TCC","author":"Boyle Elette","year":"2016","unstructured":"Elette Boyle, Kai-Min Chung, and Rafael Pass. 2016. Oblivious parallel RAM and applications. In TCC."},{"key":"e_1_3_3_8_2","volume-title":"ITCS","author":"Boyle Elette","year":"2016","unstructured":"Elette Boyle and Moni Naor. 2016. Is there an oblivious RAM lower bound?. In ITCS."},{"key":"e_1_3_3_9_2","volume-title":"FOCS","author":"Bun Mark","year":"2015","unstructured":"Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. 2015. Differentially private release and learning of threshold functions. In FOCS."},{"key":"e_1_3_3_10_2","volume-title":"Eurocrypt","author":"Cash David","year":"2014","unstructured":"David Cash and Stefano Tessaro. 2014. The locality of searchable symmetric encryption. In Eurocrypt."},{"key":"e_1_3_3_11_2","first-page":"2448","volume-title":"SODA","author":"Chan T.-H. Hubert","year":"2019","unstructured":"T.-H. Hubert Chan, Kai-Min Chung, Bruce M. Maggs, and Elaine Shi. 2019. Foundations of differentially oblivious algorithms. In SODA. SIAM, 2448\u20132467."},{"key":"e_1_3_3_12_2","volume-title":"TCC","author":"Chan T.-H. Hubert","year":"2017","unstructured":"T.-H. Hubert Chan and Elaine Shi. 2017. Circuit OPRAM: Unifying statistically and computationally secure ORAMs and OPRAMs. In TCC."},{"key":"e_1_3_3_13_2","volume-title":"ICALP","author":"Chan T.-H. Hubert","year":"2010","unstructured":"T.-H. Hubert Chan, Elaine Shi, and Dawn Song. 2010. Private and continual release of statistics. In ICALP."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2043621.2043626"},{"key":"e_1_3_3_15_2","volume-title":"FC","author":"Chan T.-H. Hubert","year":"2012","unstructured":"T.-H. Hubert Chan, Elaine Shi, and Dawn Song. 2012. Privacy-preserving stream aggregation with fault tolerance. In FC."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_3_17_2","volume-title":"STOC","author":"Dwork Cynthia","year":"2010","unstructured":"Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. 2010. Differential privacy under continual observation. In STOC."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_3_3_19_2","first-page":"51","volume-title":"FOCS","author":"Dwork Cynthia","year":"2010","unstructured":"Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. 2010. Boosting and differential privacy. In FOCS. IEEE Computer Society, 51\u201360."},{"key":"e_1_3_3_20_2","first-page":"13","volume-title":"GIS","author":"Eppstein David","year":"2010","unstructured":"David Eppstein, Michael T. Goodrich, and Roberto Tamassia. 2010. Privacy-preserving data-oblivious geometric algorithms for geographic data. In GIS. 13\u201322."},{"key":"e_1_3_3_21_2","volume-title":"ACM Symposium on Theory of Computing (STOC)","author":"Goldreich O.","year":"1987","unstructured":"O. Goldreich. 1987. Towards a theory of software protection and simulation by oblivious RAMs. In ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_3_22_2","volume-title":"ACM Symposium on Theory of Computing (STOC)","author":"Goldreich O.","year":"1987","unstructured":"O. Goldreich, S. Micali, and A. Wigderson. 1987. How to play ANY mental game. In ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_3_3_24_2","volume-title":"STOC","author":"Goodrich Michael T.","year":"2014","unstructured":"Michael T. Goodrich. 2014. Zig-zag sort: A simple deterministic data-oblivious sorting algorithm running in O(N log N) time. In STOC."},{"key":"e_1_3_3_25_2","volume-title":"Design and Analysis of Algorithms - MedAlg","author":"Goodrich Michael T.","year":"2012","unstructured":"Michael T. Goodrich, Daniel S. Hirschberg, Michael Mitzenmacher, and Justin Thaler. 2012. Cache-oblivious dictionaries and multimaps with negligible failure probability. In Design and Analysis of Algorithms - MedAlg."},{"key":"e_1_3_3_26_2","volume-title":"ICALP","author":"Goodrich Michael T.","year":"2011","unstructured":"Michael T. Goodrich and Michael Mitzenmacher. 2011. Privacy-preserving access of outsourced data via oblivious RAM simulation. In ICALP."},{"key":"e_1_3_3_27_2","article-title":"Data-oblivious graph drawing model and algorithms","volume":"1209","author":"Goodrich Michael T.","year":"2012","unstructured":"Michael T. Goodrich, Olga Ohrimenko, and Roberto Tamassia. 2012. Data-oblivious graph drawing model and algorithms. CoRR abs\/1209.0756 (2012).","journal-title":"CoRR"},{"key":"e_1_3_3_28_2","article-title":"Attribute-based encryption for circuits","author":"Gorbunov Sergey","unstructured":"Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. 2013. Attribute-based encryption for circuits. In submission to STOC 2013. ACM, 545\u2013554.","journal-title":"In submission to STOC 2013"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.09.001"},{"key":"e_1_3_3_30_2","volume-title":"FOCS","author":"Han Yijie","year":"2002","unstructured":"Yijie Han and Mikkel Thorup. 2002. Integer sorting in 0(N sqrt (log log N)) expected time and linear space. In FOCS."},{"key":"e_1_3_3_31_2","volume-title":"CCS","author":"Kellaris Georgios","year":"2016","unstructured":"Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O\u2019Neill. 2016. Generic attacks on secure outsourced databases. In CCS."},{"key":"e_1_3_3_32_2","article-title":"Accessing data while preserving privacy","volume":"1706","author":"Kellaris Georgios","year":"2017","unstructured":"Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O\u2019Neill. 2017. Accessing data while preserving privacy. CoRR abs\/1706.01552 (2017). http:\/\/arxiv.org\/abs\/1706.01552.","journal-title":"CoRR"},{"key":"e_1_3_3_33_2","volume-title":"Asiacrypt","author":"Keller Marcel","year":"2014","unstructured":"Marcel Keller and Peter Scholl. 2014. Efficient, oblivious data structures for MPC. In Asiacrypt."},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.5555\/902352"},{"key":"e_1_3_3_35_2","volume-title":"The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching","author":"Knuth Donald E.","year":"1998","unstructured":"Donald E. Knuth. 1998. The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching."},{"key":"e_1_3_3_36_2","volume-title":"SODA","author":"Lin Wei-Kai","year":"2019","unstructured":"Wei-Kai Lin, Elaine Shi, and Tiancheng Xie. 2019. Can we overcome the \\( n \\log n \\) barrier for oblivious sort?. In SODA."},{"key":"e_1_3_3_37_2","volume-title":"S&P","author":"Liu Chang","year":"2015","unstructured":"Chang Liu, Xiao Shaun Wang, Kartik Nayak, Yan Huang, and Elaine Shi. 2015. ObliVM: A programming framework for secure computation. In S&P."},{"key":"e_1_3_3_38_2","first-page":"490","volume-title":"CCS","author":"Mazloom Sahar","year":"2018","unstructured":"Sahar Mazloom and S. Dov Gordon. 2018. Secure computation with differentially private access patterns. In CCS. ACM, 490\u2013507."},{"key":"e_1_3_3_39_2","first-page":"10","article-title":"Innovative instructions and software model for isolated execution","volume":"13","author":"McKeen Frank","year":"2013","unstructured":"Frank McKeen, Ilya Alexandrovich, Alex Berenzon, Carlos V. Rozas, Hisham Shafi, Vedvyas Shanbhogue, and Uday R. Savagaonkar. 2013. Innovative instructions and software model for isolated execution. HASP 13 (2013), 10.","journal-title":"HASP"},{"key":"e_1_3_3_40_2","first-page":"554","volume-title":"STACS","author":"Mitchell John C.","year":"2014","unstructured":"John C. Mitchell and Joe Zimmerman. 2014. Data-oblivious data structures. In STACS. 554\u2013565."},{"key":"e_1_3_3_41_2","volume-title":"IEEE S & P","author":"Nayak Kartik","year":"2015","unstructured":"Kartik Nayak, Xiao Shaun Wang, Stratis Ioannidis, Udi Weinsberg, Nina Taft, and Elaine Shi. 2015. GraphSC: Parallel secure computation made easy. In IEEE S & P."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321962"},{"key":"e_1_3_3_43_2","volume-title":"EUROCRYPT","author":"Sahai Amit","year":"2005","unstructured":"Amit Sahai and Brent Waters. 2005. Fuzzy identity-based encryption. In EUROCRYPT."},{"key":"e_1_3_3_44_2","first-page":"197","volume-title":"ASIACRYPT","author":"Shi Elaine","year":"2011","unstructured":"Elaine Shi, T.-H. Hubert Chan, Emil Stefanov, and Mingfei Li. 2011. Oblivious RAM with \\( O((\\log N)^3) \\) worst-case cost. In ASIACRYPT. 197\u2013214."},{"key":"e_1_3_3_45_2","volume-title":"CCS","author":"Stefanov Emil","year":"2013","unstructured":"Emil Stefanov, Marten van Dijk, Elaine Shi, Christopher Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. 2013. Path ORAM \u2013 an extremely simple oblivious RAM protocol. In CCS."},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2002.1211"},{"key":"e_1_3_3_47_2","volume-title":"The Complexity of Differential Privacy","author":"Vahdan Salil","unstructured":"Salil Vahdan. The Complexity of Differential Privacy."},{"key":"e_1_3_3_48_2","article-title":"Root ORAM: A tunable differentially private oblivious RAM","volume":"1601","author":"Wagh Sameer","year":"2016","unstructured":"Sameer Wagh, Paul Cuff, and Prateek Mittal. 2016. Root ORAM: A tunable differentially private oblivious RAM. CoRR abs\/1601.03378 (2016).","journal-title":"CoRR"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/321439.321449"},{"key":"e_1_3_3_50_2","volume-title":"CCS","author":"Wang Xiao Shaun","year":"2015","unstructured":"Xiao Shaun Wang, T.-H. Hubert Chan, and Elaine Shi. 2015. Circuit ORAM: On tightness of the Goldreich-Ostrovsky lower bound. In CCS."},{"key":"e_1_3_3_51_2","volume-title":"CCS","author":"Wang Xiao Shaun","year":"2014","unstructured":"Xiao Shaun Wang, Yan Huang, T.-H. Hubert Chan, Abhi Shelat, and Elaine Shi. 2014. SCORAM: Oblivious RAM for secure computation. In CCS."},{"key":"e_1_3_3_52_2","volume-title":"CCS","author":"Wang Xiao Shaun","year":"2014","unstructured":"Xiao Shaun Wang, Kartik Nayak, Chang Liu, T.-H. Hubert Chan, Elaine Shi, Emil Stefanov, and Yan Huang. 2014. Oblivious data structures. In CCS."},{"key":"e_1_3_3_53_2","volume-title":"FOCS","author":"Yao Andrew Chi-Chih","year":"1986","unstructured":"Andrew Chi-Chih Yao. 1986. How to generate and exchange secrets. In FOCS."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3555984","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3555984","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3555984","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:41Z","timestamp":1750186961000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3555984"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,26]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8,31]]}},"alternative-id":["10.1145\/3555984"],"URL":"https:\/\/doi.org\/10.1145\/3555984","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,26]]},"assertion":[{"value":"2020-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}