{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T22:03:14Z","timestamp":1742940194875,"version":"3.40.3"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319298139"},{"type":"electronic","value":"9783319298146"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-29814-6_33","type":"book-chapter","created":{"date-parts":[[2016,3,7]],"date-time":"2016-03-07T09:04:46Z","timestamp":1457341486000},"page":"393-405","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An ORAM Scheme with Improved Worst-Case Computational Overhead"],"prefix":"10.1007","author":[{"given":"Nairen","family":"Cao","sequence":"first","affiliation":[]},{"given":"Xiaoqi","family":"Yu","sequence":"additional","affiliation":[]},{"given":"Yufang","family":"Yang","sequence":"additional","affiliation":[]},{"given":"Linru","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"SiuMing","family":"Yiu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,3,5]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Arbitman, Y., Naor, M., Segev, G.: Backyard cuckoo hashing: Constant worst-case operations with a succinct representation. CoRR, abs\/0912.5424 (2009)","key":"33_CR1","DOI":"10.1109\/FOCS.2010.80"},{"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)","key":"33_CR2","DOI":"10.1007\/978-3-662-45608-8_4"},{"key":"33_CR3","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)"},{"issue":"3","key":"33_CR4","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"},{"issue":"6","key":"33_CR5","doi-asserted-by":"publisher","first-page":"27: 1","DOI":"10.1145\/2049697.2049701","volume":"58","author":"MT Goodrich","year":"2011","unstructured":"Goodrich, M.T.: Randomized shellsort: a simple data-oblivious sorting algorithm. J. ACM 58(6), 27: 1\u201327: 26 (2011)","journal-title":"J. ACM"},{"key":"33_CR6","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)"},{"doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Oblivious ram simulation with efficient worst-case access overhead. In: Proceedings of the 3rd ACM Workshop on Cloud Computing Security Workshop, CCSW 2011, New York, pp. 95\u2013100. ACM (2011)","key":"33_CR7","DOI":"10.1145\/2046660.2046680"},{"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: Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 157\u2013167. SIAM (2012)","key":"33_CR8","DOI":"10.1137\/1.9781611973099.14"},{"unstructured":"Liu, Z., Chung, K.M., Lam, H., Mitzenmacher, M.: Chernoff-hoeffding bounds for markov chains: generalized and simplified. In: ACM (1998)","key":"33_CR9"},{"unstructured":"Chung, K.-M., Pass, R.: A simple oram (2013)","key":"33_CR10"},{"doi-asserted-by":"crossref","unstructured":"Goldreich, M.T.: Towards a theory of software protection and simulation by oblivious rams. STOC (1987)","key":"33_CR11","DOI":"10.1145\/28395.28416"},{"key":"33_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/978-3-642-14623-7_27","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"B Pinkas","year":"2010","unstructured":"Pinkas, B., Reinman, T.: Oblivious RAM revisited. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 502\u2013519. Springer, Heidelberg (2010)"},{"key":"33_CR13","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/3-540-49543-6_13","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"Martin Raab","year":"1998","unstructured":"Raab, M., Steger, A.: \u201cBalls into bins\" - a simple and tight analysis. In: Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 1998, London, pp. 159\u2013170. Springer-Verlag (1998)"},{"doi-asserted-by":"crossref","unstructured":"Ostrovsky, R.: Efficient computation on oblivious rams. STOC (1990)","key":"33_CR14","DOI":"10.1145\/100216.100289"},{"key":"33_CR15","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":"Elaine Shi","year":"2011","unstructured":"Shi, Elaine, Chan, T-HHubert, Stefanov, Emil, Li, Mingfei: Oblivious RAM with o((logn)$$^\\text{3}$$) worst-case cost. In: Lee, Dong Hoon, Wang, Xiaoyun (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 197\u2013214. Springer, Heidelberg (2011)"},{"doi-asserted-by":"crossref","unstructured":"Stefanov, E., van Dijk, M., Shi, E., Fletcher, C., Ren, L., Xiangyao, Y., Devadas, S., Path oram: An extremely simple oblivious ram protocol. In: Proceedings of the ACM SIGSAC Conference on Computer & Communications Security, CCS 2013, New York, pp. 299\u2013310. ACM (2013)","key":"33_CR16","DOI":"10.1145\/2508859.2516660"},{"doi-asserted-by":"crossref","unstructured":"Wang, X., Chan, H., Shi, E.: Circuit oram: On tightness of the goldreich-ostrovsky lower bound. Cryptology ePrint Archive, Report \/672 (2014). http:\/\/eprint.iacr.org\/","key":"33_CR17","DOI":"10.1145\/2810103.2813634"},{"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: Proceedings of the 15th ACM Conference on Computer and Communications Security, CCS 2008, New York, pp. 139\u2013148. ACM (2008)","key":"33_CR18","DOI":"10.1145\/1455770.1455790"}],"container-title":["Lecture Notes in Computer Science","Information and Communications Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-29814-6_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T06:17:48Z","timestamp":1623824268000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-29814-6_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319298139","9783319298146"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-29814-6_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"5 March 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}