{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:00:28Z","timestamp":1787497228954,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"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_7","type":"book-chapter","created":{"date-parts":[[2015,12,23]],"date-time":"2015-12-23T13:42:48Z","timestamp":1450878168000},"page":"175-204","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":50,"title":["Oblivious Parallel RAM and Applications"],"prefix":"10.1007","author":[{"given":"Elette","family":"Boyle","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kai-Min","family":"Chung","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafael","family":"Pass","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,12,24]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Oblivious rams without cryptogarphic assumptions. In: STOC, pp. 181\u2013190 (2010)","DOI":"10.1145\/1806689.1806716"},{"key":"7_CR2","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 (1983)","DOI":"10.1145\/800061.808726"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"Batcher, K.E.: Sorting networks and their applications. In: Proceedings of the Spring Joint Computer Conference, AFIPS 1968 (Spring), New York, NY, USA, 30 April\u20132 May 1968, pp. 307\u2013314. ACM (1968)","DOI":"10.1145\/1468075.1468121"},{"key":"7_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1007\/978-3-662-48000-7_36","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"E Boyle","year":"2015","unstructured":"Boyle, E., Chung, K.-M., Pass, R.: Large-scale secure computation: multi-party computation for (parallel) RAM programs. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 742\u2013762. Springer, Heidelberg (2015)"},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Garg, S., Lin, H., Pass, R., Telang, S.: Succinct randomized encodings and their applications. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, pp. 439\u2013448 (2015)","DOI":"10.1145\/2746539.2746574"},{"key":"7_CR6","unstructured":"Chen, Y.-C., Chow, S.S.M., Chung, K.-M., Lai, R.W.F., Lin, W.-K., Zhou, H.-S.: Computation-trace indistinguishability obfuscation and its applications. Cryptology ePrint Archive, Report 2015\/406 (2015)"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Canetti, R., Holmgren, J., Jain, A., Vaikuntanathan, V.: Succinct garbling and indistinguishability obfuscation for RAM programs. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, pp. 429\u2013437 (2015)","DOI":"10.1145\/2746539.2746621"},{"key":"7_CR8","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)$$ 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":"7_CR9","doi-asserted-by":"crossref","unstructured":"Chen, B., Lin, H., Tessaro, S.: Oblivious parallel RAM: improved efficiency and generic constructions. Cryptology ePrint Archive (2015)","DOI":"10.1007\/978-3-662-49099-0_8"},{"key":"7_CR10","unstructured":"Chung, K.-M., Pass, R.: A simple ORAM. Cryptology ePrint Archive, Report 2013\/243 (2013)"},{"key":"7_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/978-3-642-19571-6_10","volume-title":"Theory of Cryptography","author":"I Damg\u00e5rd","year":"2011","unstructured":"Damg\u00e5rd, I., Meldgaard, S., Nielsen, J.B.: Perfectly secure oblivious RAM without random oracles. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 144\u2013163. Springer, Heidelberg (2011)"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Fletcher, C.W., van Dijk, M., Devadas, S.: A secure processor architecture for encrypted computation on untrusted programs. In: Proceedings of the Seventh ACM Workshop on Scalable Trusted Computing, STC 2012, pp. 3\u20138 (2012)","DOI":"10.1145\/2382536.2382540"},{"key":"7_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":"7_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":"7_CR15","doi-asserted-by":"crossref","unstructured":"Gentry, C., Halevi, S., Raykova, M., Wichs, D.: Outsourcing private RAM computation. In: Symposium on Foundations of Computer Science, FOCS 2014, pp. 404\u2013413 (2014)","DOI":"10.1109\/FOCS.2014.50"},{"key":"7_CR16","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: The ACM Conference on Computer and Communications Security, CCS 2012, Raleigh, NC, USA, 16\u201318 October 2012, pp. 513\u2013524 (2012)","DOI":"10.1145\/2382196.2382251"},{"key":"7_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1007\/978-3-642-40084-1_30","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"S Goldwasser","year":"2013","unstructured":"Goldwasser, S., Kalai, Y.T., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: How to run turing machines on encrypted data. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 536\u2013553. Springer, Heidelberg (2013)"},{"key":"7_CR18","doi-asserted-by":"crossref","unstructured":"Garg, S., Steve, L., Ostrovsky, R., Scafuro, A.: Garbled RAM from one-way functions. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, pp. 449\u2013458 (2015)","DOI":"10.1145\/2746539.2746593"},{"key":"7_CR19","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":"7_CR20","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Oblivious ram simulation with efficient worst-case access overhead. In: CCSW, pp. 95\u2013100 (2011)","DOI":"10.1145\/2046660.2046680"},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC, pp. 218\u2013229 (1987)","DOI":"10.1145\/28395.28420"},{"issue":"3","key":"7_CR22","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":"7_CR23","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Towards a theory of software protection and simulation by oblivious RAMs. In: STOC, pp. 182\u2013194 (1987)","DOI":"10.1145\/28395.28416"},{"key":"7_CR24","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":"7_CR25","doi-asserted-by":"crossref","unstructured":"Koppula, V., Lewko, A.B., Waters, B.: Indistinguishability obfuscation for turing machines with unbounded memory. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC, pp. 419\u2013428 (2015)","DOI":"10.1145\/2746539.2746614"},{"key":"7_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)"},{"key":"7_CR27","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, pp. 199\u2013214 (2013)"},{"key":"7_CR28","doi-asserted-by":"crossref","unstructured":"Nayak, K., Wang, X.S., Ioannidis, S., Weinsberg, U., Taft, N., Shi, E.: GraphSC: parallel secure computation made easy. In: IEEE Symposium on Security and Privacy (S&P) (2015)","DOI":"10.1109\/SP.2015.30"},{"key":"7_CR29","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Shoup, V.: Private information storage (extended abstract). In: STOC, pp. 294\u2013303 (1997)","DOI":"10.1145\/258533.258606"},{"issue":"2","key":"7_CR30","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1145\/322123.322138","volume":"26","author":"N Pippenger","year":"1979","unstructured":"Pippenger, N., Fischer, M.J.: Relations among complexity measures. J. ACM 26(2), 361\u2013381 (1979)","journal-title":"J. ACM"},{"key":"7_CR31","unstructured":"Ren, L., Fletcher, C.W., Kwon, A., Stefanov, E., Shi, E., van Dijk, M., Devadas, S.: Ring ORAM: closing the gap between small and large client storage oblivious RAM. IACR Cryptology ePrint Archive 2014:997 (2014)"},{"key":"7_CR32","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 }$$ 3 ) worst-case cost. In: Wang, X., Lee, D.H. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 197\u2013214. Springer, Heidelberg (2011)"},{"key":"7_CR33","doi-asserted-by":"crossref","unstructured":"Stefanov, E., Shi, E.: ObliviStore: high performance oblivious cloud storage. In: IEEE Symposium on Security and Privacy, pp. 253\u2013267 (2013)","DOI":"10.1109\/SP.2013.25"},{"key":"7_CR34","doi-asserted-by":"crossref","unstructured":"Stefanov, E., van Dijk, M., Shi, E., Fletcher, C.W., Ren, L., Yu, X., Devadas, S.: Path ORAM: an extremely simple oblivious RAM protocol. In: ACM Conference on Computer and Communications Security, pp. 299\u2013310 (2013)","DOI":"10.1145\/2508859.2516660"},{"key":"7_CR35","doi-asserted-by":"crossref","unstructured":"Wang, X.S., Hubert Chan, T.-H., Shi, E.: Circuit ORAM: on tightness of the goldreich-ostrovsky lower bound. IACR Cryptology ePrint Archive 2014:672 (2014)","DOI":"10.1145\/2810103.2813634"},{"key":"7_CR36","doi-asserted-by":"crossref","unstructured":"Wang, X.S., Huang, Y., Hubert 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, pp. 191\u2013202 (2014)","DOI":"10.1145\/2660267.2660365"},{"key":"7_CR37","doi-asserted-by":"crossref","unstructured":"Williams, P., Sion, R., Tomescu, A.: PrivateFS: a parallel oblivious file system. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security, CCS 2012, pp. 977\u2013988 (2012)","DOI":"10.1145\/2382196.2382299"},{"key":"7_CR38","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Protocols for secure computations (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 160\u2013164 (1982)","DOI":"10.1109\/SFCS.1982.38"}],"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_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,30]],"date-time":"2022-05-30T12:24:35Z","timestamp":1653913475000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49099-0_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,24]]},"ISBN":["9783662490983","9783662490990"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49099-0_7","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"}}]}}