Fault-tolerant Verifiable Dynamic SSE with Forward and Backward Privacy

Bibhas Chandra Das; Nilanjan Datta; Avishek Majumder; Subhabrata Samajder

doi:10.62056/ayl5w4fe-3

Fault-tolerant Verifiable Dynamic SSE with Forward and Backward Privacy

Authors

Bibhas Chandra Das, Nilanjan Datta, Avishek Majumder, Subhabrata Samajder

Bibhas Chandra Das

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 $\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).

References

[BFP16]

Raphael Bost, Pierre-Alain Fouque, and David Pointcheval. Verifiable Dynamic Symmetric Searchable Encryption: Optimality and Forward Security. IACR Cryptol. ePrint Arch., 2016.

Google Scholar ePrint

[BMO17]

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

Google Scholar ePrint

[Bos16]

Raphael Bost. $\sum$o$\varphi$o$\varsigma$: 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

Google Scholar ePrint

[CDvD⁺03]

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

Google Scholar ePrint

[CG12]

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

Google Scholar ePrint

[CGKO06]

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

Google Scholar ePrint

[CGPR15]

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

Google Scholar ePrint

[CJJ⁺13]

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

Google Scholar ePrint

[CM05]

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

Google Scholar ePrint

[CMS25]

Debrup Chakraborty, Avishek Majumder, and Subhabrata Samajder. Making searchable symmetric encryption schemes smaller and faster. Int. J. Inf. Sec., 24(1):10, 2025. DOI: 10.1007/S10207-024-00915-Y

Google Scholar ePrint

[CPS20]

Sanjit Chatterjee, Shravan Kumar Parshuram Puria, and Akash Shah. Efficient backward private searchable encryption. J. Comput. Secur., 28(2):229–267, 2020. DOI: 10.3233/JCS-191322

Google Scholar ePrint

[GYZ⁺21]

Xinrui Ge, Jia Yu, Hanlin Zhang, Chengyu Hu, Zengpeng Li, Zhan Qin, and Rong Hao. Towards Achieving Keyword Search over Dynamic Encrypted Cloud Data with Symmetric-Key Based Verification. IEEE Trans. Dependable Secur. Comput., 18(1):490–504, 2021. DOI: 10.1109/TDSC.2019.2896258

Google Scholar ePrint

[HWKS98]

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

Google Scholar ePrint

[IKK12]

Mohammad Saiful Islam, Mehmet Kuzu, and Murat Kantarcioglu. Access Pattern disclosure on Searchable Encryption: Ramification, Attack and Mitigation. In 19th Annual Network and Distributed System Security Symposium, NDSS 2012, San Diego, California, USA, February 5-8, 2012. 2012. The Internet Society.

Google Scholar ePrint

[KO12]

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

Google Scholar ePrint

[KO13]

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

Google Scholar ePrint

[KPR12]

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

Google Scholar ePrint

[NC07]

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

Google Scholar ePrint

[SDY⁺20]

Xiangfu Song, Changyu Dong, Dandan Yuan, Qiuliang Xu, and Minghao Zhao. Forward Private Searchable Symmetric Encryption with Optimized I/O Efficiency. IEEE Trans. Dependable Secur. Comput., 17(5):912–927, 2020. DOI: 10.1109/TDSC.2018.2822294

Google Scholar ePrint

[SPS14]

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.

Google Scholar ePrint

[SWP00]

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

Google Scholar ePrint

[SYL⁺18]

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

Google Scholar ePrint

[YCR22]

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

Google Scholar ePrint

[Zha19]

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

Google Scholar ePrint

[ZKP16]

Yupeng Zhang, Jonathan Katz, and Charalampos Papamanthou. All Your Queries Are Belong to Us: The Power of File-Injection Attacks on Searchable Encryption. In Thorsten Holz and Stefan Savage, editors, 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, August 10-12, 2016, pages 707–720. 2016. USENIX Association.

Google Scholar ePrint

[ZLW⁺18]

Jie Zhu, Qi Li, Cong Wang, Xingliang Yuan, Qian Wang, and Kui Ren. Enabling Generic, Verifiable, and Secure Data Search in Cloud Services. IEEE Trans. Parallel Distributed Syst., 29(8):1721–1735, 2018. DOI: 10.1109/TPDS.2018.2808283

Google Scholar ePrint

[ZWW⁺19]

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

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/ayl5w4fe-3

History

Submitted: 2024-07-09
Accepted: 2024-12-03
Published: 2025-01-13

How to cite

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.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@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.