{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T18:26:10Z","timestamp":1770747970699,"version":"3.49.0"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319968834","type":"print"},{"value":"9783319968841","type":"electronic"}],"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.springernature.com\/gp\/researchers\/text-and-data-mining"},{"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.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-96884-1_13","type":"book-chapter","created":{"date-parts":[[2018,7,24]],"date-time":"2018-07-24T10:33:49Z","timestamp":1532428429000},"page":"371-406","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":50,"title":["Searchable Encryption with Optimal Locality: Achieving Sublogarithmic Read Efficiency"],"prefix":"10.1007","author":[{"given":"Ioannis","family":"Demertzis","sequence":"first","affiliation":[]},{"given":"Dimitrios","family":"Papadopoulos","sequence":"additional","affiliation":[]},{"given":"Charalampos","family":"Papamanthou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,7,25]]},"reference":[{"key":"13_CR1","unstructured":"Crimes 2001 to present (City of Chicago). https:\/\/data.cityofchicago.org\/public-safety\/crimes-2001-to-present\/ijzp-q8t2"},{"key":"13_CR2","unstructured":"Enron Email Dataset. https:\/\/www.cs.cmu.edu\/.\/enron\/"},{"key":"13_CR3","unstructured":"TPC-H Dataset. http:\/\/www.tpc.org\/tpch\/"},{"key":"13_CR4","unstructured":"USPS Dataset. http:\/\/www.app.com"},{"key":"13_CR5","unstructured":"Asharov, G., Chan, T.H., Nayak, K., Pass, R., Ren, L., Shi, E.: Oblivious computation with data locality. IACR Cryptology ePrint (2017)"},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Asharov, G., Naor, M., Segev, G., Shahaf, I.: Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations. In: STOC (2016)","DOI":"10.1145\/2897518.2897562"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"Asharov, G., Segev, G., Shahaf, I.: Tight tradeoffs in searchable symmetric encryption. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 407\u2013436. Springer, Heidelberg (2018)","DOI":"10.1007\/978-3-319-96884-1_14"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Batcher, K.E.: Sorting networks and their applications. In: AFIPS (1968)","DOI":"10.1145\/1468075.1468121"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Czumaj, A., Steger, A., V\u00f6cking, B.: Balanced allocations: the heavily loaded case. In: STOC (2000)","DOI":"10.1145\/335305.335411"},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Cash, D., et al.: Dynamic searchable encryption in very-large databases: data structures and implementation. In: NDSS (2014)","DOI":"10.14722\/ndss.2014.23264"},{"key":"13_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/978-3-642-55220-5_20","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"D Cash","year":"2014","unstructured":"Cash, D., Tessaro, S.: The locality of searchable symmetric encryption. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 351\u2013368. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-55220-5_20"},{"issue":"5","key":"13_CR12","doi-asserted-by":"publisher","first-page":"895","DOI":"10.3233\/JCS-2011-0426","volume":"9","author":"R Curtmola","year":"2011","unstructured":"Curtmola, R., Garay, J.A., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. JCS 9(5), 895\u2013934 (2011)","journal-title":"JCS"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Demertzis, I., Papadopoulos, D., Papamanthou, C.: Searchable encryption with optimal locality: achieving sublogarithmic read efficiency. In: CRYPTO 2018 (2018). https:\/\/eprint.iacr.org\/2017\/749","DOI":"10.1007\/978-3-319-96884-1_13"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Demertzis, I., Papadopoulos, S., Papapetrou, O., Deligiannakis, A., Garofalakis, M.: Practical private range search revisited. In: SIGMOD (2016)","DOI":"10.1145\/2882903.2882911"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Demertzis, I., Papadopoulos, S., Papapetrou, O., Deligiannakis, A., Garofalakis, M., Papamanthou, C.: Practical private range search in depth. In: TODS (2018)","DOI":"10.1145\/3167971"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Demertzis, I., Papamanthou, C.: Fast searchable encryption with tunable locality. In: SIGMOD (2017)","DOI":"10.1145\/3035918.3064057"},{"issue":"2","key":"13_CR17","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M","volume":"13","author":"DP Dubhashi","year":"1998","unstructured":"Dubhashi, D.P., Ranjan, D.: Balls and bins: a study in negative dependence. Random Struct. Algorithms 13(2), 99\u2013124 (1998)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"13_CR18","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":"13_CR19","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T.: Data-oblivious external-memory algorithms for the compaction, selection, and sorting of outsourced data. In: SPAA (2011)","DOI":"10.1145\/1989493.1989555"},{"key":"13_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. LNCS, vol. 6756, pp. 576\u2013587. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22012-8_46"},{"key":"13_CR21","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 (2011)","DOI":"10.1145\/2046660.2046680"},{"key":"13_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1007\/978-3-540-74619-5_28","volume-title":"Fast Software Encryption","author":"L Granboulan","year":"2007","unstructured":"Granboulan, L., Pornin, T.: Perfect block ciphers with small blocks. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 452\u2013465. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-74619-5_28"},{"key":"13_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-642-39884-1_22","volume-title":"Financial Cryptography and Data Security","author":"S Kamara","year":"2013","unstructured":"Kamara, S., Papamanthou, C.: Parallel and dynamic searchable symmetric encryption. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 258\u2013274. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39884-1_22"},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: CCS (2012)","DOI":"10.1145\/2382196.2382298"},{"key":"13_CR25","doi-asserted-by":"crossref","unstructured":"Miers, I., Mohassel, P.: IO-DSSE: scaling dynamic searchable encryption to millions of indexes by improving locality. In: NDSS (2017)","DOI":"10.14722\/ndss.2017.23394"},{"key":"13_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-642-55220-5_18","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"B Morris","year":"2014","unstructured":"Morris, B., Rogaway, P.: Sometimes-recurse shuffle - almost-random permutations in logarithmic expected time. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 311\u2013326. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-55220-5_18"},{"key":"13_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1007\/978-3-662-43951-7_47","volume-title":"Automata, Languages, and Programming","author":"O Ohrimenko","year":"2014","unstructured":"Ohrimenko, O., Goodrich, M.T., Tamassia, R., Upfal, E.: The Melbourne shuffle: improving oblivious storage in the cloud. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 556\u2013567. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43951-7_47"},{"issue":"1","key":"13_CR28","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s00453-002-0987-0","volume":"35","author":"P Sanders","year":"2003","unstructured":"Sanders, P., Egner, S., Korst, J.H.M.: Fast concurrent access to parallel disks. Algorithmica 35(1), 21\u201355 (2003)","journal-title":"Algorithmica"},{"key":"13_CR29","unstructured":"Schoenmakers, L.A.: A new algorithm for the recognition of series parallel graphs. Technical report, Amsterdam, The Netherlands (1995)"},{"key":"13_CR30","unstructured":"Song, D.X., Wagner, D., Perrig, A.: Practical techniques for searches on encrypted data. In: SP (2000)"},{"key":"13_CR31","doi-asserted-by":"crossref","unstructured":"Stefanov, E., Papamanthou, C., Shi, E.: Practical dynamic searchable encryption with small leakage. In: NDSS (2014)","DOI":"10.14722\/ndss.2014.23298"},{"key":"13_CR32","unstructured":"Stefanov, E., Shi, E.: FastPRP: fast pseudo-random permutations for small domains. IACR Cryptology ePrint (2012)"},{"key":"13_CR33","doi-asserted-by":"crossref","unstructured":"Stefanov, E., et al.: Path ORAM: an extremely simple oblivious RAM protocol. In: CCS (2013)","DOI":"10.1145\/2508859.2516660"},{"key":"13_CR34","doi-asserted-by":"crossref","unstructured":"Zahur, S., et al.: Revisiting square-root ORAM: efficient random access in multi-party computation. In: SP (2016)","DOI":"10.1109\/SP.2016.21"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2018"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-96884-1_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T10:33:07Z","timestamp":1710325987000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-96884-1_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319968834","9783319968841"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-96884-1_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"25 July 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","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":"19 August 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 August 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"38","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.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"}]}}