{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:50:22Z","timestamp":1750308622262,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,9,1]],"date-time":"2011-09-01T00:00:00Z","timestamp":1314835200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CT CNS-0627554CT CNS-0716608CRI CNS-0708025"],"award-info":[{"award-number":["CT CNS-0627554CT CNS-0716608CRI CNS-0708025"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst. Secur."],"published-print":{"date-parts":[[2011,9]]},"abstract":"<jats:p>\n            In this article we introduce a technique, guaranteeing access pattern privacy against a computationally bounded adversary, in outsourced data storage, with communication and computation overheads orders of magnitude better than existing approaches. In the presence of a small amount of temporary storage (enough to store\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) items and IDs, where\n            <jats:italic>n<\/jats:italic>\n            is the number of items in the database), we can achieve access pattern privacy with computational complexity of less than\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) per query (as compared to, for instance,\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>4<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) for existing approaches).\n          <\/jats:p>\n          <jats:p>We achieve these novel results by applying new insights based on probabilistic analyses of data shuffling algorithms to Oblivious RAM, allowing us to significantly improve its asymptotic complexity. This results in a protocol crossing the boundary between theory and practice and becoming generally applicable for access pattern privacy. We show that on off-the-shelf hardware, large data sets can be queried obliviously orders of magnitude faster than in existing work.<\/jats:p>","DOI":"10.1145\/2019599.2019605","type":"journal-article","created":{"date-parts":[[2011,10,4]],"date-time":"2011-10-04T13:24:18Z","timestamp":1317734658000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Practical Oblivious Outsourced Storage"],"prefix":"10.1145","volume":"14","author":[{"given":"Peter","family":"Williams","sequence":"first","affiliation":[{"name":"Stony Brook University"}]},{"given":"Radu","family":"Sion","sequence":"additional","affiliation":[{"name":"Stony Brook University"}]},{"given":"Miroslava","family":"Sotakova","sequence":"additional","affiliation":[{"name":"Stony Brook University"}]}],"member":"320","published-online":{"date-parts":[[2011,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808726"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Asonov D. 2004. Querying Databases Privately: A New Approach to Private Information Retrieval. Springer Verlag. Asonov D. 2004. Querying Databases Privately: A New Approach to Private Information Retrieval . Springer Verlag.","DOI":"10.1007\/b98671"},{"volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science. 41--50","author":"Chor B.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. MIT Press and McGraw-Hill. Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. MIT Press and McGraw-Hill."},{"key":"e_1_2_1_5_1","unstructured":"Feller W. 1967. An Introduction to Probability Theory and its Applications. Vol. 1. Wiley. Feller W. 1967. An Introduction to Probability Theory and its Applications . Vol. 1. Wiley."},{"key":"e_1_2_1_6_1","unstructured":"Gartner Inc. 1999. Server Storage and RAID Worldwide. Tech. rep. Gartner Group\/Dataquest. www.gartner.com. Gartner Inc. 1999. Server Storage and RAID Worldwide. Tech. rep. Gartner Group\/Dataquest. www.gartner.com."},{"key":"e_1_2_1_7_1","first-page":"72","article-title":"A survey on private information retrieval","volume":"82","author":"Gasarch W.","year":"2004","journal-title":"Bull. EATCS"},{"key":"e_1_2_1_8_1","unstructured":"Gasarch W. 2010. A WebPage on private information retrieval. http:\/\/www.cs.umd.edu\/~gasarch\/pir\/pir.html. Gasarch W. 2010. A WebPage on private information retrieval. http:\/\/www.cs.umd.edu\/~gasarch\/pir\/pir.html."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2007.23"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Goldreich O. 2001. Foundations of Cryptography. Cambridge University Press. Goldreich O. 2001. Foundations of Cryptography . Cambridge University Press.","DOI":"10.1017\/CBO9780511546891"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90214-I"},{"volume-title":"Free Email: Google, MSN Hotmail and Yahoo! (A). SSRN eLibrary.","year":"2004","author":"Hild M.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","unstructured":"IBM Corp. 2008. IBM 4764 Model 001 specification sheet. http:\/\/www-03.ibm.com\/security\/cryptocards\/pdfs\/4764-001_PCIX_Data_Sheet.pdf. IBM Corp. 2008. IBM 4764 Model 001 specification sheet. http:\/\/www-03.ibm.com\/security\/cryptocards\/pdfs\/4764-001_PCIX_Data_Sheet.pdf."},{"volume-title":"Proceedings of the 3rd Working Conference on Privacy and Anonymity in Networked and Distributed Systems (i-NetSec\u201904)","author":"Iliev A.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","unstructured":"Lipmaa H. 2006. AES ciphers: Speed. http:\/\/research.cyber.ee\/~lipmaa\/research\/aes\/rijndael.html. Lipmaa H. 2006. AES ciphers: Speed. http:\/\/research.cyber.ee\/~lipmaa\/research\/aes\/rijndael.html."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1102199.1102201"},{"key":"e_1_2_1_18_1","first-page":"1273","article-title":"Comment and casenote: Subpoena to Google Inc. in ACLU v. Gonzales: \u201cBig Brother\u201d is watching your internet searches through government subpoenas","volume":"75","author":"Scribner C.","year":"2007","journal-title":"U. Cincinnati Law Rev."},{"volume-title":"Proceedings of the Network and Distributed Systems Security Symposium.","author":"Sion R.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2163273.2163277"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455770.1455790"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85886-7_5"}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2019599.2019605","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2019599.2019605","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:42Z","timestamp":1750273662000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2019599.2019605"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["10.1145\/2019599.2019605"],"URL":"https:\/\/doi.org\/10.1145\/2019599.2019605","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"type":"print","value":"1094-9224"},{"type":"electronic","value":"1557-7406"}],"subject":[],"published":{"date-parts":[[2011,9]]},"assertion":[{"value":"2009-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}