{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T17:05:06Z","timestamp":1753895106206,"version":"3.41.2"},"reference-count":27,"publisher":"International Association for Cryptologic Research","issue":"4","license":[{"start":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T00:00:00Z","timestamp":1720483200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,12,3]]},"abstract":"<jats:p>    Dynamic Searchable Symmetric Encryption (DSSE) allows users to securely outsource their data to cloud servers while enabling efficient searches and updates. The verifiability property of a DSSE construction ensures that users do not accept incorrect search results from a malicious server while the fault-tolerance property guarantees the construction functions correctly even with faulty queries from the client (e.g., adding a keyword to a document multiple times, deleting a keyword from a document that was never added). There have been very few studies on fault-tolerant verifiable DSSE schemes that achieve forward privacy, and none of the existing constructions achieve backward privacy. In this paper, we aim to design an efficient fault-tolerant verifiable DSSE scheme that provides both forward and backward privacy. First, we propose a basic fault-tolerant verifiable DSSE scheme, dubbed <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mtext mathvariant=\"sans-serif\">FVS1<\/mml:mtext>\n              <\/mml:mrow>\n            <\/mml:math>, which achieves forward privacy and stronger backward privacy with the update pattern (BPUP). However, the communication complexity for the search operation of this scheme is <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>O<\/mml:mi>\n                <mml:mo stretchy=\"false\">(<\/mml:mo>\n                <mml:mi>u<\/mml:mi>\n                <mml:mo stretchy=\"false\">)<\/mml:mo>\n              <\/mml:mrow>\n            <\/mml:math>, where <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>u<\/mml:mi>\n              <\/mml:mrow>\n            <\/mml:math> is the total number of updates for the search keyword. To address this issue, we propose an efficient variant of the previous DSSE scheme, called <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mtext mathvariant=\"sans-serif\">FVS2<\/mml:mtext>\n              <\/mml:mrow>\n            <\/mml:math>, which achieves the same functionality with an optimized communication complexity of <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>O<\/mml:mi>\n                <mml:mo stretchy=\"false\">(<\/mml:mo>\n                <mml:mi>m<\/mml:mi>\n                <mml:mo>+<\/mml:mo>\n                <mml:msup>\n                  <mml:mi>u<\/mml:mi>\n                  <mml:mi>\u2032<\/mml:mi>\n                <\/mml:msup>\n                <mml:mo stretchy=\"false\">)<\/mml:mo>\n              <\/mml:mrow>\n            <\/mml:math> for search queries. Here <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>m<\/mml:mi>\n              <\/mml:mrow>\n            <\/mml:math> is the size of the result set and <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:msup>\n                  <mml:mi>u<\/mml:mi>\n                  <mml:mi>\u2032<\/mml:mi>\n                <\/mml:msup>\n              <\/mml:mrow>\n            <\/mml:math> is the number of update operations made on the queried keyword after the previous search made on the keyword. This improvement comes at the cost of some additional information leakage, but it ensures the construction achieves backward privacy with the link pattern (BPLP). <\/jats:p>","DOI":"10.62056\/ayl5w4fe-3","type":"journal-article","created":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T17:00:52Z","timestamp":1736787652000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Fault-tolerant Verifiable Dynamic SSE with Forward and Backward Privacy"],"prefix":"10.62056","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-8279-7330","authenticated-orcid":false,"given":"Bibhas","family":"Das","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05h2r8y34","id-type":"ROR","asserted-by":"publisher"}],"name":"Institute for Advancing Intelligence, TCG CREST","place":["India"]},{"id":[{"id":"https:\/\/ror.org\/04zp24820","id-type":"ROR","asserted-by":"publisher"}],"name":"Chennai Mathematical Institute","place":["India"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-9761-1192","authenticated-orcid":false,"given":"Nilanjan","family":"Datta","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05h2r8y34","id-type":"ROR","asserted-by":"publisher"}],"name":"Institute for Advancing Intelligence, TCG CREST","place":["India"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-3343-1085","authenticated-orcid":false,"given":"Avishek","family":"Majumder","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/04q2jes40","id-type":"ROR","asserted-by":"publisher"}],"name":"UPES","place":["India"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5737-2281","authenticated-orcid":false,"given":"Subhabrata","family":"Samajder","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05h2r8y34","id-type":"ROR","asserted-by":"publisher"}],"name":"Institute for Advancing Intelligence, TCG CREST","place":["India"]},{"id":[{"id":"https:\/\/ror.org\/053rcsq61","id-type":"ROR","asserted-by":"publisher"}],"name":"Academy of Scientific and Innovative Research","place":["India"]}]}],"member":"48349","published-online":{"date-parts":[[2025,1,13]]},"reference":[{"key":"ref1:song","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1109\/SECPRI.2000.848445","article-title":"Practical Techniques for Searches on Encrypted Data","author":"Dawn Xiaodong Song","year":"2000"},{"key":"ref2:chang05","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1007\/11496137_30","article-title":"Privacy Preserving Keyword Searches on Remote Encrypted\n  Data","volume":"3531","author":"Yan-Cheng Chang","year":"2005"},{"key":"ref3:curtmola","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1145\/1180405.1180417","article-title":"Searchable symmetric encryption: improved definitions and\n  efficient constructions","author":"Reza Curtmola","year":"2006"},{"key":"ref4:kamara12","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/2382196.2382298","article-title":"Dynamic searchable symmetric encryption","author":"Seny Kamara","year":"2012"},{"key":"ref5:NC2007","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1145\/1277741.1277776","article-title":"Pruning policies for two-tiered inverted index with\n  correctness guarantee","author":"Alexandros Ntoulas","year":"2007"},{"article-title":"Access Pattern disclosure on Searchable Encryption:\n  Ramification, Attack and Mitigation","year":"2012","author":"Mohammad Saiful Islam","key":"ref6:Islam12"},{"key":"ref7:cash15","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/2810103.2813700","article-title":"Leakage-Abuse Attacks Against Searchable Encryption","author":"David Cash","year":"2015"},{"key":"ref8:zhang16","first-page":"707","article-title":"All Your Queries Are Belong to Us: The Power of\n  File-Injection Attacks on Searchable Encryption","author":"Yupeng Zhang","year":"2016"},{"key":"ref9:bost16","doi-asserted-by":"publisher","first-page":"1143","DOI":"10.1145\/2976749.2978303","article-title":"\\(\\sum\\)o\\(\\varphi\\)o\\(\\varsigma\\): Forward Secure\n  Searchable Encryption","author":"Raphael Bost","year":"2016"},{"key":"ref10:bost17","doi-asserted-by":"publisher","first-page":"1465","DOI":"10.1145\/3133956.3133980","article-title":"Forward and Backward Private Searchable Encryption from\n  Constrained Cryptographic Primitives","author":"Rapha\u00ebl Bost","year":"2017"},{"key":"ref11:song2018-FAST","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1109\/TDSC.2018.2822294","article-title":"Forward Private Searchable Symmetric Encryption with\n  Optimized I\/O Efficiency","volume":"17","author":"Xiangfu Song","year":"2020","journal-title":"IEEE Trans. Dependable Secur. Comput."},{"key":"ref12:sun18SPE","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1145\/3243734.3243782","article-title":"Practical Backward-Secure Searchable Encryption from\n  Symmetric Puncturable Encryption","author":"Shifeng Sun","year":"2018"},{"key":"ref13:sanjitJOCS","doi-asserted-by":"publisher","first-page":"229","DOI":"10.3233\/JCS-191322","article-title":"Efficient backward private searchable encryption","volume":"28","author":"Sanjit Chatterjee","year":"2020","journal-title":"J. Comput. Secur."},{"key":"ref14:CMS25","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1007\/S10207-024-00915-Y","article-title":"Making searchable symmetric encryption schemes smaller and\n  faster","volume":"24","author":"Debrup Chakraborty","year":"2025","journal-title":"Int. J. Inf. Sec."},{"key":"ref15:Kurosawa-uc","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-3-642-32946-3_21","article-title":"UC-Secure Searchable Symmetric Encryption","volume":"7397","author":"Kaoru Kurosawa","year":"2012"},{"key":"ref16:Gong12","doi-asserted-by":"publisher","first-page":"917","DOI":"10.1109\/ICC.2012.6364125","article-title":"Verifiable symmetric searchable encryption for\n  semi-honest-but-curious cloud servers","author":"Qi Chai","year":"2012"},{"key":"ref17:Kurosawa13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/978-3-319-02937-5_17","article-title":"How to Update Documents Verifiably in Searchable Symmetric\n  Encryption","volume":"8257","author":"Kaoru Kurosawa","year":"2013"},{"key":"ref18:Bost16Ver","first-page":"62","article-title":"Verifiable Dynamic Symmetric Searchable Encryption:\n  Optimality and Forward Security","author":"Raphael Bost","year":"2016","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref19:multi-set-hash","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-540-40061-5_12","article-title":"Incremental Multiset Hash Functions and Their Application to\n  Memory Integrity Checking","volume":"2894","author":"Dwaine E. Clarke","year":"2003"},{"key":"ref20:Zhang19ver","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1007\/978-3-030-29962-0_15","article-title":"Towards Efficient Verifiable Forward Secure Searchable\n  Symmetric Encryption","volume":"11736","author":"Zhongjun Zhang","year":"2019"},{"key":"ref21:Zhang21ver","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1109\/TDSC.2019.2896258","article-title":"Towards Achieving Keyword Search over Dynamic Encrypted\n  Cloud Data with Symmetric-Key Based Verification","volume":"18","author":"Xinrui Ge","year":"2021","journal-title":"IEEE Trans. Dependable Secur. Comput."},{"key":"ref22:Zhu18ver","doi-asserted-by":"publisher","first-page":"1721","DOI":"10.1109\/TPDS.2018.2808283","article-title":"Enabling Generic, Verifiable, and Secure Data Search in\n  Cloud Services","volume":"29","author":"Jie Zhu","year":"2018","journal-title":"IEEE Trans. Parallel Distributed Syst."},{"article-title":"Practical Dynamic Searchable Encryption with Small Leakage","year":"2014","author":"Emil Stefanov","key":"ref23:Stefanov15"},{"key":"ref24:Yuan22ver","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1109\/EUROSP53844.2022.00043","article-title":"We Can Make Mistakes: Fault-tolerant Forward Private\n  Verifiable Dynamic Searchable Symmetric Encryption","author":"Dandan Yuan","year":"2022"},{"key":"ref25:cash13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/978-3-642-40041-4_20","article-title":"Highly-Scalable Searchable Symmetric Encryption with Support\n  for Boolean Queries","volume":"8042","author":"David Cash","year":"2013"},{"key":"ref26:zhandry","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-030-26951-7_9","article-title":"How to Record Quantum Queries, and Applications to Quantum\n  Indifferentiability","volume":"11693","author":"Mark Zhandry","year":"2019"},{"key":"ref27:switch","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/BFB0055742","article-title":"Building PRFs from PRPs","volume":"1462","author":"Chris Hall","year":"1998"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T17:11:03Z","timestamp":1736788263000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/4\/7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,13]]},"references-count":27,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,1,13]]}},"URL":"https:\/\/doi.org\/10.62056\/ayl5w4fe-3","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"type":"electronic","value":"3006-5496"}],"subject":[],"published":{"date-parts":[[2025,1,13]]},"assertion":[{"value":"2024-07-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-3-126"}}