Abstract
Searchable symmetric encryption allows operating on encrypted data, particularly keyword-based search on documents and range-based search on spatial data. Various methods can be used in Searchable symmetric encryption, such as order-preserving or fully homomorphic encryption, for different levels of information leakage. New schemes with more efficient search operations and reduced access and search pattern leakage that support novel settings, such as dynamic data sets and multiple users, have been proposed in the last few years. Especially with the emergence of cloud storage, encrypting sensitive remote data while preserving the ability to operate efficiently is an ample opportunity for the military and industry. However, there are risks when deploying Searchable symmetric encryption that must be considered since some Searchable symmetric encryption schemes proposed in the past have been (completely) broken by the research community.
You have full access to this open access chapter, Download chapter PDF
1 Introduction
Searchable symmetric encryption (SSE) allows operating on encrypted data, in particular keyword- based search on documents and range-based search on spatial data. Various methods can be used in SSE, such as order-preserving encryption or fully homomorphic encryption for different levels of information leakage. New schemes with more efficient search operation and reduced access and search pattern leakage that support novel settings, such as dynamic data sets and multiple users, have been proposed in the last few years. Especially with the emergence of cloud storage, encrypting sensitive remote data while preserving the ability to efficiently operate on it is an ample opportunity for the military and industry. However, there are risks when deploying SSE that must be taken into account since some SSE schemes proposed in the past have been (completely) broken by the research community.
2 Analysis
2.1 Definition
In the searchable symmetric encryption (SSE) setting, there is a collection of files where keywords are associated with each file. A user searches for all files in the collection associated with a specific keyword. Neither the content of files nor the associated keywords should be revealed to an unauthorized entity. To achieve this, files and keywords are encrypted, and only users with the respective keys can search the collection and decrypt files. Depending on the SSE protocol, files can be added and removed (dynamic), files can be added but not removed (semi-dynamic), or all files must be present when the system is set up and cannot change over time (static).
SSE should not be confused with Public Key Encryption with Keyword Search (PEKS), a related technique that allows holders of a public key to add encrypted files to the collection and the private key holder to search for and decrypt files.
The security of an SSE protocol is defined by its privacy leakage, i.e., how much information is leaked in addition to necessarily leaked information such as the file sizes, access patterns, and search patterns under different attacker models (adaptive and non-adaptive attackers) [1].
Fully homomorphic encryption (FHE) is another cryptographic primitive to operate on encrypted data without revealing the results. Although FHE can provide stronger privacy guarantees than SSE, it is computationally more expensive and requires data in homogeneous form, while SSE can operate on any heterogeneous data.
There are several variations on the SSE model. For example, some SSEs consider searches for data ranges instead of searches for specific keywords. Such SSEs are useful for outsourcing encrypted spatial data, e.g., collecting location-indexed data. However, early constructs, such as order preserving encryption [2], are vulnerable to database reconstruction attacks [3].
Traditional SSEs operate in a single-user setting, but some SSE also considers a multi-user setting, where users can be added and removed, which brings additional challenges, such as colluding users.
2.2 Trends
There is a long history of research on SSE, starting with early work in 2000 by Song et al. [4]. Over the last 20 years, SSEs have improved functionality, security, and efficiency. First, the functionality of SSE schemes was improved, e.g., by allowing modifications to the dictionaries [5]. The attacker model was extended to provide forward privacy (previous search queries cannot be associated with future updates) and backward privacy (search queries cannot be associated with deleted documents). Finally, SSE schemes become increasingly efficient (e.g., Aura [6], which has a sub-millisecond index insertion time and a sub-microsecond deletion time). State-of-the-art SSE schemes have become practical to be used in real-world settings while providing strong security properties [6, 7].
With the emergence of cloud-based services and storage, parties in various sectors have decided to move their data to cloud storage, significantly reducing operational costs. In most cases, the cloud infrastructure is not hosted by the party but by an independent provider. In such cases, it is often preferential or even required by law or policy to only store encrypted data in the cloud. Unfortunately, storing encrypted data makes searching the database impossible for the provider that does not possess the decryption keys. SSE allows parties to combine the benefits of encrypted cloud storage while retaining the ability to search this data. Since the trend of increasingly using cloud storage is not expected to slow down in the near future, efficient SSE approaches are likely to be increasingly used.
However, it is essential to note that correctly designing and implementing SSE is difficult. Many proposed systems have become insecure as they leak access patterns or even allow reconstructing the complete database [8, 9]. The risk of storing sensitive data on remote storage using SSE must thus be carefully evaluated case-by-case.
3 Consequences for Switzerland
There is ample opportunity to move more sensitive data to the cloud to reduce hardware and management costs and facilitate information sharing. At the same time, privacy regulations or company-specific policies that require sensitive data to be encrypted fuel the need for SSE.
3.1 Implementation Possibilities: Make or Buy
For the military, public cloud solutions are likely not up to their standard in terms of security and reliability. However, the military must collaborate with foreign armed forces, police forces, or between different divisions. Therefore, custom-built SSE solutions running on trustworthy cloud infrastructures could be attractive, especially for sharing data within Switzerland. Furthermore, a solution offered by a trustworthy international source could also be an exciting option for collaboration with foreign entities.
For the civil society and economy sector, custom-built solutions may be prohibitive in terms of cost and complicate collaboration with other entities. Public cloud SSE solutions are also attractive due to their low cost and simple management. A straightforward use case for SSE in civil society is storing privacy-sensitive healthcare data on a public cloud for collaboration between health insurance providers, hospitals, and clinics (Table 14.1).
3.2 Variations and Recommendation
There is typically a trade-off between the low cost, straightforward management, and ease of collaboration of (public) cloud-based SSE solutions and the stronger security guarantees of self-hosted storage (which can be further improved through SSE). In general, which type of SSE should be used depends on the application (e.g., keyword search or geometric range search on spatial data), the efficiency, and the security requirements.
4 Conclusion
SSE provides the necessary tools to ensure privacy for the transitions of different sectors from local storage to cloud-based remote storage. The benefits of cloud-based services have been shown over the last decade for virtually all sectors. Moreover, this trend of moving data to the cloud does not show any signs of slowing down, making efficient and secure SSE solutions a vital tool for Switzerland in the coming years. However, the secure usage of SSE approaches is very challenging; thus, data security needs to be carefully assessed, especially in the case of highly sensitive information.
References
Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky. Searchable symmetric encryption: Improved definitions and efficient constructions. Journal of Computer Security, 19(5):895–934, November 2011.
Rakesh Agrawal, Jerry Kiernan, Ramakrishnan Srikant, and Yirong Xu. Order preserving encryption for numeric data. In Proceedings of the ACM international conference on Management of data, SIGMOD ’04. ACM Press, 2004.
Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O'Neill. Generic attacks on secure outsourced databases. CCS ’16. ACM, oct 2016.
Dawn Xiaoding Song, D. Wagner, and A. Perrig. Practical techniques for searches on encrypted data. In Proceeding 2000 IEEE Symposium on Security and Privacy. S&P 2000, pages 44–55, May 2000. ISSN: 1081-6011.
Seny Kamara, Charalampos Papamanthou, and Tom Roeder. Dynamic searchable symmetric encryption. In Proceedings of the 2012 ACM conference on Computer and communications security - CCS ’12, page 965, Raleigh, North Carolina, USA, 2012. ACM Press.
Shi-Feng Sun, Ron Steinfeld, Shangqi Lai, Xingliang Yuan, Amin Sakzad, Joseph Liu, Surya Nepal, and Dawu Gu. Practical Non-Interactive Searchable Encryption with Forward and Backward Privacy. In Proceedings 2021 Network and Distributed System Security Symposium, Virtual, 2021. Internet Society.
Tianyang Chen, Peng Xu, Wei Wang, Yubo Zheng, Willy Susilo, and Hai Jin. Bestie: Very Practical Searchable Encryption with Forward and Backward Security. In Computer Security – ESORICS 2021: 26th European Symposium on Research in Computer Security, Darmstadt, Germany, October 4–8, 2021, Proceedings, Part II, pages 3–23, Berlin, Heidelberg, October 2021. Springer-Verlag.
Paul Grubbs, Richard McPherson, Muhammad Naveed, Thomas Ristenpart, and Vitaly Shmatikov. Breaking Web Applications Built On Top of Encrypted Data. pages 1353–1364, October 2016.
Francesca Falzon, Evangelia Anna Markatou, Akshima, David Cash, Adam Rivkin, Jesse Stern, and Roberto Tamassia. Full Database Reconstruction in Two Dimensions. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, CCS ’20, pages 443–460, New York, NY, USA, October 2020. Association for Computing Machinery.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2023 The Author(s)
About this chapter
Cite this chapter
Krähenbühl, C., Perrig, A. (2023). Searchable Symmetric Encryption. In: Mulder, V., Mermoud, A., Lenders, V., Tellenbach, B. (eds) Trends in Data Protection and Encryption Technologies . Springer, Cham. https://doi.org/10.1007/978-3-031-33386-6_14
Download citation
DOI: https://doi.org/10.1007/978-3-031-33386-6_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-33385-9
Online ISBN: 978-3-031-33386-6
eBook Packages: Computer ScienceComputer Science (R0)