{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,12]],"date-time":"2025-09-12T19:18:29Z","timestamp":1757704709077,"version":"3.41.0"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319968834"},{"type":"electronic","value":"9783319968841"}],"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_14","type":"book-chapter","created":{"date-parts":[[2018,7,24]],"date-time":"2018-07-24T10:33:49Z","timestamp":1532428429000},"page":"407-436","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["Tight Tradeoffs in Searchable Symmetric Encryption"],"prefix":"10.1007","author":[{"given":"Gilad","family":"Asharov","sequence":"first","affiliation":[]},{"given":"Gil","family":"Segev","sequence":"additional","affiliation":[]},{"given":"Ido","family":"Shahaf","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,7,25]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"Arbitman, Y., Naor, M., Segev, G.: Backyard cuckoo hashing: constant worst-case operations with a succinct representation. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 787\u2013796 (2010)","DOI":"10.1109\/FOCS.2010.80"},{"key":"14_CR2","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: Proceedings of the 48th Annual ACM Symposium on Theory of Computing, pp. 1101\u20131114 (2016)","DOI":"10.1145\/2897518.2897562"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Asharov, G., Segev, G., Shahaf, I.: Tight tradeoffs in searchable symmetric encryption. Cryptology ePrint Archive, Report 2018\/507 (2018). https:\/\/eprint.iacr.org\/2018\/507","DOI":"10.1007\/978-3-319-96884-1_14"},{"issue":"3","key":"14_CR4","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/s00453-013-9840-x","volume":"70","author":"M Aum\u00fcller","year":"2014","unstructured":"Aum\u00fcller, M., Dietzfelbinger, M., Woelfel, P.: Explicit and efficient hash families suffice for cuckoo hashing with a stash. Algorithmica 70(3), 428\u2013456 (2014)","journal-title":"Algorithmica"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Cash, D., Grubbs, P., Perry, J., Ristenpart, T.: Leakage-abuse attacks against searchable encryption. In: Proceedings of the 22nd ACM Conference on Computer and Communications Security, pp. 668\u2013679 (2015)","DOI":"10.1145\/2810103.2813700"},{"key":"14_CR6","doi-asserted-by":"crossref","unstructured":"Cash, D., Jaeger, J., Jarecki, S., Jutla, C.S., Krawczyk, H., Rosu, M., Steiner, M.: Dynamic searchable encryption in very-large databases: data structures and implementation. In: Proceedings of the 21st Annual Network and Distributed System Security Symposium (2014)","DOI":"10.14722\/ndss.2014.23264"},{"key":"14_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/978-3-642-40041-4_20","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"D Cash","year":"2013","unstructured":"Cash, D., Jarecki, S., Jutla, C., Krawczyk, H., Ro\u015fu, M.-C., Steiner, M.: Highly-scalable searchable symmetric encryption with support for boolean queries. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 353\u2013373. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40041-4_20"},{"key":"14_CR8","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"},{"key":"14_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1007\/11496137_30","volume-title":"Applied Cryptography and Network Security","author":"Y-C Chang","year":"2005","unstructured":"Chang, Y.-C., Mitzenmacher, M.: Privacy preserving keyword searches on remote encrypted data. In: Ioannidis, J., Keromytis, A., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 442\u2013455. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11496137_30"},{"key":"14_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/978-3-642-17373-8_33","volume-title":"Advances in Cryptology - ASIACRYPT 2010","author":"M Chase","year":"2010","unstructured":"Chase, M., Kamara, S.: Structured encryption and controlled disclosure. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 577\u2013594. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-17373-8_33"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Curtmola, R., Garay, J.A., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. In: Proceedings of the 13th ACM Conference on Computer and Communications Security, pp. 79\u201388 (2006)","DOI":"10.1145\/1180405.1180417"},{"issue":"5","key":"14_CR12","doi-asserted-by":"publisher","first-page":"895","DOI":"10.3233\/JCS-2011-0426","volume":"19","author":"R Curtmola","year":"2011","unstructured":"Curtmola, R., Garay, J.A., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: Improved definitions and efficient constructions. J. Comput. Secur. 19(5), 895\u2013934 (2011)","journal-title":"J. Comput. Secur."},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"Demertzis, I. Papadopoulos, D., Papamanthou, C.: Searchable encryption with optimal locality: achieving sublogarithmic read efficiency. Cryptology ePrint Archive, Report 2017\/749 (2017)","DOI":"10.1007\/978-3-319-96884-1_13"},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Demertzis, I., Papamanthou, C.: Fast searchable encryption with tunable locality. In: Proceedings of the 2017 ACM Special Interest Group on Management of Data (SIGMOD) Conference, pp. 1053\u20131067 (2017)","DOI":"10.1145\/3035918.3064057"},{"key":"14_CR15","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/978-3-540-70575-8_32","volume-title":"Automata, Languages and Programming","author":"Martin Dietzfelbinger","year":"2008","unstructured":"Dietzfelbinger, M., Pagh, R.: Succinct data structures for retrieval and approximate membership. In: Proceedings of the 35th International Colloquium on Automata, Languages and Programming, pp. 385\u2013396 (2008)"},{"key":"14_CR16","doi-asserted-by":"crossref","unstructured":"Goh, E.: Secure indexes. Cryptology ePrint Archive, Report 2003\/216 (2003)","DOI":"10.1108\/09696470310476981"},{"key":"14_CR17","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/BFb0028575","volume-title":"STACS 98","author":"Torben Hagerup","year":"1998","unstructured":"Hagerup, T.: Sorting and searching on the word RAM. In: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, pp. 366\u2013398 (1998)"},{"issue":"1","key":"14_CR18","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1006\/jagm.2001.1171","volume":"41","author":"T Hagerup","year":"2001","unstructured":"Hagerup, T., Miltersen, P.B., Pagh, R.: Deterministic dictionaries. J. Algorithms 41(1), 69\u201385 (2001)","journal-title":"J. Algorithms"},{"key":"14_CR19","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-642-39884-1_22","volume-title":"Financial Cryptography and Data Security","author":"Seny Kamara","year":"2013","unstructured":"Kamara, S., Papamanthou, C.: Parallel and dynamic searchable symmetric encryption. In: Proceedings of the 16th International Conference on Financial Cryptography and Data Security, pp. 258\u2013274 (2013)"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: Proceedings of the 19th ACM Conference on Computer and Communications Security, pp. 965\u2013976 (2012)","DOI":"10.1145\/2382196.2382298"},{"issue":"4","key":"14_CR21","doi-asserted-by":"publisher","first-page":"1543","DOI":"10.1137\/080728743","volume":"39","author":"A Kirsch","year":"2009","unstructured":"Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: cuckoo hashing with a stash. SIAM J. Comput. 39(4), 1543\u20131561 (2009)","journal-title":"SIAM J. Comput."},{"key":"14_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-3-642-32946-3_21","volume-title":"Financial Cryptography and Data Security","author":"K Kurosawa","year":"2012","unstructured":"Kurosawa, K., Ohtaki, Y.: UC-secure searchable symmetric encryption. In: Keromytis, A.D. (ed.) FC 2012. LNCS, vol. 7397, pp. 285\u2013298. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32946-3_21"},{"key":"14_CR23","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/978-3-319-02937-5_17","volume-title":"Cryptology and Network Security","author":"Kaoru Kurosawa","year":"2013","unstructured":"Kurosawa, K., Ohtaki, Y.: How to update documents verifiably in searchable symmetric encryption. In: Proceedings of the 12th International Conference on Cryptology and Network Security, pp. 309\u2013328 (2013)"},{"key":"14_CR24","unstructured":"Miltersen, P.B.: Cell probe complexity - a survey. In: Proceedings of the 19th Conference on the Foundations of Software Technology and Theoretical Computer Science, Advances in Data Structures Workshop (1999)"},{"issue":"1","key":"14_CR25","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1137\/060658400","volume":"38","author":"A Pagh","year":"2008","unstructured":"Pagh, A., Pagh, R.: Uniform hashing in constant time and optimal space. SIAM J. Comput. 38(1), 85\u201396 (2008)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"14_CR26","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R Pagh","year":"2004","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms 51(2), 122\u2013144 (2004)","journal-title":"J. Algorithms"},{"key":"14_CR27","unstructured":"Song, D.X., Wagner, D., Perrig, A.: Practical techniques for searches on encrypted data. In: Proceedings of the 21st Annual IEEE Symposium on Security and Privacy, pp. 44\u201355 (2000)"},{"key":"14_CR28","doi-asserted-by":"crossref","unstructured":"Stefanov, E., Papamanthou, C., Shi, E.: Practical dynamic searchable encryption with small leakage. In: Proceedings of the 21st Annual Network and Distributed System Security Symposium (2014)","DOI":"10.14722\/ndss.2014.23298"},{"key":"14_CR29","doi-asserted-by":"crossref","unstructured":"van Liesdonk, P., Sedghi, S., Doumen, J., Hartel, P.H., Jonker, W.: Computationally efficient searchable symmetric encryption. In: Proceedings of 7th VLDB Workshop on Secure Data Management, pp. 87\u2013100 (2010)","DOI":"10.1007\/978-3-642-15546-8_7"}],"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_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T00:01:10Z","timestamp":1751760070000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-96884-1_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319968834","9783319968841"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-96884-1_14","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":"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"}]}}