{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T19:52:03Z","timestamp":1767988323912,"version":"3.49.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T00:00:00Z","timestamp":1611187200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T00:00:00Z","timestamp":1611187200000},"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":["J Cryptol"],"published-print":{"date-parts":[[2021,4]]},"DOI":"10.1007\/s00145-020-09370-z","type":"journal-article","created":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T17:03:33Z","timestamp":1611248613000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Tight Tradeoffs in Searchable Symmetric Encryption"],"prefix":"10.1007","volume":"34","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":[[2021,1,21]]},"reference":[{"issue":"3","key":"9370_CR1","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/s00453-013-9840-x","volume":"70","author":"M Aum\u00fcller","year":"2014","unstructured":"M. Aum\u00fcller, M. Dietzfelbinger, P. Woelfel, Explicit and efficient hash families suffice for cuckoo hashing with a stash. Algorithmica, 70(3), 428\u2013456, (2014)","journal-title":"Algorithmica"},{"key":"9370_CR2","unstructured":"Y. Arbitman, M. Naor, G. Segev, Backyard cuckoo hashing: constant worst-case operations with a succinct representation, in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (2010), pp. 787\u2013796"},{"key":"9370_CR3","unstructured":"G. Asharov, M. Naor, G. Segev, I. Shahaf, 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 (2016), pp. 1101\u20131114"},{"key":"9370_CR4","unstructured":"R. Curtmola, J. A. Garay, S. Kamara, R. Ostrovsky, Searchable symmetric encryption: improved definitions and efficient constructions, in Proceedings of the 13th ACM Conference on Computer and Communications Security (2006), pp. 79\u201388"},{"issue":"5","key":"9370_CR5","doi-asserted-by":"publisher","first-page":"895","DOI":"10.3233\/JCS-2011-0426","volume":"19","author":"R Curtmola","year":"2011","unstructured":"R. Curtmola, J. A. Garay, S. Kamara, R. Ostrovsky, Searchable symmetric encryption: Improved definitions and efficient constructions. J. Comput. Sec. 19(5), 895\u2013934 (2011)","journal-title":"J. Comput. Sec."},{"key":"9370_CR6","unstructured":"D. Cash, P. Grubbs, J. Perry, T. Ristenpart, Leakage-abuse attacks against searchable encryption, in Proceedings of the 22nd ACM Conference on Computer and Communications Security (2015), pp. 668\u2013679"},{"key":"9370_CR7","unstructured":"D. Cash, S. Jarecki, C. S. Jutla, H. Krawczyk, M. Rosu, M. Steiner, Highly-scalable searchable symmetric encryption with support for Boolean queries, in Advances in Cryptology\u2014CRYPTO \u201913 (2013), pp. 353\u2013373"},{"key":"9370_CR8","doi-asserted-by":"crossref","unstructured":"D. Cash, J. Jaeger, S. Jarecki, C. S. Jutla, H. Krawczyk, M. Rosu, M. Steiner, 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":"9370_CR9","unstructured":"M. Chase, S. Kamara, Structured encryption and controlled disclosure, in Advances in Cryptology\u2014ASIACRYPT \u201910 (2010), pp. 577\u2013594"},{"key":"9370_CR10","unstructured":"Y.-C. Chang, M. Mitzenmacher, Privacy preserving keyword searches on remote encrypted data, in Proceedings of the 3rd International Conference on Applied Cryptography and Network Security (2005), pp. 442\u2013455"},{"key":"9370_CR11","unstructured":"D. Cash and S. Tessaro, The locality of searchable symmetric encryption, in Advances in Cryptology\u2014EUROCRYPT \u201914 (2014), pp. 351\u2013368"},{"key":"9370_CR12","unstructured":"M. Dietzfelbinger, R. Pagh, Succinct data structures for retrieval and approximate membership, in Proceedings of the 35th International Colloquium on Automata, Languages and Programming(2008), pp. 385\u2013396"},{"key":"9370_CR13","unstructured":"I. Demertzis, C. Papamanthou, Fast searchable encryption with tunable locality, in Proceedings of the 2017 ACM Special Interest Group on Management of Data (SIGMOD) Conference (2017), pp. 1053\u20131067"},{"key":"9370_CR14","doi-asserted-by":"crossref","unstructured":"I. Demertzis, D. Papadopoulos, C. Papamanthou, Searchable encryption with optimal locality: achieving sublogarithmic read efficiency, in Cryptology ePrint Archive, Report 2017\/749 (2017)","DOI":"10.1007\/978-3-319-96884-1_13"},{"key":"9370_CR15","unstructured":"E. Goh, Secure indexes, in Cryptology ePrint Archive, Report 2003\/216 (2003)"},{"key":"9370_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of Cryptography\u2014Volume 2: Basic Applications","author":"O Goldreich","year":"2004","unstructured":"O. Goldreich, Foundations of Cryptography\u2014Volume 2: Basic Applications. Cambridge University Press, Cambridge (2004)"},{"key":"9370_CR17","unstructured":"T. Hagerup, Sorting and searching on the word RAM, in Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science (1998), pp. 366\u2013398"},{"issue":"1","key":"9370_CR18","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1006\/jagm.2001.1171","volume":"41","author":"T Hagerup","year":"2001","unstructured":"T. Hagerup, P. B. Miltersen, R. Pagh, Deterministic dictionaries. J. Algorithms 41(1), 69\u201385 (2001)","journal-title":"J. Algorithms"},{"issue":"4","key":"9370_CR19","doi-asserted-by":"publisher","first-page":"1543","DOI":"10.1137\/080728743","volume":"39","author":"A Kirsch","year":"2009","unstructured":"A. Kirsch, M. Mitzenmacher, U. Wieder, More robust hashing: cuckoo hashing with a stash. SIAM J. Comput., 39(4), 1543\u20131561, (2009)","journal-title":"SIAM J. Comput."},{"key":"9370_CR20","unstructured":"K. Kurosawa, Y. Ohtaki, UC-secure searchable symmetric encryption, in Proceedings of the 16th International Conference on Financial Cryptography and Data Security (2012), pp. 285\u2013298"},{"key":"9370_CR21","unstructured":"K. Kurosawa, Y. Ohtaki, How to update documents verifiably in searchable symmetric encryption, in Proceedings of the 12th International Conference on Cryptology and Network Security (2013), pp. 309\u2013328"},{"key":"9370_CR22","unstructured":"S. Kamara, C. Papamanthou, Parallel and dynamic searchable symmetric encryption, in Proceedings of the 16th International Conference on Financial Cryptography and Data Security (2013), pp. 258\u2013274"},{"key":"9370_CR23","unstructured":"S. Kamara, C. Papamanthou, T. Roeder, Dynamic searchable symmetric encryption, in Proceedings of the 19th ACM Conference on Computer and Communications Security (2012), pp. 965\u2013976"},{"key":"9370_CR24","unstructured":"P.B. Miltersen, Cell probe complexity\u2014a 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":"9370_CR25","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1137\/060658400","volume":"38","author":"A Pagh","year":"2008","unstructured":"A. Pagh, R. Pagh, Uniform hashing in constant time and optimal space. SIAM J. Comput. 38(1), 85\u201396 (2008)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9370_CR26","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R Pagh","year":"2004","unstructured":"R. Pagh, F.F. Rodler, Cuckoo hashing. J. Algorithms, 51(2), 122\u2013144 (2004)","journal-title":"J. Algorithms"},{"key":"9370_CR27","doi-asserted-by":"crossref","unstructured":"E. Stefanov, C. Papamanthou, E. Shi, 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":"9370_CR28","unstructured":"D.X. Song, D. Wagner, A. Perrig, Practical techniques for searches on encrypted data, in Proceedings of the 21st Annual IEEE Symposium on Security and Privacy (2000), pp. 44\u201355"},{"key":"9370_CR29","unstructured":"P. van Liesdonk, S. Sedghi, J. Doumen, P.H. Hartel, W. Jonker, Computationally efficient searchable symmetric encryption, in Proceedings of 7th VLDB Workshop on Secure Data Management (2010), pp. 87\u2013100"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-020-09370-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-020-09370-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-020-09370-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,25]],"date-time":"2021-04-25T03:04:11Z","timestamp":1619319851000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-020-09370-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,21]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["9370"],"URL":"https:\/\/doi.org\/10.1007\/s00145-020-09370-z","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,21]]},"assertion":[{"value":"7 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 September 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 October 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"9"}}