{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T16:30:05Z","timestamp":1791477005452,"version":"4.3.4"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319457437","type":"print"},{"value":"9783319457444","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-45744-4_17","type":"book-chapter","created":{"date-parts":[[2016,9,14]],"date-time":"2016-09-14T04:54:30Z","timestamp":1473828870000},"page":"344-362","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Anonymous RAM"],"prefix":"10.1007","author":[{"given":"Michael","family":"Backes","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amir","family":"Herzberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aniket","family":"Kate","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ivan","family":"Pryvalov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,9,15]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"Backes, M., Herzberg, A., Kate, A., Pryvalov, I.: Anonymous RAM (extended version). Cryptology ePrint Archive, Report 2016\/678 (2016)","DOI":"10.1007\/978-3-319-45744-4_17"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Bindschaedler, V., Naveed, M., Pan, X., Wang, X., Huang, Y.: Practicing oblivious access on cloud storage: the gap, the fallacy, and the new way forward. In: CCS, pp. 837\u2013849 (2015)","DOI":"10.1145\/2810103.2813649"},{"key":"17_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/BFb0054851","volume-title":"Algorithmic Number Theory","author":"D Boneh","year":"1998","unstructured":"Boneh, D.: The decision Diffie-Hellman problem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 48\u201363. Springer, Heidelberg (1998)"},{"key":"17_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/978-3-662-49099-0_7","volume-title":"Theory of Cryptography","author":"E Boyle","year":"2016","unstructured":"Boyle, E., Chung, K.-M., Pass, R.: Oblivious parallel RAM and applications. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016-A. LNCS, vol. 9563, pp. 175\u2013204. Springer, Heidelberg (2016). doi:10.1007\/978-3-662-49099-0_7"},{"key":"17_CR5","unstructured":"Camenisch, J., Stadler, M.: Proof systems for general statements about discrete logarithms. Technical report, TR260. Dept. of Computer Science, ETH Z\u00fcrich, March 1997"},{"key":"17_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BFb0055723","volume-title":"Advances in Cryptology - CRYPTO \u201998","author":"D Catalano","year":"1998","unstructured":"Catalano, D., Gennaro, R.: New efficient and secure protocols for verifiable signature sharing and other applications. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 105\u2013120. Springer, Heidelberg (1998)"},{"issue":"2","key":"17_CR7","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1145\/358549.358563","volume":"4","author":"D Chaum","year":"1981","unstructured":"Chaum, D.: Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM 4(2), 84\u201388 (1981)","journal-title":"Commun. ACM"},{"issue":"1","key":"17_CR8","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF00206326","volume":"1","author":"D Chaum","year":"1988","unstructured":"Chaum, D.: The dining cryptographers problem: unconditional sender and recipient untraceability. J. Cryptology 1(1), 65\u201375 (1988)","journal-title":"J. Cryptology"},{"key":"17_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/3-540-48071-4_7","volume-title":"Advances in Cryptology - CRYPTO \u201992","author":"D Chaum","year":"1993","unstructured":"Chaum, D., Pedersen, T.P.: Wallet databases with observers. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 89\u2013105. Springer, Heidelberg (1993)"},{"key":"17_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-662-49099-0_8","volume-title":"Theory of Cryptography","author":"B Chen","year":"2016","unstructured":"Chen, B., Lin, H., Tessaro, S.: Oblivious parallel RAM: improved efficiency and generic constructions. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016-A. LNCS, vol. 9563, pp. 205\u2013234. Springer, Heidelberg (2016). doi:10.1007\/978-3-662-49099-0_8"},{"key":"17_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1007\/978-3-662-45608-8_4","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2014","author":"K-M Chung","year":"2014","unstructured":"Chung, K.-M., Liu, Z., Pass, R.: Statistically-secure ORAM with $$\\tilde{O}(\\log ^2 n)$$ overhead. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 62\u201381. Springer, Heidelberg (2014)"},{"key":"17_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/3-540-48658-5_19","volume-title":"Advances in Cryptology - CRYPTO \u201994","author":"R Cramer","year":"1994","unstructured":"Cramer, R., Damg\u00e5rd, I.B., Schoenmakers, B.: Proof of partial knowledge and simplified design of witness hiding protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 174\u2013187. Springer, Heidelberg (1994)"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Danezis, G., Dingledine, R., Mathewson, N.: Mixminion: design of a type III anonymous remailer protocol. In: Security and Privacy (S&P), pp. 2\u201315 (2003)","DOI":"10.1109\/SECPRI.2003.1199323"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"De Santis, A., Di Crescenzo, G., Persiano, G., Yung, M.: On monotone formula closure of SZK. In: FOCS, pp. 454\u2013465 (1994)","DOI":"10.1109\/SFCS.1994.365745"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"Dingledine, R., Mathewson, N., Syverson, P.: Tor: the second-generation onion router. In: Usenix Security, pp. 303\u2013320 (2004)","DOI":"10.21236\/ADA465464"},{"key":"17_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/978-3-540-30580-4_28","volume-title":"Public Key Cryptography - PKC 2005","author":"Y Dodis","year":"2005","unstructured":"Dodis, Y., Yampolskiy, A.: A verifiable random function with short proofs and keys. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 416\u2013431. Springer, Heidelberg (2005)"},{"key":"17_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-642-27576-0_11","volume-title":"Financial Cryptography and Data Security","author":"M Franz","year":"2012","unstructured":"Franz, M., Williams, P., Carbunar, B., Katzenbeisser, S., Peter, A., Sion, R., Sotakova, M.: Oblivious outsourced storage with delegation. In: Danezis, G. (ed.) FC 2011. LNCS, vol. 7035, pp. 127\u2013140. Springer, Heidelberg (2012)"},{"key":"17_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-540-30576-7_17","volume-title":"Theory of Cryptography","author":"MJ Freedman","year":"2005","unstructured":"Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword search and oblivious pseudorandom functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 303\u2013324. Springer, Heidelberg (2005)"},{"issue":"3","key":"17_CR19","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 (JACM) 43(3), 431\u2013473 (1996)","journal-title":"J. ACM (JACM)"},{"key":"17_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-540-24660-2_14","volume-title":"Topics in Cryptology \u2013 CT-RSA 2004","author":"P Golle","year":"2004","unstructured":"Golle, P., Jakobsson, M., Juels, A., Syverson, P.: Universal re-encryption for mixnets. In: Okamoto, T. (ed.) CT-RSA 2004. LNCS, vol. 2964, pp. 163\u2013178. Springer, Heidelberg (2004)"},{"issue":"6","key":"17_CR21","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1145\/2049697.2049701","volume":"58","author":"MT Goodrich","year":"2011","unstructured":"Goodrich, M.T.: Randomized shellsort: a simple data-oblivious sorting algorithm. J. ACM (JACM) 58(6), 27 (2011)","journal-title":"J. ACM (JACM)"},{"key":"17_CR22","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Oblivious RAM simulation with efficient worst-case access overhead. In: ACM CCSW, pp. 95\u2013100 (2011)","DOI":"10.1145\/2046660.2046680"},{"key":"17_CR23","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":"17_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/978-3-642-00457-5_34","volume-title":"Theory of Cryptography","author":"S Jarecki","year":"2009","unstructured":"Jarecki, S., Liu, X.: Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 577\u2013594. Springer, Heidelberg (2009)"},{"key":"17_CR25","unstructured":"Jinsheng, Z., Wensheng, Z., Qiao, D.: A Multi-user Oblivious RAM for outsourced data (2014). http:\/\/lib.dr.iastate.edu\/cs_techreports\/262\/"},{"key":"17_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":"17_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/978-3-642-36594-2_22","volume-title":"Theory of Cryptography","author":"S Lu","year":"2013","unstructured":"Lu, S., Ostrovsky, R.: Distributed oblivious RAM for secure two-party computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 377\u2013396. Springer, Heidelberg (2013)"},{"key":"17_CR28","doi-asserted-by":"crossref","unstructured":"Maffei, M., Malavolta, G., Reinert, M., Schr\u00f6der, D.: Privacy and access control for outsourced personal records. In: Security and Privacy (S&P), pp. 341\u2013358 (2015)","DOI":"10.1109\/SP.2015.28"},{"key":"17_CR29","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R.: Efficient computation on oblivious RAMs. In: STOC, pp. 514\u2013523 (1990)","DOI":"10.1145\/100216.100289"},{"key":"17_CR30","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. 6223, pp. 502\u2013519. Springer, Heidelberg (2010)"},{"key":"17_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/978-3-540-74143-5_29","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"M Prabhakaran","year":"2007","unstructured":"Prabhakaran, M., Rosulek, M.: Rerandomizable RCCA encryption. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 517\u2013534. Springer, Heidelberg (2007)"},{"key":"17_CR32","doi-asserted-by":"crossref","unstructured":"Sahin, C., Zakhary, V., El Abbadi, A., Lin, H.R., Tessaro, S.: Taostore: Overcoming asynchronicity in oblivious data storage. In: Security and Privacy (S&P) (2016)","DOI":"10.1109\/SP.2016.20"},{"issue":"3","key":"17_CR33","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF00196725","volume":"4","author":"CP Schnorr","year":"1991","unstructured":"Schnorr, C.P.: Efficient signature generation by smart cards. J. Cryptology 4(3), 161\u2013174 (1991)","journal-title":"J. Cryptology"},{"key":"17_CR34","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((log N)$${^3}$$) worst-case cost. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 197\u2013214. Springer, Heidelberg (2011)"},{"key":"17_CR35","doi-asserted-by":"crossref","unstructured":"Stefanov, E., Shi, E.: ObliviStore: High performance oblivious cloud storage. In: Security and Privacy (S&P), pp. 253\u2013267 (2013)","DOI":"10.1109\/SP.2013.25"},{"key":"17_CR36","doi-asserted-by":"crossref","unstructured":"Stefanov, E., Van Dijk, M., Shi, E., Fletcher, C., Ren, L., Yu, X., Devadas, S.: Path oram: an extremely simple oblivious ram protocol. In: CCS, pp. 299\u2013310 (2013)","DOI":"10.1145\/2508859.2516660"},{"key":"17_CR37","unstructured":"The Tor project (2003). https:\/\/www.torproject.org\/. Accessed Feb 2016"},{"key":"17_CR38","doi-asserted-by":"crossref","unstructured":"Wang, X., Chan, T.H., Shi, E.: Circuit ORAM: on tightness of the goldreich-ostrovsky lower bound. In: CCS, pp. 850\u2013861 (2015)","DOI":"10.1145\/2810103.2813634"},{"key":"17_CR39","doi-asserted-by":"crossref","unstructured":"Williams, P., Sion, R., Tomescu, A.: PrivateFS: a parallel oblivious file system. In: CCS, pp. 977\u2013988 (2012)","DOI":"10.1145\/2382196.2382299"}],"container-title":["Lecture Notes in Computer Science","Computer Security \u2013 ESORICS 2016"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-45744-4_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T18:37:09Z","timestamp":1749580629000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-45744-4_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319457437","9783319457444"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-45744-4_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"15 September 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ESORICS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Symposium on Research in Computer Security","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Heraklion","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 September 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 September 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"esorics2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}