{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T22:26:55Z","timestamp":1780352815630,"version":"3.54.1"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030752477","type":"print"},{"value":"9783030752484","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-75248-4_18","type":"book-chapter","created":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T14:08:19Z","timestamp":1619791699000},"page":"499-527","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Two-Server Distributed ORAM with Sublinear Computation and Constant Rounds"],"prefix":"10.1007","author":[{"given":"Ariel","family":"Hamlin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mayank","family":"Varia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,5,1]]},"reference":[{"key":"18_CR1","doi-asserted-by":"publisher","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","DOI":"10.1007\/978-3-662-54365-8_5"},{"key":"18_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/978-3-030-45724-2_14","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2020","author":"G Asharov","year":"2020","unstructured":"Asharov, G., Komargodski, I., Lin, W.-K., Nayak, K., Peserico, E., Shi, E.: OptORAMa: optimal oblivious RAM. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 403\u2013432. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45724-2_14"},{"key":"18_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/978-3-030-36033-7_18","volume-title":"Theory of Cryptography","author":"E Boyle","year":"2019","unstructured":"Boyle, E., Holmgren, J., Weiss, M.: Permuted puzzles and cryptographic hardness. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019. LNCS, vol. 11892, pp. 465\u2013493. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-36033-7_18"},{"key":"18_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1007\/978-3-319-70503-3_22","volume-title":"Theory of Cryptography","author":"E Boyle","year":"2017","unstructured":"Boyle, E., Ishai, Y., Pass, R., Wootters, M.: Can we access a database both locally and privately? In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10678, pp. 662\u2013693. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70503-3_22"},{"key":"18_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/978-3-030-57990-6_11","volume-title":"Security and Cryptography for Networks","author":"P Bunn","year":"2020","unstructured":"Bunn, P., Katz, J., Kushilevitz, E., Ostrovsky, R.: Efficient 3-party distributed ORAM. In: Galdi, C., Kolesnikov, V. (eds.) SCN 2020. LNCS, vol. 12238, pp. 215\u2013232. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-57990-6_11"},{"key":"18_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"694","DOI":"10.1007\/978-3-319-70503-3_23","volume-title":"Theory of Cryptography","author":"R Canetti","year":"2017","unstructured":"Canetti, R., Holmgren, J., Richelson, S.: Towards doubly efficient private information retrieval. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10678, pp. 694\u2013726. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70503-3_23"},{"key":"18_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-030-03332-3_7","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2018","author":"T-HH Chan","year":"2018","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. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11274, pp. 158\u2013188. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-03332-3_7"},{"issue":"90","key":"18_CR8","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","volume":"19","author":"JW Cooley","year":"1965","unstructured":"Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex fourier series. Math. Comput. 19(90), 297\u2013301 (1965)","journal-title":"Math. Comput."},{"key":"18_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/11681878_15","volume-title":"Theory of Cryptography","author":"I Damg\u00e5rd","year":"2006","unstructured":"Damg\u00e5rd, I., Fitzi, M., Kiltz, E., Nielsen, J.B., Toft, T.: Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 285\u2013304. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11681878_15"},{"key":"18_CR10","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). https:\/\/doi.org\/10.1007\/978-3-540-30580-4_28"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Doerner, J., Shelat, A.: Scaling ORAM for secure computation. In: ACM Conference on Computer and Communications Security, pp. 523\u2013535. ACM (2017)","DOI":"10.1145\/3133956.3133967"},{"issue":"12","key":"18_CR12","doi-asserted-by":"publisher","first-page":"6265","DOI":"10.1109\/TIT.2010.2079016","volume":"56","author":"S Gao","year":"2010","unstructured":"Gao, S., Mateer, T.D.: Additive fast fourier transforms over finite fields. IEEE Trans. Inf. Theory 56(12), 6265\u20136272 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"Garg, S., Lu, S., Ostrovsky, R.: Black-box garbled RAM. In: FOCS, pp. 210\u2013229. IEEE Computer Society (2015)","DOI":"10.1109\/FOCS.2015.22"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Garg, S., Lu, S., Ostrovsky, R., Scafuro, A.: Garbled RAM from one-way functions. In: STOC, pp. 449\u2013458. ACM (2015)","DOI":"10.1145\/2746539.2746593"},{"key":"18_CR15","first-page":"1010","volume":"2015","author":"S Garg","year":"2015","unstructured":"Garg, S., Mohassel, P., Papamanthou, C.: TWORAM: round-optimal oblivious RAM with applications to searchable encryption. IACR Cryptol. ePrint Arch. 2015, 1010 (2015)","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"18_CR16","doi-asserted-by":"publisher","unstructured":"Gentry, C., Halevi, S., Lu, S., Ostrovsky, R., Raykova, M., Wichs, D.: Garbled RAM revisited. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 405\u2013422. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-55220-5_23","DOI":"10.1007\/978-3-642-55220-5_23"},{"issue":"3","key":"18_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":"18_CR18","doi-asserted-by":"crossref","unstructured":"Gordon, S.D., Katz, J., Kolesnikov, V., Krell, F., Malkin, T., Raykova, M., Vahlis, Y.: Secure two-party computation in sublinear (amortized) time. In: ACM Conference on Computer and Communications Security, pp. 513\u2013524. ACM (2012)","DOI":"10.1145\/2382196.2382251"},{"key":"18_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/978-3-030-03332-3_6","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2018","author":"SD Gordon","year":"2018","unstructured":"Gordon, S.D., Katz, J., Wang, X.: Simple and efficient two-server ORAM. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11274, pp. 141\u2013157. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-03332-3_6"},{"key":"18_CR20","first-page":"1547","volume":"2020","author":"A Hamlin","year":"2020","unstructured":"Hamlin, A., Varia, M.: Two-server distributed ORAM with sublinear computation and constant rounds. IACR Cryptol. ePrint Arch. 2020, 1547 (2020)","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"18_CR21","first-page":"1158","volume":"2017","author":"T Hoang","year":"2017","unstructured":"Hoang, T., Yavuz, A.A., Durak, F.B., Guajardo, J.: Oblivious dynamic searchable encryption via distributed PIR and ORAM. IACR Cryptol. ePrint Arch. 2017, 1158 (2017)","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"18_CR22","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). https:\/\/doi.org\/10.1007\/978-3-642-00457-5_34"},{"key":"18_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/978-3-319-93387-0_19","volume-title":"Applied Cryptography and Network Security","author":"S Jarecki","year":"2018","unstructured":"Jarecki, S., Wei, B.: 3PC ORAM with low latency, low bandwidth, and fast batch retrieval. In: Preneel, B., Vercauteren, F. (eds.) ACNS 2018. LNCS, vol. 10892, pp. 360\u2013378. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-93387-0_19"},{"key":"18_CR24","doi-asserted-by":"crossref","unstructured":"Kedlaya, K.S., Umans, C.: Fast modular composition in any characteristic. In: FOCS, pp. 146\u2013155. IEEE Computer Society (2008)","DOI":"10.1109\/FOCS.2008.13"},{"key":"18_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-17253-4_1","volume-title":"Public-Key Cryptography \u2013 PKC 2019","author":"E Kushilevitz","year":"2019","unstructured":"Kushilevitz, E., Mour, T.: Sub-logarithmic distributed oblivious RAM with small block size. In: Lin, D., Sako, K. (eds.) PKC 2019. LNCS, vol. 11442, pp. 3\u201333. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17253-4_1"},{"key":"18_CR26","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":"18_CR27","doi-asserted-by":"crossref","unstructured":"Lu, S., Ostrovsky, R.: How to garble RAM programs. In: EUROCRYPT. Lecture Notes in Computer Science, vol. 7881, pp. 719\u2013734. Springer (2013)","DOI":"10.1007\/978-3-642-38348-9_42"},{"key":"18_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-56877-1_1","volume-title":"Advances in Cryptology \u2013 CRYPTO 2020","author":"P Miao","year":"2020","unstructured":"Miao, P., Patel, S., Raykova, M., Seth, K., Yung, M.: Two-sided malicious security for private intersection-sum with cardinality. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 3\u201333. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-56877-1_1"},{"key":"18_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/978-3-540-71677-8_23","volume-title":"Public Key Cryptography \u2013 PKC 2007","author":"T Nishide","year":"2007","unstructured":"Nishide, T., Ohta, K.: Multiparty computation for interval, equality, and comparison without bit-decomposition protocol. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 343\u2013360. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-71677-8_23"},{"key":"18_CR30","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Shoup, V.: Private information storage (extended abstract). In: STOC, pp. 294\u2013303. ACM (1997)","DOI":"10.1145\/258533.258606"},{"key":"18_CR31","doi-asserted-by":"crossref","unstructured":"Patel, S., Persiano, G., Raykova, M., Yeo, K.: Panorama: Oblivious RAM with logarithmic overhead. In: FOCS, pp. 871\u2013882. IEEE Computer Society (2018)","DOI":"10.1109\/FOCS.2018.00087"},{"key":"18_CR32","doi-asserted-by":"crossref","unstructured":"Roche, D.S., Aviv, A.J., Choi, S.G.: A practical oblivious map data structure with secure deletion and history independence. In: IEEE Symposium on Security and Privacy, pp. 178\u2013197. IEEE Computer Society (2016)","DOI":"10.1109\/SP.2016.19"},{"key":"18_CR33","doi-asserted-by":"crossref","unstructured":"Wang, X., Chan, T.H., Shi, E.: Circuit ORAM: on tightness of the goldreich-ostrovsky lower bound. In: ACM Conference on Computer and Communications Security, pp. 850\u2013861. ACM (2015)","DOI":"10.1145\/2810103.2813634"},{"key":"18_CR34","doi-asserted-by":"crossref","unstructured":"Wang, X.S., Huang, Y., Chan, T.H., Shelat, A., Shi, E.: SCORAM: oblivious RAM for secure computation. In: ACM Conference on Computer and Communications Security, pp. 191\u2013202. ACM (2014)","DOI":"10.1145\/2660267.2660365"},{"key":"18_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1007\/978-3-030-03810-6_22","volume-title":"Theory of Cryptography","author":"M Weiss","year":"2018","unstructured":"Weiss, M., Wichs, D.: Is there an oblivious RAM lower bound for online reads? In: Beimel, A., Dziembowski, S. (eds.) TCC 2018. LNCS, vol. 11240, pp. 603\u2013635. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-03810-6_22"},{"key":"18_CR36","doi-asserted-by":"crossref","unstructured":"Zahur, S., Wang, X., Raykova, M., Gasc\u00f3n, A., Doerner, J., Evans, D., Katz, J.: Revisiting square-root ORAM: efficient random access in multi-party computation. In: IEEE Symposium on Security and Privacy, pp. 218\u2013234. IEEE Computer Society (2016)","DOI":"10.1109\/SP.2016.21"},{"key":"18_CR37","first-page":"882","volume":"2016","author":"J Zhang","year":"2016","unstructured":"Zhang, J., Ma, Q., Zhang, W., Qiao, D.: MSKT-ORAM: a constant bandwidth ORAM without homomorphic encryption. IACR Cryptol. ePrint Arch. 2016, 882 (2016)","journal-title":"IACR Cryptol. ePrint Arch."}],"container-title":["Lecture Notes in Computer Science","Public-Key Cryptography \u2013 PKC 2021"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-75248-4_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,30]],"date-time":"2024-04-30T00:04:14Z","timestamp":1714435454000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-75248-4_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030752477","9783030752484"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-75248-4_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"1 May 2021","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 Conference on Public-Key Cryptography","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 May 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 May 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"pkc2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/pkc.iacr.org\/2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Web-Submission-and-Review","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"156","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"52","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3,5","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"15","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}