DISCO: Dynamic Searchable Encryption with Constant State
Authors: 
Xiangfu Song, Yu Zheng, Jianli Bai, Changyu Dong, Zheli Liu, Ee-Chien ChangAuthors Info & Claims
Pages 1724 - 1738
Abstract
Dynamic searchable encryption (DSE) with forward and backward privacy reduces leakages in early-stage schemes. Security enhancement comes with a price - maintaining updatable keyword-wise state information. State information, if stored locally, incurs significant client-side storage overhead for keyword-rich datasets, potentially hindering real-world deployments.
We propose DISCO, a simple and efficient framework for designing DSE schemes using constant client state. DISCO combines range-constrained pseudorandom functions (RCPRFs) over a global counter and leverages nice properties from the underlying primitives and index structure to simultaneously achieve forward-and-backward privacy and constant client state. To configure DISCO concretely, we identify a set of RCPRF properties that are vital for the resulting DISCO instantiations. By configuring DISCO with different RCPRFs, we resolve efficiency and usability issues in existing schemes. We further optimize DISCO's concrete efficiency without downgrading security. We implement DISCO constructions and report performance, showing trade-offs from different DISCO constructions. Besides, we compare the practical efficiency of DISCO with existing non-constant-state DSE schemes, demonstrating DISCO's competitive efficiency.
References
[1]
Raphael Bost. 2016. Σoφoς: Forward secure searchable encryption. In ACM SIGSAC Conference on Computer and Communications Security. 1143--1154.
[2]
Raphaël Bost, Brice Minaud, and Olga Ohrimenko. 2017. Forward and backward private searchable encryption from constrained cryptographic primitives. In ACM SIGSAC Conference on Computer and Communications Security. 1465--1482.
[3]
Lukas Burkhalter, Anwar Hithnawi, Alexander Viand, Hossein Shafagh, and Sylvia Ratnasamy. 2020. {TimeCrypt}: Encrypted data stream processing at scale with cryptographic access control. In USENIX Symposium on Networked Systems Design and Implementation (NSDI). 835--850.
[4]
David Cash, Joseph Jaeger, Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel-Catalin Rosu, and Michael Steiner. 2014. Dynamic searchable encryption in very-large databases: Data structures and implementation. Network and Distributed System Security Symposium (2014).
[5]
David Cash, Stanislaw Jarecki, Charanjit Jutla, Hugo Krawczyk, Marcel-Cuatualin Rocsu, and Michael Steiner. 2013. Highly-scalable searchable symmetric encryption with support for boolean queries. In Annual Cryptology Conference. 353--373.
[6]
David Cash and Stefano Tessaro. 2014. The locality of searchable symmetric encryption. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. 351--368.
[7]
Javad Ghareh Chamani, Dimitrios Papadopoulos, Mohammadamin Karbasforushan, and Ioannis Demertzis. 2022. Dynamic searchable encryption with optimal search in the presence of deletions. In USENIX Security. 2425--2442.
[8]
Tianyang Chen, Peng Xu, Wei Wang, Yubo Zheng, Willy Susilo, and Hai Jin. 2021. Bestie: Very practical searchable encryption with forward and backward security. In European Symposium on Research in Computer Security, Part II 26. 3--23.
[9]
Shujie Cui, Xiangfu Song, Muhammad Rizwan Asghar, Steven D Galbraith, and Giovanni Russello. 2021. Privacy-preserving dynamic symmetric searchable encryption with controllable leakage. ACM Transactions on Privacy and Security (TOPS) 24, 3 (2021), 1--35.
[10]
Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky. 2006. Searchable symmetric encryption: improved definitions and efficient constructions. In ACM conference on Computer and communications security. 79--88.
[11]
Ioannis Demertzis, Javad Ghareh Chamani, Dimitrios Papadopoulos, and Charalampos Papamanthou. 2020. Dynamic Searchable Encryption with Small Client Storage. In Annual Network and Distributed System Security Symposium.
[12]
Mohammad Etemad, Alptekin Küpçü, Charalampos Papamanthou, and David Evans. 2018. Efficient Dynamic Searchable Encryption with Forward Privacy. Privacy Enhancing Technologies 1 (2018), 5--20.
[13]
Sanjam Garg, Payman Mohassel, and Charalampos Papamanthou. 2016. TWORAM: efficient oblivious RAM in two rounds with applications to searchable encryption. In Annual International Cryptology Conference. 563--592.
[14]
Javad Ghareh Chamani, Dimitrios Papadopoulos, Charalampos Papamanthou, and Rasool Jalili. 2018. New constructions for forward and backward private symmetric searchable encryption. In ACM SIGSAC Conference on Computer and Communications Security. 1038--1055.
[15]
Oded Goldreich. 1987. Towards a theory of software protection and simulation by oblivious RAMs. In ACM symposium on Theory of computing. 182--194.
[16]
Oded Goldreich, Shafi Goldwasser, and Silvio Micali. 1986. How to construct random functions. Journal of the ACM (JACM) 33, 4 (1986), 792--807.
[17]
Kun He, Jing Chen, Qinxi Zhou, Ruiying Du, and Yang Xiang. 2020. Secure dynamic searchable symmetric encryption with constant client storage cost. IEEE Transactions on Information Forensics and Security 16 (2020), 1538--1549.
[18]
Seny Kamara, Tarik Moataz, and Olya Ohrimenko. 2018. Structured encryption and leakage suppression. In Annual International Cryptology Conference, Part I 38. 339--370.
[19]
Seny Kamara and Charalampos Papamanthou. 2013. Parallel and dynamic searchable symmetric encryption. In FC.
[20]
Seny Kamara, Charalampos Papamanthou, and Tom Roeder. 2012. Dynamic searchable symmetric encryption. In ACM conference on Computer and communications security. 965--976.
[21]
Kee Sung Kim, Minkyu Kim, Dongsoo Lee, Je Hong Park, and Woo-Hwan Kim. 2017. Forward secure dynamic searchable symmetric encryption with efficient updates. In ACM SIGSAC Conference on Computer and Communications Security. 1449--1463.
[22]
Russell WF Lai and Sherman SM Chow. 2017. Forward-secure searchable encryption on labeled bipartite graphs. In International Conference on Applied Cryptography and Network Security. 478--497.
[23]
Feng Li, Jianfeng Ma, Yinbin Miao, Pengfei Wu, and Xiangfu Song. 2023. Beyond Volume Pattern: Storage-Efficient Boolean Searchable Symmetric Encryption with Suppressed Leakage. In European Symposium on Research in Computer Security. Springer, 126--146.
[24]
Zheli Liu, Yanyu Huang, Xiangfu Song, Bo Li, Jin Li, Yali Yuan, and Changyu Dong. 2020. Eurus: towards an efficient searchable symmetric encryption with size pattern protection. IEEE Transactions on Dependable and Secure Computing 19, 3 (2020), 2023--2037.
[25]
Dawn Xiaoding Song, David Wagner, and Adrian Perrig. 2000. Practical techniques for searches on encrypted data. In IEEE symposium on security and privacy. S&P 2000. 44--55.
[26]
Xiangfu Song, Changyu Dong, Dandan Yuan, Qiuliang Xu, and Minghao Zhao. 2018. Forward private searchable symmetric encryption with optimized I/O efficiency. IEEE Transactions on Dependable and Secure Computing 17, 5 (2018), 912--927.
[27]
Xiangfu Song, Dong Yin, Han Jiang, and Qiuliang Xu. 2020. Searchable Symmetric Encryption with Tunable Leakage Using Multiple Servers. In International Conference on Database Systems for Advanced Applications. Springer, 157--177.
[28]
Emil Stefanov, Marten van Dijk, Elaine Shi, T-H Hubert Chan, Christopher Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. 2018. Path ORAM: an extremely simple oblivious RAM protocol. Journal of the ACM (JACM) 65, 4 (2018), 1--26.
[29]
Emil Stefanov, Charalampos Papamanthou, and Elaine Shi. 2014. Practical Dynamic Searchable Encryption with Small Leakage. In NDSS.
[30]
Shi-Feng Sun, Ron Steinfeld, Shangqi Lai, Xingliang Yuan, Amin Sakzad, Joseph K Liu, Surya Nepal, and Dawu Gu. 2021. Practical Non-Interactive Searchable Encryption with Forward and Backward Privacy. In Network and Distributed System Security Symposium.
[31]
Shi-Feng Sun, Xingliang Yuan, Joseph K Liu, Ron Steinfeld, Amin Sakzad, Viet Vo, and Surya Nepal. 2018. Practical backward-secure searchable encryption from symmetric puncturable encryption. In ACM SIGSAC Conference on Computer and Communications Security. 763--780.
[32]
Jiafan Wang and Sherman SM Chow. 2022. Forward and Backward-Secure Range-Searchable Symmetric Encryption. Privacy Enhancing Technologies 1 (2022), 28--48.
[33]
Xiao Shaun Wang, Kartik Nayak, Chang Liu, TH Hubert Chan, Elaine Shi, Emil Stefanov, and Yan Huang. 2014. Oblivious data structures. In ACM SIGSAC Conference on Computer and Communications Security. 215--226.
[34]
Yupeng Zhang, Jonathan Katz, and Charalampos Papamanthou. 2016. All your queries are belong to us: the power of {File-Injection} attacks on searchable encryption. In USENIX Security Symposium (USENIX Security). 707--720.
[35]
Yu Zheng, Heng Tian, Minxin Du, and Chong Fu. 2022. Encrypted video search: Scalable, modular, and content-similar. In ACM Multimedia systems Conference. 177--190.
Index Terms
- DISCO: Dynamic Searchable Encryption with Constant State
Recommendations
Forward and Backward Private Searchable Encryption with SGX
EuroSec '19: Proceedings of the 12th European Workshop on Systems SecuritySymmetric Searchable Encryption (SSE) schemes enable users to search over encrypted data hosted on an untrusted server. Recently, there has been a lot of interest in forward and backward private SSE. The notion of forward privacy guarantees that updates ...
Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives
CCS '17: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications SecurityUsing dynamic Searchable Symmetric Encryption, a user with limited storage resources can securely outsource a database to an untrusted server, in such a way that the database can still be searched and updated efficiently. For these schemes, it would be ...
Dynamic Searchable Symmetric Encryption with Forward and Stronger Backward Privacy
Computer Security – ESORICS 2019AbstractDynamic Searchable Symmetric Encryption (DSSE) enables a client to perform updates and searches on encrypted data which makes it very useful in practice. To protect DSSE from the leakage of updates (leading to break query or data privacy), two new ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
1987 pages
ISBN:9798400704826
DOI:10.1145/3634737
- Chair:
- Jianying Zhou,
- Co-chair:
- Tony Q. S. Quek,
- Program Chairs:
- Debin Gao,
- Alvaro Cardenas
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 July 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- National Research Foundation, Singapore
- National Natural Science Foundation of China
Conference
ASIA CCS '24
Sponsor:
ASIA CCS '24: 19th ACM Asia Conference on Computer and Communications Security
July 1 - 5, 2024
Singapore, Singapore
Acceptance Rates
Overall Acceptance Rate 418 of 2,322 submissions, 18%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 142Total Downloads
- Downloads (Last 12 months)142
- Downloads (Last 6 weeks)11
Reflects downloads up to 14 Feb 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in