{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:53:22Z","timestamp":1775638402494,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642365935","type":"print"},{"value":"9783642365942","type":"electronic"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36594-2_22","type":"book-chapter","created":{"date-parts":[[2013,2,7]],"date-time":"2013-02-07T02:43:27Z","timestamp":1360205007000},"page":"377-396","source":"Crossref","is-referenced-by-count":89,"title":["Distributed Oblivious RAM for Secure Two-Party Computation"],"prefix":"10.1007","author":[{"given":"Steve","family":"Lu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Oblivious RAMs without cryptogrpahic assumptions. In: STOC, pp. 181\u2013190 (2010)","DOI":"10.1145\/1806689.1806716"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: An O(n logn) sorting network. In: STOC, pp. 1\u20139 (1983)","DOI":"10.1145\/800061.808726"},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"Batcher, K.E.: Sorting networks and their applications. In: AFIPS Spring Joint Computing Conference, pp. 307\u2013314 (1968)","DOI":"10.1145\/1468075.1468121"},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Kilian, J., Wigderson, A.: Multi-prover interactive proofs: How to remove intractability assumptions. In: STOC, pp. 113\u2013131 (1988)","DOI":"10.1145\/62212.62223"},{"issue":"7","key":"22_CR5","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"B.H. Bloom","year":"1970","unstructured":"Bloom, B.H.: Space\/time trade-offs in hash coding with allowable errors. Commun. ACM\u00a013(7), 422\u2013426 (1970)","journal-title":"Commun. ACM"},{"key":"22_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-540-74143-5_4","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"D. Boneh","year":"2007","unstructured":"Boneh, D., Kushilevitz, E., Ostrovsky, R., Skeith III, W.E.: Public Key Encryption That Allows PIR Queries. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol.\u00a04622, pp. 50\u201367. Springer, Heidelberg (2007)"},{"key":"22_CR7","unstructured":"Boneh, D., Mazieres, D., Popa, R.A.: Remote oblivious storage: Making oblivious RAM practical. CSAIL Technical Report, MIT-CSAIL-TR-2011-018 (2011)"},{"key":"22_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-642-15317-4_2","volume-title":"Security and Cryptography for Networks","author":"N. Chandran","year":"2010","unstructured":"Chandran, N., Ostrovsky, R., Skeith III, W.E.: Public-Key Encryption with Efficient Amortized Updates. In: Garay, J.A., De Prisco, R. (eds.) SCN 2010. LNCS, vol.\u00a06280, pp. 17\u201335. Springer, Heidelberg (2010)"},{"key":"22_CR9","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: FOCS, pp. 41\u201350 (1995)"},{"key":"22_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/978-3-642-19571-6_10","volume-title":"Theory of Cryptography","author":"I. Damg\u00e5rd","year":"2011","unstructured":"Damg\u00e5rd, I., Meldgaard, S., Nielsen, J.B.: Perfectly Secure Oblivious RAM without Random Oracles. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol.\u00a06597, pp. 144\u2013163. Springer, Heidelberg (2011)"},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Towards a theory of software protection and simulation by oblivious RAMs. In: STOC, pp. 182\u2013194 (1987)","DOI":"10.1145\/28395.28416"},{"key":"22_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891","volume-title":"Foundations of Cryptography: Basic Tools","author":"O. Goldreich","year":"2001","unstructured":"Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2001)"},{"key":"22_CR13","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC, pp. 218\u2013229 (1987)","DOI":"10.1145\/28395.28420"},{"issue":"3","key":"22_CR14","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1145\/233551.233553","volume":"43","author":"O. Goldreich","year":"1996","unstructured":"Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious RAMs. J. ACM\u00a043(3), 431\u2013473 (1996)","journal-title":"J. ACM"},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T.: Randomized shellsort: A simple oblivious sorting algorithm. In: SODA, pp. 1262\u20131277 (2010)","DOI":"10.1137\/1.9781611973075.101"},{"key":"22_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1007\/978-3-642-22012-8_46","volume-title":"Automata, Languages and Programming","author":"M.T. Goodrich","year":"2011","unstructured":"Goodrich, M.T., Mitzenmacher, M.: Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol.\u00a06756, pp. 576\u2013587. Springer, Heidelberg (2011)"},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Oblivious RAM simulation with efficient worst-case access overhead. In: CCSW, pp. 95\u2013100 (2011)","DOI":"10.1145\/2046660.2046680"},{"key":"22_CR18","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Privacy-preserving group data access via stateless oblivious RAM simulation. In: SODA, pp. 157\u2013167 (2012)","DOI":"10.1137\/1.9781611973099.14"},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"Gordon, D., Katz, J., Kolesnikov, V., Malkin, T., Raykova, M., Vahlis, Y.: Secure computation with sublinear amortized work. Cryptology ePrint Archive, Report 2011\/482 (2011)","DOI":"10.1145\/2382196.2382251"},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"Huang, Y., Evans, D., Katz, J., Malka, L.: Faster secure two-party computation using garbled circuits. In: USENIX Security Symposium (2011)","DOI":"10.1007\/978-3-642-25560-1_2"},{"key":"22_CR21","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: STOC, pp. 433\u2013442 (2008)","DOI":"10.1145\/1374376.1374438"},{"key":"22_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1007\/978-3-540-85174-5_32","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"Y. Ishai","year":"2008","unstructured":"Ishai, Y., Prabhakaran, M., Sahai, A.: Founding Cryptography on Oblivious Transfer \u2013 Efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol.\u00a05157, pp. 572\u2013591. Springer, Heidelberg (2008)"},{"key":"22_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1007\/978-3-540-87744-8_51","volume-title":"Algorithms - ESA 2008","author":"A. Kirsch","year":"2008","unstructured":"Kirsch, A., Mitzenmacher, M., Wieder, U.: More Robust Hashing: Cuckoo Hashing with a Stash. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol.\u00a05193, pp. 611\u2013622. Springer, Heidelberg (2008)"},{"key":"22_CR24","unstructured":"Kreuter, B., Shelat, A., Shen, C.-H.: Towards billion-gate secure computation with malicious adversaries. Cryptology ePrint Archive, Report 2012\/179 (2012)"},{"key":"22_CR25","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Lu, S., Ostrovsky, R.: On the (in)security of hash-based oblivious RAM and a new balancing scheme. Cryptology ePrint Archive, Report 2011\/327 (2011)","DOI":"10.1137\/1.9781611973099.13"},{"key":"22_CR26","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Lu, S., Ostrovsky, R.: On the (in)security of hash-based oblivious RAM and a new balancing scheme. In: SODA, pp. 143\u2013156 (2012)","DOI":"10.1137\/1.9781611973099.13"},{"key":"22_CR27","unstructured":"Lu, S., Ostrovsky, R.: Multi-server oblivious RAM. IACR Cryptology ePrint Archive, 2011:384 (2011)"},{"key":"22_CR28","doi-asserted-by":"crossref","unstructured":"Lu, S., Ostrovsky, R.: How to garble RAM programs. IACR Cryptology ePrint Archive, 2012:601 (2012)","DOI":"10.1007\/978-3-642-38348-9_42"},{"key":"22_CR29","doi-asserted-by":"crossref","unstructured":"Naor, M., Nissim, K.: Communication preserving protocols for secure function evaluation. In: STOC, pp. 590\u2013599 (2001)","DOI":"10.1145\/380752.380855"},{"key":"22_CR30","unstructured":"Ostrovsky, R.: Apparatus system and method to efficiently search and modify information stored on remote servers, while hiding the access pattern. U.S. Patent Application No. 12,768,617 (April 27, 2010)"},{"key":"22_CR31","unstructured":"Ostrovsky, R.: Software Protection and Simulation On Oblivious RAMs. PhD thesis, Massachusetts Institute of Technology (1992)"},{"key":"22_CR32","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R.: Efficient computation on oblivious RAMs. In: STOC, pp. 514\u2013523 (1990)","DOI":"10.1145\/100216.100289"},{"key":"22_CR33","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Shoup, V.: Private information storage (extended abstract). In: STOC, pp. 294\u2013303 (1997)","DOI":"10.1145\/258533.258606"},{"key":"22_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11605805_1","volume-title":"Topics in Cryptology \u2013 CT-RSA 2006","author":"D.A. Osvik","year":"2006","unstructured":"Osvik, D.A., Shamir, A., Tromer, E.: Cache Attacks and Countermeasures: The Case of AES. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, vol.\u00a03860, pp. 1\u201320. Springer, Heidelberg (2006)"},{"key":"22_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/3-540-44676-1_10","volume-title":"Algorithms - ESA 2001","author":"R. Pagh","year":"2001","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo Hashing. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 121\u2013133. Springer, Heidelberg (2001)"},{"key":"22_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/978-3-642-14623-7_27","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"B. Pinkas","year":"2010","unstructured":"Pinkas, B., Reinman, T.: Oblivious RAM Revisited. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.\u00a06223, pp. 502\u2013519. Springer, Heidelberg (2010)"},{"issue":"2","key":"22_CR37","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1145\/322123.322138","volume":"26","author":"N. Pippenger","year":"1979","unstructured":"Pippenger, N., Fischer, M.J.: Relations among complexity measures. J. ACM\u00a026(2), 361\u2013381 (1979)","journal-title":"J. ACM"},{"key":"22_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-642-25385-0_11","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2011","author":"E. Shi","year":"2011","unstructured":"Shi, E., Chan, T.-H.H., Stefanov, E., Li, M.: Oblivious RAM with O((logN)3) Worst-Case Cost. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol.\u00a07073, pp. 197\u2013214. Springer, Heidelberg (2011)"},{"key":"22_CR39","unstructured":"Stefanov, E., Shi, E., Song, D.: Towards practical oblivious RAM. In: NDSS (2012)"},{"key":"22_CR40","unstructured":"Williams, P., Sion, R.: Usable PIR. In: NDSS (2008)"},{"key":"22_CR41","doi-asserted-by":"crossref","unstructured":"Williams, P., Sion, R., Carbunar, B.: Building castles out of mud: practical access pattern privacy and correctness on untrusted storage. In: ACM Conference on Computer and Communications Security, pp. 139\u2013148 (2008)","DOI":"10.1145\/1455770.1455790"},{"key":"22_CR42","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Protocols for secure computations (extended abstract). In: FOCS, pp. 160\u2013164 (1982)","DOI":"10.1109\/SFCS.1982.38"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36594-2_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T20:11:22Z","timestamp":1745957482000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36594-2_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642365935","9783642365942"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36594-2_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}