Institute for Advancing Intelligence, TCG CREST, India
Chennai Mathematical Institute, India bibhaschandra dot das at tcgcrest dot org
Nilanjan Datta
Institute for Advancing Intelligence, TCG CREST, India nilanjan dot datta at tcgcrest dot org
Avishek Majumder
UPES, India avishek dot majumder1991 at gmail dot com
Subhabrata Samajder
Institute for Advancing Intelligence, TCG CREST, India
Academy of Scientific and Innovative Research, India subhabrata dot samajder at tcgcrest dot org
Abstract
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 , 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 , where 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 , which achieves the same functionality with an optimized communication complexity of for search queries. Here is the size of the result set and 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).
Raphaël Bost, Brice Minaud, and Olga Ohrimenko. Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives. In Bhavani Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017, pages 1465–1482. 2017. ACM. DOI: 10.1145/3133956.3133980
Raphael Bost. oo: Forward Secure Searchable Encryption. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016, pages 1143–1154. 2016. ACM. DOI: 10.1145/2976749.2978303
Dwaine E. Clarke, Srinivas Devadas, Marten van Dijk, Blaise Gassend, and G. Edward Suh. Incremental Multiset Hash Functions and Their Application to Memory Integrity Checking. In Chi-Sung Laih, editor, Advances in Cryptology - ASIACRYPT 2003, 9th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, November 30 - December 4, 2003, Proceedings, volume 2894 of Lecture Notes in Computer Science, pages 188–207. 2003. Springer. DOI: 10.1007/978-3-540-40061-5_12
Qi Chai and Guang Gong. Verifiable symmetric searchable encryption for semi-honest-but-curious cloud servers. In Proceedings of IEEE International Conference on Communications, ICC 2012, Ottawa, ON, Canada, June 10-15, 2012, pages 917–922. 2012. IEEE. DOI: 10.1109/ICC.2012.6364125
Reza Curtmola, Juan A. Garay, Seny Kamara, and Rafail Ostrovsky. Searchable symmetric encryption: improved definitions and efficient constructions. In Ari Juels, Rebecca N. Wright, and Sabrina De Capitani di Vimercati, editors, Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS 2006, Alexandria, VA, USA, October 30 - November 3, 2006, pages 79–88. 2006. ACM. DOI: 10.1145/1180405.1180417
David Cash, Paul Grubbs, Jason Perry, and Thomas Ristenpart. Leakage-Abuse Attacks Against Searchable Encryption. In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12-16, 2015, pages 668–679. 2015. ACM. DOI: 10.1145/2810103.2813700
David Cash, Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel-Catalin Rosu, and Michael Steiner. Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, volume 8042 of Lecture Notes in Computer Science, pages 353–373. 2013. Springer. DOI: 10.1007/978-3-642-40041-4_20
Yan-Cheng Chang and Michael Mitzenmacher. Privacy Preserving Keyword Searches on Remote Encrypted Data. In John Ioannidis, Angelos D. Keromytis, and Moti Yung, editors, Applied Cryptography and Network Security, Third International Conference, ACNS 2005, New York, NY, USA, June 7-10, 2005, Proceedings, volume 3531 of Lecture Notes in Computer Science, pages 442–455. 2005. DOI: 10.1007/11496137_30
Chris Hall, David A. Wagner, John Kelsey, and Bruce Schneier. Building PRFs from PRPs. In Hugo Krawczyk, editor, Advances in Cryptology - CRYPTO '98, 18th Annual International Cryptology Conference, Santa Barbara, California, USA, August 23-27, 1998, Proceedings, volume 1462 of Lecture Notes in Computer Science, pages 370–389. 1998. Springer. DOI: 10.1007/BFB0055742
Kaoru Kurosawa and Yasuhiro Ohtaki. UC-Secure Searchable Symmetric Encryption. In Angelos D. Keromytis, editor, Financial Cryptography and Data Security - 16th International Conference, FC 2012, Kralendijk, Bonaire, February 27 - March 2, 2012, Revised Selected Papers, volume 7397 of Lecture Notes in Computer Science, pages 285–298. 2012. Springer. DOI: 10.1007/978-3-642-32946-3_21
Kaoru Kurosawa and Yasuhiro Ohtaki. How to Update Documents Verifiably in Searchable Symmetric Encryption. In Michel Abdalla, Cristina Nita-Rotaru, and Ricardo Dahab, editors, Cryptology and Network Security - 12th International Conference, CANS 2013, Paraty, Brazil, November 20-22. 2013. Proceedings, volume 8257 of Lecture Notes in Computer Science, pages 309–328. 2013. Springer. DOI: 10.1007/978-3-319-02937-5_17
Seny Kamara, Charalampos Papamanthou, and Tom Roeder. Dynamic searchable symmetric encryption. In Ting Yu, George Danezis, and Virgil D. Gligor, editors, the ACM Conference on Computer and Communications Security, CCS'12, Raleigh, NC, USA, October 16-18, 2012, pages 965–976. 2012. ACM. DOI: 10.1145/2382196.2382298
Alexandros Ntoulas and Junghoo Cho. Pruning policies for two-tiered inverted index with correctness guarantee. In Wessel Kraaij, Arjen P. de Vries, Charles L. A. Clarke, Norbert Fuhr, and Noriko Kando, editors, SIGIR 2007: Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Amsterdam, The Netherlands, July 23-27, 2007, pages 191–198. 2007. ACM. DOI: 10.1145/1277741.1277776
Emil Stefanov, Charalampos Papamanthou, and Elaine Shi. Practical Dynamic Searchable Encryption with Small Leakage. In 21st Annual Network and Distributed System Security Symposium, NDSS 2014, San Diego, California, USA, February 23-26, 2014. 2014. The Internet Society.
Dawn Xiaodong Song, David A. Wagner, and Adrian Perrig. Practical Techniques for Searches on Encrypted Data. In 2000 IEEE Symposium on Security and Privacy, Berkeley, California, USA, May 14-17, 2000, pages 44–55. 2000. IEEE Computer Society. DOI: 10.1109/SECPRI.2000.848445
Shifeng Sun, Xingliang Yuan, Joseph K. Liu, Ron Steinfeld, Amin Sakzad, Viet Vo, and Surya Nepal. Practical Backward-Secure Searchable Encryption from Symmetric Puncturable Encryption. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, October 15-19, 2018, pages 763–780. 2018. ACM. DOI: 10.1145/3243734.3243782
Dandan Yuan, Shujie Cui, and Giovanni Russello. We Can Make Mistakes: Fault-tolerant Forward Private Verifiable Dynamic Searchable Symmetric Encryption. In 7th IEEE European Symposium on Security and Privacy, EuroS&P 2022, Genoa, Italy, June 6-10, 2022, pages 587–605. 2022. IEEE. DOI: 10.1109/EUROSP53844.2022.00043
Mark Zhandry. How to Record Quantum Queries, and Applications to Quantum Indifferentiability. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part II, volume 11693 of Lecture Notes in Computer Science, pages 239–268. 2019. Springer. DOI: 10.1007/978-3-030-26951-7_9
Zhongjun Zhang, Jianfeng Wang, Yunling Wang, Yaping Su, and Xiaofeng Chen. Towards Efficient Verifiable Forward Secure Searchable Symmetric Encryption. In Kazue Sako, Steve A. Schneider, and Peter Y. A. Ryan, editors, Computer Security - ESORICS 2019 - 24th European Symposium on Research in Computer Security, Luxembourg, September 23-27, 2019, Proceedings, Part II, volume 11736 of Lecture Notes in Computer Science, pages 304–321. 2019. Springer. DOI: 10.1007/978-3-030-29962-0_15
@article{CiC-1-4-7,
author = "Das, Bibhas Chandra and Datta, Nilanjan and Majumder, Avishek and Samajder, Subhabrata",
journal = "{IACR} {C}ommunications in {C}ryptology",
publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
title = "Fault-tolerant Verifiable Dynamic {SSE} with Forward and Backward Privacy",
volume = "1",
number = "4",
date = "2025-01-13",
year = "2025",
issn = "3006-5496",
doi = "10.62056/ayl5w4fe-3"
}
TY - JOUR
AU - Das, Bibhas
AU - Datta, Nilanjan
AU - Majumder, Avishek
AU - Samajder, Subhabrata
PY - 2025
TI - Fault-tolerant Verifiable Dynamic SSE with Forward and Backward Privacy
JF - IACR Communications in Cryptology
JA - CIC
VL - 1
IS - 4
DO - 10.62056/ayl5w4fe-3
UR - https://doi.org/10.62056/ayl5w4fe-3
AB - <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 $\textsf{FVS1}$, 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 $O(u)$, where $u$ 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 $\textsf{FVS2}$, which achieves the same functionality with an optimized communication complexity of $O(m+u')$ for search queries. Here $m$ is the size of the result set and $u'$ 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). </p>
ER -
Bibhas Chandra Das, Nilanjan Datta, Avishek Majumder, and
Subhabrata Samajder, Fault-tolerant Verifiable Dynamic SSE with Forward and Backward Privacy. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/ayl5w4fe-3.
Known citations
We do not crawl the web, so we are only able to identify
citations from papers that are registered with a DOI in
crossref.org and the publisher reports their citations to
crossref, and crossref can identify a DOI from the
reference. That includes (most) articles from Springer and
many from ACM, but it excludes citations from USENIX because
they don't issue DOIs. It also excludes citations from arxiv
and eprint. You may find more citations in
Google Scholar.