{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T22:13:15Z","timestamp":1791324795067,"version":"4.3.1"},"publisher-location":"Berlin, Heidelberg","reference-count":49,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662487969","type":"print"},{"value":"9783662487976","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-662-48797-6_15","type":"book-chapter","created":{"date-parts":[[2015,11,26]],"date-time":"2015-11-26T05:09:27Z","timestamp":1448514567000},"page":"337-359","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Oblivious Network RAM and Leveraging Parallelism to Achieve Obliviousness"],"prefix":"10.1007","author":[{"given":"Dana","family":"Dachman-Soled","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chang","family":"Liu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Charalampos","family":"Papamanthou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Uzi","family":"Vishkin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,1,8]]},"reference":[{"key":"15_CR1","unstructured":"Intel SGX for dummies (intel SGX design objectives). https:\/\/software.intel.com\/en-us\/blogs\/2013\/09\/26\/protecting-application-secrets-with-intel-sgx"},{"key":"15_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-642-02927-1_11","volume-title":"Automata, Languages and Programming","author":"Y Arbitman","year":"2009","unstructured":"Arbitman, Y., Naor, M., Segev, G.: De-amortized cuckoo hashing: provable worst-case performance and experimental results. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 107\u2013118. Springer, Heidelberg (2009)"},{"issue":"3","key":"15_CR3","doi-asserted-by":"publisher","first-page":"752","DOI":"10.1109\/TKDE.2013.38","volume":"26","author":"S Bajaj","year":"2014","unstructured":"Bajaj, S., Sion, R.: Trusteddb: a trusted hardware-based database with privacy and data confidentiality. IEEE Trans. Knowl. Data Eng. 26(3), 752\u2013765 (2014)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"1","key":"15_CR4","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1006\/inco.1995.1159","volume":"123","author":"H Bast","year":"1995","unstructured":"Bast, H., Hagerup, T.: Fast parallel space allocation, estimation, and integer sorting. Inf. Comput. 123(1), 72\u2013110 (1995)","journal-title":"Inf. Comput."},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Bast, H., Hagerup, T.: Fast and reliable parallel hashing. In: SPAA, pp. 50\u201361 (1991)","DOI":"10.1145\/113379.113384"},{"key":"15_CR6","unstructured":"Boneh, D., Mazieres, D., Popa, R.A.: Remote oblivious storage: making oblivious RAM practical (2011). http:\/\/dspace.mit.edu\/bitstream\/handle\/1721.1\/62006\/MIT-CSAIL-TR-2011-018.pdf"},{"key":"15_CR7","unstructured":"Boyle, E., Chung, K.-M., Pass, R.: Oblivious parallel RAM. http:\/\/eprint.iacr.org\/2014\/594.pdf"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Chung, K.-M., Liu, Z., Pass, R.: Statistically-secure oram with $$\\tilde{O}(\\log ^2 n)$$ overhead. CoRR, abs\/1307.3699 (2013)","DOI":"10.1007\/978-3-662-45608-8_4"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Fletcher, C.W., van Dijk, M., Devadas, S.: A secure processor architecture for encrypted computation on untrusted programs. In: STC (2012)","DOI":"10.1145\/2382536.2382540"},{"key":"15_CR10","unstructured":"Fletcher, C.W., Ren, L., Kwon, A., Van Dijk, M., Stefanov, E., Devadas, S.: Tiny ORAM: a low-latency, low-area hardware ORAM controller with integrity verification"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Fletcher, C.W., Ren, L., Kwon, A., van Dijk, M., Stefanov, E., Devadas, S.: RAW path ORAM: a low-latency, low-area hardware ORAM controller with integrity verification. IACR Cryptology ePrint Archive 2014:431 (2014)","DOI":"10.1109\/FCCM.2015.58"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Fletcher, C.W., Ren, L., Yu, X., van Dijk, M., Khan, O., Devadas, S.: Suppressing the oblivious RAM timing channel while making information leakage and program efficiency trade-offs. In: HPCA, pp. 213\u2013224 (2014)","DOI":"10.1109\/HPCA.2014.6835932"},{"key":"15_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":"15_CR14","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":"15_CR15","unstructured":"Gentry, C., Halevi, S., Raykova, M., Wichs, D.: Garbled RAM revisited, part i. Cryptology ePrint Archive, Report 2014\/082 (2014). http:\/\/eprint.iacr.org\/"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Gentry, C., Halevi, S., Raykova, M., Wichs, D.: Outsourcing private RAM computation. IACR Cryptology ePrint Archive 2014:148 (2014)","DOI":"10.1109\/FOCS.2014.50"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Gil, J., Matias, Y., Vishkin, U.: Towards a theory of nearly constant time parallel algorithms. In: 32nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 698\u2013710 (1991)","DOI":"10.1109\/SFCS.1991.185438"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Towards a theory of software protection and simulation by oblivious RAMs. In: ACM Symposium on Theory of Computing (STOC) (1987)","DOI":"10.1145\/28395.28416"},{"key":"15_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 43, 431\u2013473 (1996)","journal-title":"J. ACM"},{"key":"15_CR20","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, Part II. LNCS, vol. 6756, pp. 576\u2013587. Springer, Heidelberg (2011)"},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Practical oblivious storage. In: ACM Conference on Data and Application Security and Privacy (CODASPY) (2012)","DOI":"10.1145\/2133601.2133604"},{"key":"15_CR22","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":"15_CR23","doi-asserted-by":"crossref","unstructured":"Dov Gordon, S., Katz, J., Kolesnikov, V., Krell, F., Malkin, T., Raykova, M., Vahlis, Y.: Secure two-party computation in sublinear (amortized) time. In: ACM CCS (2012)","DOI":"10.1145\/2382196.2382251"},{"key":"15_CR24","series-title":"Lecture Notes in Computer Science","first-page":"259","volume-title":"STACS 92","author":"T Hagerup","year":"1992","unstructured":"Hagerup, T.: The log-star revolution. In: Finkel, A., Jantzen, M. (eds.) STACS 1992. LNCS, vol. 577, pp. 259\u2013278. Springer, Heidelberg (1992)"},{"key":"15_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":"15_CR26","doi-asserted-by":"crossref","unstructured":"Liu, C., Huang, Y., Shi, E., Katz, J., Hicks, M.: Automating efficient ram-model secure computation. In: IEEE S & P. IEEE Computer Society (2014)","DOI":"10.1109\/SP.2014.46"},{"key":"15_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":"15_CR28","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":"15_CR29","unstructured":"Lu, S., Ostrovsky, R.: Garbled RAM revisited, part ii. Cryptology ePrint Archive, Report 2014\/083 (2014). http:\/\/eprint.iacr.org\/"},{"key":"15_CR30","doi-asserted-by":"crossref","unstructured":"Maas, M., Love, E., Stefanov, E., Tiwari, M., Shi, E., Asanovic, K., Kubiatowicz, J.,\u00a0Song, D.: Phantom: practical oblivious computation in a secure processor. In: CCS (2013)","DOI":"10.1145\/2508859.2516692"},{"key":"15_CR31","unstructured":"Maas, M., Love, E., Stefanov, E., Tiwari, M., Shi, E., Asanovic, K., Kubiatowicz, J., Song, D.: A high-performance oblivious RAM controller on the convey HC-2ex heterogeneous computing platform. In: Workshop on the Intersections of Computer Architecture and Reconfigurable Logic (CARL) (2013)"},{"key":"15_CR32","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/BF00264615","volume":"21","author":"K Mehlhorn","year":"1984","unstructured":"Mehlhorn, K., Vishkin, U.: Randomized and deterministic simulations of prams by parallel machines with restricted granularity of parallel memories. Acta Inf. 21, 339\u2013374 (1984)","journal-title":"Acta Inf."},{"key":"15_CR33","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Shoup, V.: Private information storage (extended abstract). In: ACM Symposium on Theory of Computing (STOC) (1997)","DOI":"10.1145\/258533.258606"},{"issue":"2","key":"15_CR34","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":"15_CR35","doi-asserted-by":"crossref","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. In: ISCA, pp. 571\u2013582 (2013)","DOI":"10.1145\/2508148.2485971"},{"key":"15_CR36","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) $$^\\text{3 }$$ ) worst-case cost. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 197\u2013214. Springer, Heidelberg (2011)"},{"key":"15_CR37","doi-asserted-by":"crossref","unstructured":"Stefanov, E., Shi, E.: Oblivistore: high performance oblivious cloud storage. In: IEEE Symposium on Security and Privacy (S & P) (2013)","DOI":"10.1109\/SP.2013.25"},{"key":"15_CR38","unstructured":"Stefanov, E., Shi, E., Song, D.: Towards practical oblivious RAM. In: NDSS (2012)"},{"key":"15_CR39","doi-asserted-by":"crossref","unstructured":"Stefanov, E., van Dijk, M., Shi, E., Hubert Chan, T.-H., Fletcher, C., Ren, L., Yu, X., Devadas, S.: Path ORAM: an extremely simple oblivious RAM protocol. In: ACM CCS (2013)","DOI":"10.1145\/2508859.2516660"},{"key":"15_CR40","doi-asserted-by":"crossref","unstructured":"Edward Suh, G., Clarke, D., Gassend, B., van Dijk, M., Devadas, S.: Aegis: architecture for tamper-evident and tamper-resistant processing. In: International Conference on Supercomputing, ICS 2003, pp. 160\u2013171 (2003)","DOI":"10.1145\/782814.782838"},{"issue":"5","key":"15_CR41","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/384264.379237","volume":"34","author":"DLC Thekkath","year":"2000","unstructured":"Thekkath, D.L.C., Mitchell, M., Lincoln, P., Boneh, D., Mitchell, J., Horowitz, M.: Architectural support for copy and tamper resistant software. SIGOPS Oper. Syst. Rev. 34(5), 168\u2013177 (2000)","journal-title":"SIGOPS Oper. Syst. Rev."},{"issue":"9","key":"15_CR42","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1145\/234215.234475","volume":"39","author":"U Vishkin","year":"1996","unstructured":"Vishkin, U.: Can parallel algorithms enhance seriel implementation? Commun. ACM 39(9), 88\u201391 (1996)","journal-title":"Commun. ACM"},{"key":"15_CR43","doi-asserted-by":"crossref","unstructured":"Wang, X.S., Hubert Chan, T.-H., Shi, E.: Circuit ORAM: on tightness of the goldreich-ostrovksy lower bound. http:\/\/eprint.iacr.org\/2014\/672.pdf","DOI":"10.1145\/2810103.2813634"},{"key":"15_CR44","doi-asserted-by":"crossref","unstructured":"Wang, X.S., Huang, Y., Chan, H.T-H., shelat, a., Shi, E.: Scoram: oblivious ram for secure computation. http:\/\/eprint.iacr.org\/2014\/671.pdf","DOI":"10.1145\/2660267.2660365"},{"key":"15_CR45","unstructured":"Williams, P., Sion, R.: Usable PIR. In: Network and Distributed System Security Symposium (NDSS) (2008)"},{"key":"15_CR46","unstructured":"Williams, P., Sion, R.: SR-ORAM: single round-trip oblivious RAM. In: ACM Conference on Computer and Communications Security (CCS) (2012)"},{"key":"15_CR47","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: CCS (2008)","DOI":"10.1145\/1455770.1455790"},{"key":"15_CR48","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":"15_CR49","doi-asserted-by":"crossref","unstructured":"Yu, X., Haider, S.K., Ren, L., Fletcher, C.W., Kwon, A., van Dijk, M., Devadas, S.: Proram: dynamic prefetcher for oblivious RAM. In: Proceedings of the 42nd Annual International Symposium on Computer Architecture, Portland, OR, USA, 13\u201317 June 2015, pp. 616\u2013628 (2015)","DOI":"10.1145\/2872887.2750413"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology -- ASIACRYPT 2015"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48797-6_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T15:12:52Z","timestamp":1748704372000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48797-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662487969","9783662487976"],"references-count":49,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48797-6_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"8 January 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}