{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T22:13:16Z","timestamp":1791324796102,"version":"4.3.1"},"publisher-location":"Berlin, Heidelberg","reference-count":52,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662490983","type":"print"},{"value":"9783662490990","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,12,24]],"date-time":"2015-12-24T00:00:00Z","timestamp":1450915200000},"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":[[2016]]},"DOI":"10.1007\/978-3-662-49099-0_6","type":"book-chapter","created":{"date-parts":[[2015,12,23]],"date-time":"2015-12-23T13:42:48Z","timestamp":1450878168000},"page":"145-174","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":109,"title":["Onion ORAM: A Constant Bandwidth Blowup Oblivious RAM"],"prefix":"10.1007","author":[{"given":"Srinivas","family":"Devadas","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marten","family":"van Dijk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christopher W.","family":"Fletcher","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ling","family":"Ren","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Wichs","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,12,24]]},"reference":[{"key":"6_CR1","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)"},{"key":"6_CR2","unstructured":"Blum, M., Evans, W.S., Gemmell, P., Kannan, S., Naor, M.: Checking the correctness of memories. In: FOCS (1991)"},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/978-3-642-22792-9_29","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"Z Brakerski","year":"2011","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from ring-LWE and security for key dependent messages. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 505\u2013524. Springer, Heidelberg (2011)"},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s001459910006","volume":"13","author":"R Canetti","year":"2000","unstructured":"Canetti, R.: Security and composition of multiparty cryptographic protocols. J. Cryptol. 13, 143\u2013202 (2000)","journal-title":"J. Cryptol."},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: FOCS (2001)","DOI":"10.1109\/SFCS.2001.959888"},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/3-540-44586-2_9","volume-title":"Public Key Cryptography","author":"I Damgard","year":"2001","unstructured":"Damgard, I., Jurik, M.: A generalisation, a simplification and some applications of Paillier\u2019s probabilistic public-key system. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119\u2013136. Springer, Heidelberg (2001)"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Dautrich, J., Ravishankar, C.: Combining ORAM with PIR to minimize bandwidth costs. In: CODASPY (2015)","DOI":"10.1145\/2699026.2699117"},{"key":"6_CR8","unstructured":"Dautrich, J., Stefanov, E., Shi, E.: Burst ORAM: Minimizing ORAM response times for bursty access patterns. In: USENIX Security (2014)"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Devadas, S., van Dijk, M., Fletcher, C.W., Ren, L., Shi, E., Wichs, D.: Onion ORAM: a constant bandwidth blowup oblivious RAM. Cryptology ePrint Archive, Report 2015\/005 (2015)","DOI":"10.1007\/978-3-662-49099-0_6"},{"issue":"4","key":"6_CR10","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/2775054.2694353","volume":"50","author":"Christopher W. Fletcher","year":"2015","unstructured":"Fletcher, C., Ren, L., Kwon, A., van Dijk, M., Devadas, S.: Freecursive ORAM: [nearly] free recursion and integrity verification for position-based oblivious RAM. In: ASPLOS (2015)","journal-title":"ACM SIGPLAN Notices"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Fletcher, C., Ren, L., Kwon, A., Van Dijk, M., Stefanov, E., Serpanos, D., Devadas, S.: A low-latency, low-area hardware oblivious RAM controller. In: FCCM (2015)","DOI":"10.1109\/FCCM.2015.58"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Fletcher, C., van Dijk, M., Devadas, S.: Secure processor architecture for encrypted computation on untrusted programs. In: STC (2012)","DOI":"10.1145\/2382536.2382540"},{"key":"6_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-39077-7_1","volume-title":"Privacy Enhancing Technologies","author":"C Gentry","year":"2013","unstructured":"Gentry, C., Goldman, K.A., Halevi, S., Julta, C., Raykova, M., Wichs, D.: Optimizing ORAM and using it efficiently for secure computation. In: De Cristofaro, E., Wright, M. (eds.) PETS 2013. LNCS, vol. 7981, pp. 1\u201318. Springer, Heidelberg (2013)"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Gentry, C., Halevi, S., Jutla, C., Raykova, M.: Private database access with he-over-oram architecture. Cryptology ePrint Archive, Report 2014\/345","DOI":"10.1007\/978-3-319-28166-7_9"},{"key":"6_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/978-3-642-55220-5_23","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"C Gentry","year":"2014","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)"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Gentry, C., Halevi, S., Raykova, M., Wichs, D.: Outsourcing private RAM computation. In: FOCS (2014)","DOI":"10.1109\/FOCS.2014.50"},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","volume-title":"Public Key Cryptography \u2013 PKC 2012","author":"C Gentry","year":"2012","unstructured":"Gentry, C., Halevi, S., Smart, N.P.: Better bootstrapping in fully homomorphic encryption. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) Public Key Cryptography \u2013 PKC 2012. LNCS, vol. 7293. Springer, Heidelberg (2012)"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: STOC (2011)","DOI":"10.1145\/1993636.1993651"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Towards a theory of software protection and simulation on Oblivious RAMs. In: STOC (1987)","DOI":"10.1145\/28395.28416"},{"key":"6_CR20","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, 431\u2013473 (1996)","journal-title":"J. ACM"},{"key":"6_CR21","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 (2012)","DOI":"10.1137\/1.9781611973099.14"},{"key":"6_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1007\/978-3-662-46800-5_25","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2015","author":"S Halevi","year":"2015","unstructured":"Halevi, S., Shoup, V.: Bootstrapping for HElib. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 641\u2013670. Springer, Heidelberg (2015)"},{"key":"6_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/978-3-540-70936-7_31","volume-title":"Theory of Cryptography","author":"Y Ishai","year":"2007","unstructured":"Ishai, Y., Paskin, A.: Evaluating branching programs on encrypted data. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 575\u2013594. Springer, Heidelberg (2007)"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Keller, M., Scholl, P.: Efficient, Oblivious data structures for MPC. Cryptology ePrint Archive, Report 2014\/137 (2014)","DOI":"10.1007\/978-3-662-45608-8_27"},{"key":"6_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. In: SODA (2012)","DOI":"10.1137\/1.9781611973099.13"},{"key":"6_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-642-19074-2_21","volume-title":"Topics in Cryptology \u2013 CT-RSA 2011","author":"R Lindner","year":"2011","unstructured":"Lindner, R., Peikert, C.: Better key sizes (and attacks) for LWE-based encryption. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 319\u2013339. Springer, Heidelberg (2011)"},{"key":"6_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1007\/11556992_23","volume-title":"Information Security","author":"H Lipmaa","year":"2005","unstructured":"Lipmaa, H.: An oblivious transfer protocol with log-squared communication. In: Zhou, J., L\u00f3pez, J., Deng, R.H., Bao, F. (eds.) ISC 2005. LNCS, vol. 3650, pp. 314\u2013328. Springer, Heidelberg (2005)"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"Liu, Y. Huang, E. Shi, J. Katz, and M. Hicks. Automating efficient RAM-model secure computation. In: Oakland (2014)","DOI":"10.1109\/SP.2014.46"},{"key":"6_CR29","unstructured":"Lorch, J.R., Parno, B., Mickens, J. W., Raykova, M., Schiffman, J.: Shroud: ensuring private access to large-scale data in the data center. In: FAST (2013)"},{"key":"6_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1007\/978-3-642-38348-9_42","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"S Lu","year":"2013","unstructured":"Lu, S., Ostrovsky, R.: How to garble RAM programs? In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 719\u2013734. Springer, Heidelberg (2013)"},{"key":"6_CR31","doi-asserted-by":"crossref","unstructured":"Maas, M., Love, E., Stefanov, E., Tiwari, M., Shi, E., Asanovic, K., Kubiatowicz, J., Song, D.: Phantom: practical oblivious computation in a secure processor. In: CCS (2013)","DOI":"10.1145\/2508859.2516692"},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"Mayberry, T., Blass, E.-O., Chan, A. H.: Efficient private file retrieval by combining ORAM and PIR. In: NDSS (2014)","DOI":"10.14722\/ndss.2014.23033"},{"key":"6_CR33","doi-asserted-by":"crossref","unstructured":"Merkle, R.C.: Protocols for public key cryptography. In: Oakland (1980)","DOI":"10.1109\/SP.1980.10006"},{"key":"6_CR34","doi-asserted-by":"crossref","unstructured":"Miller, A., Hicks, M., Katz, J., Shi, E.: Authenticated data structures, generically. In: POPL (2014)","DOI":"10.1145\/2535838.2535851"},{"key":"6_CR35","unstructured":"Moataz, T., Mayberry, T., Blass, E.-O.: Constant communication oblivious RAM. Cryptology ePrint Archive, Report 2015\/570 (2015)"},{"key":"6_CR36","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R.: Efficient computation on oblivious RAMs. In: STOC (1990)","DOI":"10.1145\/100216.100289"},{"key":"6_CR37","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology - EUROCRYPT \u201999","author":"P Paillier","year":"1999","unstructured":"Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592. Springer, Heidelberg (1999)"},{"key":"6_CR38","doi-asserted-by":"crossref","unstructured":"Ren, L., Fletcher, C., Yu, X., van Dijk, M., Devadas, S.: Integrity verification for path oblivious-RAM. In: HPEC (2013)","DOI":"10.1109\/HPEC.2013.6670339"},{"key":"6_CR39","unstructured":"Ren, L., Fletcher, C.W., Kwon, A., Stefanov, E., Shi, E., Dijk, M.V., Devadas, S.: Constants count: practical improvements to oblivious RAM. In: USENIX Security (2015)"},{"key":"6_CR40","doi-asserted-by":"crossref","unstructured":"Ren, L., Yu, X., Fletcher, C., van Dijk, M., Devadas, S.: Design space exploration and optimization of path oblivious RAM in secure processors. In: ISCA (2013)","DOI":"10.1145\/2485922.2485971"},{"key":"6_CR41","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)\n                      \n                        \n                      \n                      $$^3$$\n                      \n                        \n                          \n                            \n                            3\n                          \n                        \n                      \n                    ) Worst-Case Cost. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 197\u2013214. Springer, Heidelberg (2011)"},{"key":"6_CR42","doi-asserted-by":"crossref","unstructured":"Stefanov, E., Shi, E.: Oblivistore: high performance oblivious cloud storage. In: S&P (2013)","DOI":"10.1109\/SP.2013.25"},{"key":"6_CR43","unstructured":"Stefanov, E., Shi, E., Song, D.: Towards practical oblivious RAM. In: NDSS (2012)"},{"key":"6_CR44","doi-asserted-by":"crossref","unstructured":"Stefanov, E., van Dijk, M., Shi, E., Chan, T.-H.H., Fletcher, C., Ren, L., Yu, X., Devadas, S.: Path ORAM: an extremely simple oblivious RAM protocol. Cryptology ePrint Archive, Report 2013\/280","DOI":"10.1145\/2508859.2516660"},{"key":"6_CR45","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 (2013)","DOI":"10.1145\/2508859.2516660"},{"key":"6_CR46","doi-asserted-by":"crossref","unstructured":"Wang, X., Nayak, K., Liu, C., Shi, E., Stefanov, E., Huang, Y.: Oblivious data structures. In: IACR (2014)","DOI":"10.1145\/2660267.2660314"},{"key":"6_CR47","doi-asserted-by":"crossref","unstructured":"Wang, X.S., Chan, T.-H.H., Shi, E.: Circuit ORAM: On tightness of the Goldreich-Ostrovsky lower bound. Cryptology ePrint Archive, Report 2014\/672","DOI":"10.1145\/2810103.2813634"},{"key":"6_CR48","doi-asserted-by":"crossref","unstructured":"Wang, X.S., Huang, Y., Chan, T.-H.H., Shelat, A., Shi, E.: Scoram: oblivious ram for secure computation. In: CCS (2014)","DOI":"10.1145\/2660267.2660365"},{"key":"6_CR49","doi-asserted-by":"crossref","unstructured":"Williams, P., Sion, R.: Single round access privacy on outsourced storage. In: CCS (2012)","DOI":"10.1145\/2382196.2382229"},{"key":"6_CR50","doi-asserted-by":"crossref","unstructured":"Williams, P., Sion, R., Tomescu, A.: Privatefs: a parallel oblivious file system. In: CCS (2012)","DOI":"10.1145\/2382196.2382299"},{"key":"6_CR51","doi-asserted-by":"crossref","unstructured":"Yu, X., Fletcher, C.W., Ren, L., van Dijk, M., Devadas, S.: Generalized external interaction with tamper-resistant hardware with bounded information leakage. In: CCSW (2013)","DOI":"10.1145\/2517488.2517498"},{"key":"6_CR52","unstructured":"Zhang, J., Ma, Q., Zhang, W., Qiao, D.: Kt-oram: a bandwidth-efficient ORAM built on k-ary tree of pir nodes. Cryptology ePrint Archive, Report 2014\/624 (2014)"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49099-0_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T20:05:54Z","timestamp":1578513954000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49099-0_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,24]]},"ISBN":["9783662490983","9783662490990"],"references-count":52,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49099-0_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,24]]},"assertion":[{"value":"24 December 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}