{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,8,25]],"date-time":"2022-08-25T15:49:11Z","timestamp":1661442551880},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,8,9]],"date-time":"2018-08-09T00:00:00Z","timestamp":1533772800000},"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":["J Cryptol"],"published-print":{"date-parts":[[2019,7]]},"DOI":"10.1007\/s00145-018-9301-4","type":"journal-article","created":{"date-parts":[[2018,8,9]],"date-time":"2018-08-09T16:27:29Z","timestamp":1533832049000},"page":"941-972","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Oblivious Network RAM and Leveraging Parallelism to Achieve Obliviousness"],"prefix":"10.1007","volume":"32","author":[{"given":"Dana","family":"Dachman-Soled","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chang","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charalampos","family":"Papamanthou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Uzi","family":"Vishkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,9]]},"reference":[{"key":"9301_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon, O. Goldreich, Y. Mansour. Almost k-wise independence versus k-wise independence. Inf. Process. Lett.\n                           88(3), 107\u2013110 (2003)","DOI":"10.1016\/S0020-0190(03)00359-4"},{"key":"9301_CR2","unstructured":"Y. Arbitman, M. Naor, G. Segev. De-amortized cuckoo hashing: provable worst-case performance and experimental results, in Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5\u201312, 2009, Proceedings, Part I (2009), pp. 107\u2013118"},{"issue":"3","key":"9301_CR3","doi-asserted-by":"publisher","first-page":"752","DOI":"10.1109\/TKDE.2013.38","volume":"26","author":"Sumeet Bajaj","year":"2014","unstructured":"S. Bajaj, R. Sion. Trusteddb: a trusted hardware-based database with privacy and data confidentiality. IEEE Trans. Knowl. Data Eng.\n                           26(3), 752\u2013765 (2014)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"9301_CR4","doi-asserted-by":"crossref","unstructured":"H. Bast, T. Hagerup. Fast parallel space allocation, estimation, and integer sorting. Inf. Comput.\n                           123(1), 72\u2013110 (1995)","DOI":"10.1006\/inco.1995.1159"},{"key":"9301_CR5","unstructured":"H. Bast, T. Hagerup. Fast and reliable parallel hashing, in SPAA (1991), pp. 50\u201361"},{"key":"9301_CR6","unstructured":"D. Boneh, D. Mazieres, R.A. Popa. Remote oblivious storage: making oblivious RAM practical (2011). \n                    http:\/\/dspace.mit.edu\/bitstream\/handle\/1721.1\/62006\/MIT-CSAIL-TR-2011-018.pdf"},{"key":"9301_CR7","unstructured":"E. Boyle, K.-M. Chung, R. Pass. Oblivious parallel ram. \n                    https:\/\/eprint.iacr.org\/2014\/594.pdf"},{"key":"9301_CR8","doi-asserted-by":"crossref","unstructured":"K.-M. Chung, Z. Liu, R. Pass. Statistically-secure oram with \n                    \n                      \n                    \n                    $$\\tilde{O}(\\log ^2 n)$$\n                    \n                      \n                        \n                          \n                            O\n                            ~\n                          \n                          \n                            (\n                            \n                              log\n                              2\n                            \n                            n\n                            )\n                          \n                        \n                      \n                    \n                   overhead. CoRR. \n                    arXiv:1307.3699\n                    \n                   (2013)","DOI":"10.1007\/978-3-662-45608-8_4"},{"key":"9301_CR9","doi-asserted-by":"crossref","unstructured":"C.W. Fletcher, M.\u00a0van Dijk, S. Devadas. A secure processor architecture for encrypted computation on untrusted programs, in STC (2012)","DOI":"10.1145\/2382536.2382540"},{"key":"9301_CR10","doi-asserted-by":"publisher","unstructured":"C.W. Fletcher, L. Ren, A. Kwon, M. Van Dijk, E. Stefanov, D.N. Serpanos, S. Devadas. A low-latency, low-area hardware oblivious RAM controller, in 23rd IEEE Annual International Symposium on Field-Programmable Custom Computing Machines, FCCM 2015, Vancouver, BC, Canada, May 2\u20136 (2015), pp. 215\u2013222. \n                    https:\/\/doi.org\/10.1109\/FCCM.2015.58","DOI":"10.1109\/FCCM.2015.58"},{"key":"9301_CR11","first-page":"431","volume":"2014","author":"Christopher W Fletcher","year":"2014","unstructured":"C.W. Fletcher, L. Ren, A. Kwon, M. van Dijk, E. Stefanov, S. Devadas. RAW path ORAM: a low-latency, low-area hardware ORAM controller with integrity verification, in IACR Cryptology ePrint Archive, vol. 431 (2014)","journal-title":"IACR Cryptology ePrint Archive"},{"key":"9301_CR12","unstructured":"C.W. Fletcher, L. Ren, X. Yu, M. van Dijk, O. Khan, S. Devadas. Suppressing the oblivious RAM timing channel while making information leakage and program efficiency trade-offs, in HPCA (2014), pp. 213\u2013224"},{"key":"9301_CR13","doi-asserted-by":"crossref","unstructured":"C. Gentry, K.A. Goldman, S. Halevi, C.S. Jutla, M. Raykova, D. Wichs. 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":"9301_CR14","unstructured":"C. Gentry, S. Halevi, S. Lu, R. Ostrovsky, M. Raykova, D. Wichs. Garbled ram revisited, in Advances in Cryptology\u2014EUROCRYPT 2014, vol. 8441 (2014), pp. 405\u2013422"},{"key":"9301_CR15","doi-asserted-by":"crossref","unstructured":"C. Gentry, S. Halevi, M. Raykova, D. Wichs. Garbled ram revisited, part i. Cryptology ePrint Archive, Report 2014\/082, 2014. \n                    http:\/\/eprint.iacr.org\/","DOI":"10.1007\/978-3-642-55220-5_23"},{"key":"9301_CR16","first-page":"148","volume":"2014","author":"Craig Gentry","year":"2014","unstructured":"C. Gentry, S. Halevi, M. Raykova, D. Wichs. Outsourcing private ram computation. IACR Cryptology ePrint Archive, vol. 148 (2014)","journal-title":"IACR Cryptology ePrint Archive"},{"issue":"2","key":"9301_CR17","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1109\/TPDS.2017.2754376","volume":"29","author":"F Ghanim","year":"2018","unstructured":"F. Ghanim, U. Vishkin, R. Barua. Easy PRAM-based high-performance parallel programming with ICE. IEEE Trans. Parallel Distrib. Syst.\n                           29(2), 377\u2013390 (2018). \n                    https:\/\/doi.org\/10.1109\/TPDS.2017.2754376","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"9301_CR18","unstructured":"J. Gil, Y. Matias, U. Vishkin. Towards a theory of nearly constant time parallel algorithms, in 32nd Annual Symposium on Foundations of Computer Science (FOCS) (1991), pp. 698\u2013710"},{"key":"9301_CR19","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich. 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":"9301_CR20","doi-asserted-by":"crossref","unstructured":"O. Goldreich, R. Ostrovsky. Software protection and simulation on oblivious RAMs. J. ACM\n                           43(3), 431\u2013473 (1996)","DOI":"10.1145\/233551.233553"},{"key":"9301_CR21","unstructured":"M.T. Goodrich, D.S. Hirschberg, M. Mitzenmacher, J. Thaler. Fully de-amortized cuckoo hashing for cache-oblivious dictionaries and multimaps. CoRR. \n                    arXiv:1107.4378\n                    \n                   (2011)"},{"key":"9301_CR22","doi-asserted-by":"crossref","unstructured":"M.T. Goodrich, D.S. Hirschberg, M. Mitzenmacher, J. Thaler. Cache-oblivious dictionaries and multimaps with negligible failure probability, in G. Even, D. Rawitz, editors, Design and Analysis of Algorithms\u2014First Mediterranean Conference on Algorithms, MedAlg 2012, Kibbutz Ein Gedi, Israel, December 3\u20135, 2012. Proceedings. LNCS, vol. 7659 (Springer, 2012), pp. 203\u2013218","DOI":"10.1007\/978-3-642-34862-4_15"},{"key":"9301_CR23","doi-asserted-by":"crossref","unstructured":"M.T. Goodrich, M. Mitzenmacher. Privacy-preserving access of outsourced data via oblivious RAM simulation, in ICALP (2011)","DOI":"10.1137\/1.9781611973099.14"},{"key":"9301_CR24","doi-asserted-by":"crossref","unstructured":"M.T. Goodrich, M. Mitzenmacher, O. Ohrimenko, R. Tamassia. Practical oblivious storage, in ACM Conference on Data and Application Security and Privacy (CODASPY) (2012)","DOI":"10.1145\/2133601.2133604"},{"key":"9301_CR25","doi-asserted-by":"crossref","unstructured":"M.T. Goodrich, M. Mitzenmacher, O. Ohrimenko, R. Tamassia. Privacy-preserving group data access via stateless oblivious RAM simulation, in SODA (2012)","DOI":"10.1137\/1.9781611973099.14"},{"key":"9301_CR26","doi-asserted-by":"crossref","unstructured":"S.D. Gordon, J. Katz, V. Kolesnikov, F. Krell, T. Malkin, M. Raykova, Y. Vahlis. Secure two-party computation in sublinear (amortized) time, in ACM CCS (2012)","DOI":"10.1145\/2382196.2382251"},{"key":"9301_CR27","unstructured":"T. Hagerup. The log-star revolution, in STACS 92, 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13\u201315, 1992, Proceedings (1992), pp. 259\u2013278"},{"key":"9301_CR28","unstructured":"A. Kirsch, M. Mitzenmacher, U. Wieder. More robust hashing: cuckoo hashing with a stash, in Algorithms\u2014ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15\u201317, 2008. Proceedings (2008), pp. 611\u2013622."},{"key":"9301_CR29","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz, S. Lu, R. Ostrovsky. On the (in)security of hash-based oblivious RAM and a new balancing scheme, in SODA (2012)","DOI":"10.1137\/1.9781611973099.13"},{"key":"9301_CR30","doi-asserted-by":"crossref","unstructured":"C. Liu, Y. Huang, E. Shi, J. Katz, M. Hicks. Automating efficient ram-model secure computation, in IEEE S & P (IEEE Computer Society, 2014)","DOI":"10.1109\/SP.2014.46"},{"key":"9301_CR31","doi-asserted-by":"crossref","unstructured":"S. Lu, R. Ostrovsky. Distributed oblivious RAM for secure two-party computation, in Theory of Cryptography Conference (TCC) (2013)","DOI":"10.1007\/978-3-642-36594-2_22"},{"key":"9301_CR32","unstructured":"S. Lu, R. Ostrovsky. How to garble ram programs, in EUROCRYPT (2013), pp. 719\u2013734"},{"key":"9301_CR33","unstructured":"S. Lu, R. Ostrovsky. Garbled ram revisited, part ii. Cryptology ePrint Archive, Report 2014\/083, 2014. \n                    http:\/\/eprint.iacr.org\/"},{"key":"9301_CR34","doi-asserted-by":"crossref","unstructured":"M. Maas, E. Love, E. Stefanov, M. Tiwari, E. Shi, K. Asanovic, J. Kubiatowicz, D. Song. Phantom: practical oblivious computation in a secure processor, in CCS (2013)","DOI":"10.1145\/2508859.2516692"},{"key":"9301_CR35","unstructured":"M. Maas, E. Love, E. Stefanov, M. Tiwari, E. Shi, K. Asanovic, J. Kubiatowicz, D. Song. 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":"9301_CR36","unstructured":"R. Meka, O. Reingold, G.N. Rothblum, R.D. Rothblum. Fast pseudorandomness for independence and load balancing\u2014(extended abstract), in Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8\u201311, 2014, Proceedings, Part I (2014), pp. 859\u2013870"},{"key":"9301_CR37","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky, V. Shoup. Private information storage (extended abstract), in ACM Symposium on Theory of Computing (STOC) (1997)","DOI":"10.1145\/258533.258606"},{"key":"9301_CR38","doi-asserted-by":"crossref","unstructured":"R. Pagh, F.F. Rodler. Cuckoo hashing. J. Algorithms\n                           51(2), 122\u2013144 (2004)","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"9301_CR39","unstructured":"L. Ren, X. Yu, C.W. Fletcher, M. van Dijk, S. Devadas. Design space exploration and optimization of path oblivious RAM in secure processors, in ISCA (2013), pp. 571\u2013582"},{"issue":"2","key":"9301_CR40","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/S089548019223872X","volume":"8","author":"Jeanette P Schmidt","year":"1995","unstructured":"J.P. Schmidt, A. Siegel, A. Srinivasan. Chernoff-hoeffding bounds for applications with limited independence. SIAM J. Discrete Math.\n                           8(2), 223\u2013250 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"9301_CR41","unstructured":"E. Shi, T.-H. Hubert Chan, E. Stefanov, M. Li. Oblivious RAM with \n                    \n                      \n                    \n                    $$O((\\log N)^3)$$\n                    \n                      \n                        \n                          O\n                          (\n                          \n                            \n                              (\n                              log\n                              N\n                              )\n                            \n                            3\n                          \n                          )\n                        \n                      \n                    \n                   worst-case cost, in ASIACRYPT (2011)"},{"key":"9301_CR42","doi-asserted-by":"crossref","unstructured":"E. Stefanov, E. Shi. Oblivistore: high performance oblivious cloud storage, in IEEE Symposium on Security and Privacy (S & P) (2013)","DOI":"10.1109\/SP.2013.25"},{"key":"9301_CR43","unstructured":"E. Stefanov, E. Shi, D. Song. Towards practical oblivious RAM, in NDSS (2012)"},{"key":"9301_CR44","doi-asserted-by":"crossref","unstructured":"E. Stefanov, M. van Dijk, E. Shi, T.-H.H. Chan, C. Fletcher, L. Ren, X. Yu, S. Devadas. Path ORAM: an extremely simple oblivious ram protocol, in ACM CCS (2013)","DOI":"10.1145\/2508859.2516660"},{"issue":"9","key":"9301_CR45","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1145\/234215.234475","volume":"39","author":"Uzi Vishkin","year":"1996","unstructured":"U. Vishkin. Can parallel algorithms enhance seriel implementation? Commun. ACM\n                           39(9), 88\u201391 (1996)","journal-title":"Commun. ACM"},{"issue":"1","key":"9301_CR46","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1145\/1866739.1866757","volume":"54","author":"Uzi Vishkin","year":"2011","unstructured":"U. Vishkin. Using simple abstraction to reinvent computing for parallelism. Commun. ACM\n                           54(1), 75\u201385 (2011)","journal-title":"Commun. ACM"},{"key":"9301_CR47","doi-asserted-by":"crossref","unstructured":"X.S. Wang, T.-H.H. Chan, E. Shi. Circuit ORAM: on tightness of the Goldreich\u2013Ostrovksy lower bound. \n                    http:\/\/eprint.iacr.org\/2014\/672.pdf","DOI":"10.1145\/2810103.2813634"},{"key":"9301_CR48","doi-asserted-by":"crossref","unstructured":"X.S. Wang, Y. Huang, T.-H.H. Chan, A. Shelat, E. Shi. Scoram: oblivious ram for secure computation. \n                    http:\/\/eprint.iacr.org\/2014\/671.pdf","DOI":"10.1145\/2660267.2660365"},{"key":"9301_CR49","unstructured":"P. Williams, R. Sion. Usable PIR, in Network and Distributed System Security Symposium (NDSS) (2008)"},{"key":"9301_CR50","unstructured":"P. Williams, R. Sion. SR-ORAM: single round-trip oblivious ram, in ACM Conference on Computer and Communications Security (CCS) (2012)"},{"key":"9301_CR51","doi-asserted-by":"crossref","unstructured":"P. Williams, R. Sion, B. Carbunar. Building castles out of mud: Practical access pattern privacy and correctness on untrusted storage, in CCS (2008)","DOI":"10.1145\/1455770.1455790"},{"key":"9301_CR52","doi-asserted-by":"crossref","unstructured":"P. Williams, R. Sion, A. Tomescu. PrivateFS: A parallel oblivious file system, in CCS (2012)","DOI":"10.1145\/2382196.2382299"},{"key":"9301_CR53","unstructured":"X. Yu, S.K. Haider, L. Ren, C.W. Fletcher, A. Kwon, M. van Dijk, S. Devadas. Program: dynamic prefetcher for oblivious RAM, in Proceedings of the 42nd Annual International Symposium on Computer Architecture, Portland, OR, USA, June 13\u201317, 2015 (2015), pp. 616\u2013628"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-018-9301-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-018-9301-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-018-9301-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T08:15:01Z","timestamp":1586333701000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-018-9301-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,9]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["9301"],"URL":"https:\/\/doi.org\/10.1007\/s00145-018-9301-4","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,9]]},"assertion":[{"value":"13 December 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 August 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}