{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T15:11:59Z","timestamp":1775315519989,"version":"3.50.1"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030172527","type":"print"},{"value":"9783030172534","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-17253-4_1","type":"book-chapter","created":{"date-parts":[[2019,4,7]],"date-time":"2019-04-07T23:02:48Z","timestamp":1554678168000},"page":"3-33","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Sub-logarithmic Distributed Oblivious RAM with Small Block Size"],"prefix":"10.1007","author":[{"given":"Eyal","family":"Kushilevitz","sequence":"first","affiliation":[]},{"given":"Tamer","family":"Mour","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,4,6]]},"reference":[{"key":"1_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/978-3-662-54365-8_5","volume-title":"Public-Key Cryptography \u2013 PKC 2017","author":"I Abraham","year":"2017","unstructured":"Abraham, I., Fletcher, C.W., Nayak, K., Pinkas, B., Ren, L.: Asymptotically tight bounds for composing ORAM with PIR. In: Fehr, S. (ed.) PKC 2017. LNCS, vol. 10174, pp. 91\u2013120. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-54365-8_5"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Adler, M., Chakrabarti, S., Mitzenmacher, M., Rasmussen, L.: Parallel randomized load balancing. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC 1995, pp. 238\u2013247. ACM, New York (1995)","DOI":"10.1145\/225058.225131"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: An 0(n log n) sorting network. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC 1983, pp. 1\u20139. ACM, New York (1983)","DOI":"10.1145\/800061.808726"},{"key":"1_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-3-642-54631-0_8","volume-title":"Public-Key Cryptography \u2013 PKC 2014","author":"D Apon","year":"2014","unstructured":"Apon, D., Katz, J., Shi, E., Thiruvengadam, A.: Verifiable oblivious storage. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 131\u2013148. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54631-0_8"},{"key":"1_CR5","unstructured":"Asharov, G., Komargodski, I., Lin, W.-K., Nayak, K., Shi, E.: OptORAMa: optimal oblivious RAM. Cryptology ePrint Archive, Report 2018\/892 (2018)"},{"key":"1_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-540-74208-1_23","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"O Barkol","year":"2007","unstructured":"Barkol, O., Ishai, Y., Weinreb, E.: On locally decodable codes, self-correctable codes, and t-private PIR. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) APPROX\/RANDOM -2007. LNCS, vol. 4627, pp. 311\u2013325. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-74208-1_23"},{"key":"1_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-662-46803-6_12","volume-title":"Advances in Cryptology - EUROCRYPT 2015","author":"E Boyle","year":"2015","unstructured":"Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 337\u2013367. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46803-6_12"},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"Chan, T.-H.H., Guo, Y., Lin, W.-K., Shi, E.: Oblivious hashing revisited, and applications to asymptotically efficient ORAM and OPRAM. Cryptology ePrint Archive, Report 2017\/924 (2017)","DOI":"10.1007\/978-3-319-70694-8_23"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Chan, T.-H.H, Katz, J., Nayak, K., Polychroniadou, A., Shi, E.: More is less: perfectly secure oblivious algorithms in the multi-server setting. Cryptology ePrint Archive, Report 2018\/851 (2018)","DOI":"10.1007\/978-3-030-03332-3_7"},{"issue":"6","key":"1_CR10","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/293347.293350","volume":"45","author":"B Chor","year":"1998","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. J. ACM 45(6), 965\u2013981 (1998)","journal-title":"J. ACM"},{"key":"1_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-662-49099-0_6","volume-title":"Theory of Cryptography","author":"S Devadas","year":"2016","unstructured":"Devadas, S., van Dijk, M., Fletcher, C.W., Ren, L., Shi, E., Wichs, D.: Onion ORAM: a constant bandwidth blowup oblivious RAM. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 145\u2013174. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49099-0_6"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Doerner, J., Shelat, A.: Scaling ORAM for secure computation. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, pp. 523\u2013535. ACM, New York (2017)","DOI":"10.1145\/3133956.3133967"},{"issue":"4","key":"1_CR13","doi-asserted-by":"publisher","first-page":"39:1","DOI":"10.1145\/2968443","volume":"63","author":"Z Dvir","year":"2016","unstructured":"Dvir, Z., Gopi, S.: 2-Server PIR with subpolynomial communication. J. ACM 63(4), 39:1\u201339:15 (2016)","journal-title":"J. ACM"},{"key":"1_CR14","unstructured":"Fletcher, C.W., Naveed, M., Ren, L., Shi, E., Stefanov, E.: Bucket ORAM: single online roundtrip, constant bandwidth oblivious RAM. IACR Cryptology ePrint Archive, 2015:1065 (2015)"},{"key":"1_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1007\/11523468_65","volume-title":"Automata, Languages and Programming","author":"C Gentry","year":"2005","unstructured":"Gentry, C., Ramzan, Z.: Single-database private information retrieval with constant communication rate. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 803\u2013815. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11523468_65"},{"key":"1_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1007\/978-3-642-55220-5_35","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"N Gilboa","year":"2014","unstructured":"Gilboa, N., Ishai, Y.: Distributed point functions and their applications. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 640\u2013658. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-55220-5_35"},{"issue":"3","key":"1_CR17","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 43(3), 431\u2013473 (1996)","journal-title":"J. ACM"},{"key":"1_CR18","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":"MT 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. LNCS, vol. 6756, pp. 576\u2013587. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22012-8_46"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"Gordon, D., Katz, J., Wang, X.: Simple and efficient two-server ORAM. Cryptology ePrint Archive, Report 2018\/005 (2018)","DOI":"10.1007\/978-3-030-03332-3_6"},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"Gordon, S.D., et al.: Secure two-party computation in sublinear (amortized) time. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security, CCS 2012, pp. 513\u2013524. ACM, New York (2012)","DOI":"10.1145\/2382196.2382251"},{"issue":"4","key":"1_CR21","doi-asserted-by":"publisher","first-page":"1543","DOI":"10.1137\/080728743","volume":"39","author":"A Kirsch","year":"2009","unstructured":"Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: cuckoo hashing with a stash. SIAM J. Comput. 39(4), 1543\u20131561 (2009)","journal-title":"SIAM J. Comput."},{"key":"1_CR22","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: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 143\u2013156. Society for Industrial and Applied Mathematics, Philadelphia (2012)","DOI":"10.1137\/1.9781611973099.13"},{"key":"1_CR23","unstructured":"Kushilevitz, E., Ostrovsky, R.: Replication is not needed: single database, computationally-private information retrieval. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, p. 364. IEEE Computer Society, Washington, DC (1997)"},{"key":"1_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/978-3-319-96881-0_18","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"KG Larsen","year":"2018","unstructured":"Larsen, K.G., Nielsen, J.B.: Yes, there is an oblivious RAM lower bound!. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 523\u2013542. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96881-0_18"},{"key":"1_CR25","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). https:\/\/doi.org\/10.1007\/978-3-642-36594-2_22"},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"Moataz, T., Blass, E., Mayberry, T.: CHf-ORAM: a constant communication ORAM without homomorphic encryption. Cryptology ePrint Archive, Report 2015\/1116 (2015)","DOI":"10.1145\/2810103.2813701"},{"key":"1_CR27","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R.: Efficient computation on oblivious RAMs. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC 1990, pp. 514\u2013523. ACM, New York (1990)","DOI":"10.1145\/100216.100289"},{"key":"1_CR28","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Shoup, V.: Private information storage (extended abstract). In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC 1997, pp. 294\u2013303. ACM, New York (1997)","DOI":"10.1145\/258533.258606"},{"issue":"2","key":"1_CR29","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R Pagh","year":"2004","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms 51(2), 122\u2013144 (2004)","journal-title":"J. Algorithms"},{"key":"1_CR30","doi-asserted-by":"crossref","unstructured":"Patel, S., Persiano, G., Raykova, M., Yeo, K.: PanORAMa: oblivious RAM with logarithmic overhead. Cryptology ePrint Archive, Report 2018\/373 (2018)","DOI":"10.1109\/FOCS.2018.00087"},{"key":"1_CR31","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). https:\/\/doi.org\/10.1007\/978-3-642-14623-7_27"},{"issue":"3","key":"1_CR32","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1145\/2508148.2485971","volume":"41","author":"L Ren","year":"2013","unstructured":"Ren, L., Yu, X., Fletcher, C.W., van Dijk, M., Devadas, S.: Design space exploration and optimization of path oblivious RAM in secure processors. SIGARCH Comput. Archit. News 41(3), 571\u2013582 (2013)","journal-title":"SIGARCH Comput. Archit. News"},{"key":"1_CR33","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. 7073, pp. 197\u2013214. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-25385-0_11"},{"key":"1_CR34","doi-asserted-by":"crossref","unstructured":"Stefanov, E., et al.: Path ORAM: an extremely simple oblivious RAM protocol. In: Proceedings of the 2013 ACM SIGSAC Conference on Computer Communications Security, CCS 2013, pp. 299\u2013310. ACM, New York (2013)","DOI":"10.1145\/2508859.2516660"},{"key":"1_CR35","doi-asserted-by":"crossref","unstructured":"Wang, X., Chan, H., Shi, E.: Circuit ORAM: on tightness of the Goldreich-Ostrovsky lower bound. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS 2015, pp. 850\u2013861. ACM, New York (2015)","DOI":"10.1145\/2810103.2813634"},{"key":"1_CR36","doi-asserted-by":"crossref","unstructured":"Wang, X., Huang, Y., Chan, T.-H., Shelat, A., Shi, E.: SCORAM: oblivious RAM for secure computation. In: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS 2014, pp. 191\u2013202. ACM, New York (2014)","DOI":"10.1145\/2660267.2660365"},{"key":"1_CR37","doi-asserted-by":"crossref","unstructured":"Zahur, S., et al.: Revisiting square-root ORAM: efficient random access in multi-party computation. In: 2016 IEEE Symposium on Security and Privacy (SP), pp. 218\u2013234, May 2016","DOI":"10.1109\/SP.2016.21"},{"key":"1_CR38","unstructured":"Zhang, J., Ma, Q., Zhang, W., Qiao, D.: MSKT-ORAM: a constant bandwidth ORAM without homomorphic encryption. Cryptology ePrint Archive, Report 2016\/882 (2016)"}],"container-title":["Lecture Notes in Computer Science","Public-Key Cryptography \u2013 PKC 2019"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-17253-4_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T12:35:33Z","timestamp":1709814933000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-17253-4_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030172527","9783030172534"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-17253-4_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"6 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"PKC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"IACR International Workshop on Public Key Cryptography","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Beijing","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 April 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 April 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"pkc2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/pkc.iacr.org\/2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}