{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T04:53:51Z","timestamp":1764305631205,"version":"3.40.3"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030038090"},{"type":"electronic","value":"9783030038106"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-03810-6_23","type":"book-chapter","created":{"date-parts":[[2018,11,7]],"date-time":"2018-11-07T21:30:29Z","timestamp":1541626229000},"page":"636-668","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Perfectly Secure Oblivious Parallel RAM"],"prefix":"10.1007","author":[{"given":"T.-H. Hubert","family":"Chan","sequence":"first","affiliation":[]},{"given":"Kartik","family":"Nayak","sequence":"additional","affiliation":[]},{"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,11,8]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: An O(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":"23_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Oblivious RAMs without cryptogrpahic assumptions. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC 2010, pp. 181\u2013190. ACM, New York (2010)","DOI":"10.1145\/1806689.1806716"},{"key":"23_CR3","unstructured":"Asharov, G., Chan, T.-H.H., Nayak, K., Pass, R., Ren, L., Shi, E.: Oblivious computation with data locality. IACR Cryptology ePrint Archive 2017:772 (2017)"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC 1988, pp. 1\u201310 (1988)","DOI":"10.1145\/62212.62213"},{"key":"23_CR5","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). https:\/\/doi.org\/10.1007\/978-3-662-48000-7_36"},{"key":"23_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/978-3-662-49099-0_7","volume-title":"Theory of Cryptography","author":"E Boyle","year":"2016","unstructured":"Boyle, E., Chung, K.-M., Pass, R.: Oblivious parallel RAM and applications. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 175\u2013204. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49099-0_7"},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1007\/978-3-319-70694-8_20","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2017","author":"T.-H. Hubert Chan","year":"2017","unstructured":"Chan, T.-H.H., Chung, K.-M., Shi, E.: On the depth of oblivious parallel RAM. In: Asiacrypt (2017)"},{"key":"23_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. In: Asiacrypt (2017)","DOI":"10.1007\/978-3-319-70694-8_23"},{"key":"23_CR9","unstructured":"Chan, T.-H.H., Nayak, K., Shi, E.: Perfectly secure oblivious parallel ram. Cryptology ePrint Archive, Report 2018\/364 (2018). https:\/\/eprint.iacr.org\/2018\/364"},{"key":"23_CR10","unstructured":"Chan, T-H.H., Shi, E.: Circuit OPRAM: a unifying framework for computationally and statistically secure ORAMs and OPRAMs. In: TCC (2017)"},{"key":"23_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-662-49099-0_8","volume-title":"Theory of Cryptography","author":"B Chen","year":"2016","unstructured":"Chen, B., Lin, H., Tessaro, S.: Oblivious parallel RAM: improved efficiency and generic constructions. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 205\u2013234. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49099-0_8"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"Chung, K.-M., Liu, Z., Pass, R.: Statistically-secure ORAM with $$\\tilde{O}(\\log ^2n)$$ overhead. In: Asiacrypt (2014)","DOI":"10.1007\/978-3-662-45608-8_4"},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/978-3-642-19571-6_10","volume-title":"Theory of Cryptography","author":"Ivan Damg\u00e5rd","year":"2011","unstructured":"Damg\u00e5rd, I., Meldgaard, S., Nielsen, J.B.: Perfectly secure oblivious RAM without random oracles. In: Theory of Cryptography Conference (TCC), pp. 144\u2013163 (2011)"},{"key":"23_CR14","unstructured":"Dautrich, J., Stefanov, E., Shi, E.: Burst ORAM: minimizing ORAM response times for bursty access patterns. In: 23rd USENIX Security Symposium (USENIX Security 14), pp. 749\u2013764, San Diego, CA, August 2014. USENIX Association"},{"key":"23_CR15","unstructured":"Demertzis, I., Papadopoulos, D., Papamanthou, C.: Searchable encryption with optimal locality: achieving sublogarithmic read efficiency. Cryptology ePrint Archive, Report 2017\/749 (2017). https:\/\/eprint.iacr.org\/2017\/749"},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"Fletcher, C.W., 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)","DOI":"10.1145\/2694344.2694353"},{"key":"23_CR17","first-page":"431","volume":"2014","author":"CW Fletcher","year":"2014","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 Cryptol. Eprint Arch. 2014, 431 (2014)","journal-title":"IACR Cryptol. Eprint Arch."},{"key":"23_CR18","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":"23_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/978-3-662-53641-4_14","volume-title":"Theory of Cryptography","author":"D Genkin","year":"2016","unstructured":"Genkin, D., Ishai, Y., Weiss, M.: Binary AMD circuits from secure multiparty computation. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9985, pp. 336\u2013366. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53641-4_14"},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Gentry, C., Goldman, K.A., Halevi, S., Jutla, C.S., Raykova, M., Wichs, D.: Optimizing ORAM and using it efficiently for secure computation. In: Privacy Enhancing Technologies Symposium (PETS) (2013)","DOI":"10.1007\/978-3-642-39077-7_1"},{"key":"23_CR21","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"},{"issue":"3","key":"23_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":"23_CR23","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1007\/978-3-642-22012-8_46","volume-title":"Automata, Languages and Programming","author":"Michael T. Goodrich","year":"2011","unstructured":"Goodrich, M.T., Mitzenmacher, M.: Privacy-preserving access of outsourced data via oblivious RAM simulation. In: International Colloquium on Automata, Languages and Programming (ICALP), pp. 576\u2013587 (2011)"},{"key":"23_CR24","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1137\/1.9781611973099.14","volume-title":"Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Michael T. Goodrich","year":"2012","unstructured":"Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Privacy-preserving group data access via stateless oblivious RAM simulation. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 157\u2013167, Philadelphia, PA, USA (2012). Society for Industrial and Applied Mathematics"},{"key":"23_CR25","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 Conference on Computer and Communications Security (CCS) (2012)","DOI":"10.1145\/2382196.2382251"},{"key":"23_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/978-3-642-20465-4_23","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"Y Ishai","year":"2011","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Prabhakaran, M., Sahai, A.: Efficient non-interactive secure computation. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 406\u2013425. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-20465-4_23"},{"key":"23_CR27","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: ACM-SIAM Symposium on Discrete Algorithms (SODA) (2012)","DOI":"10.1137\/1.9781611973099.13"},{"issue":"4","key":"23_CR28","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1145\/2775054.2694385","volume":"50","author":"C Liu","year":"2015","unstructured":"Liu, C., Harris, A., Maas, M., Hicks, M., Tiwari, M., Shi, E.: Ghostrider: a hardware-software system for memory trace oblivious computation. SIGPLAN Not. 50(4), 87\u2013101 (2015)","journal-title":"SIGPLAN Not."},{"key":"23_CR29","doi-asserted-by":"crossref","unstructured":"Liu, C., Wang, X.S., Nayak, K., Huang, Y., Shi, E.: ObliVM: a programming framework for secure computation. In: 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, 17\u201321 May 2015, pp. 359\u2013376 (2015","DOI":"10.1109\/SP.2015.29"},{"key":"23_CR30","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: ACM Conference on Computer and Communications Security (CCS) (2013)","DOI":"10.1145\/2508859.2516692"},{"key":"23_CR31","doi-asserted-by":"crossref","unstructured":"Nayak, K., et al.: HOP: hardware makes obfuscation practical. In: 24th Annual Network and Distributed System Security Symposium, NDSS (2017)","DOI":"10.14722\/ndss.2017.23349"},{"key":"23_CR32","first-page":"1141","volume":"2016","author":"K Nayak","year":"2016","unstructured":"Nayak, K., Katz, J.: An oblivious parallel RAM with $$o(log^2 n)$$ parallel runtime blowup. IACR Cryptol. Eprint Arch. 2016, 1141 (2016)","journal-title":"IACR Cryptol. Eprint Arch."},{"key":"23_CR33","doi-asserted-by":"crossref","unstructured":"Pippenger, N.: Self-routing superconcentrators. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC 1993, pp. 355\u2013361. ACM, New York (1993)","DOI":"10.1145\/167088.167195"},{"key":"23_CR34","unstructured":"Raskin, M., Simkin, M.: Oblivious RAM with small storage overhead. Cryptology ePrint Archive, Report 2018\/268 (2018). https:\/\/eprint.iacr.org\/2018\/268"},{"key":"23_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":"23_CR36","doi-asserted-by":"crossref","unstructured":"Shi, E., Chan, T.-H.H., Stefanov, E., Li, M.: Oblivious RAM with $$O(\\log ^3 N)$$ worst-case cost. In: ASIACRYPT, pp. 197\u2013214 (2011)","DOI":"10.1007\/978-3-642-25385-0_11"},{"key":"23_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":"23_CR38","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: ACM Conference on Computer and Communications Security (CCS) (2013)","DOI":"10.1145\/2508859.2516660"},{"key":"23_CR39","doi-asserted-by":"crossref","unstructured":"Wang, X.S., Chan, T-H.H., Shi, E.: Circuit ORAM: on tightness of the Goldreich-Ostrovsky lower bound. In: ACM CCS (2015)","DOI":"10.1145\/2810103.2813634"},{"key":"23_CR40","doi-asserted-by":"crossref","unstructured":"Williams, P., Sion, R., Tomescu, A.: PrivateFS: a parallel oblivious file system. In: ACM Conference on Computer and Communications Security (CCS) (2012)","DOI":"10.1145\/2382196.2382299"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-03810-6_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,7]],"date-time":"2021-11-07T01:04:30Z","timestamp":1636247070000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-03810-6_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030038090","9783030038106"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-03810-6_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"8 November 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Panaji","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 November 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 November 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcc.iacr.org\/2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}