Overview of Searchable Encryption Technology

Abstract

Searchable encryption technology is a method for protecting user privacy, widely applied in data sharing, cloud computing, and location privacy protection. This article mainly introduces the basic knowledge, implementation methods, security threats, application scenarios, and future development directions of this technology. The article first introduces the concept of searchable encryption, then discusses existing symmetric searchable encryption and asymmetric searchable encryption technologies, exploring their potential security threats. Finally, the article briefly outlines the application scenarios of searchable encryption technology and summarizes its future development directions. This article aims to provide the public with a comprehensive overview to preliminarily understand the concepts, applications, and security threats of searchable encryption technology.

1. Introduction

With the rapid development of cloud services, more and more users are storing personal data on cloud servers, which not only provides convenience but also leads to an increase in data leakage incidents. To protect data privacy, encryption technology has become an important means. However, with the increase and dispersion of data, traditional encryption methods can no longer meet the needs of large-scale data usage. In this context, Searchable Encryption (SE) technology has emerged.

Searchable encryption technology is an emerging method for ciphertext retrieval, which allows data to be encrypted and stored in the cloud without exposing plaintext, and then queries can be performed on the ciphertext. To achieve encrypted data retrieval, Song et al. [1] utilized symmetric encryption algorithms to encrypt keywords and encrypted the data information using an XOR operation between keyword ciphertext and stream ciphertext to obtain Ciphertext, as shown in Figure 1-1. When a keyword needs to be queried, the user can first generate a stream ciphertext A, then XOR the query keyword ciphertext with the stored Ciphertext to obtain stream ciphertext B. If stream ciphertext A is the same as stream ciphertext B, it indicates a successful retrieval; otherwise, it indicates failure.

Overview of Searchable Encryption Technology

Figure 1-1 Ciphertext Retrieval Implementation Scheme

Subsequently, other proposals have been made, such as searchable encryption using secure indexes [2], public key searchable encryption based on asymmetric encryption algorithms [3], and fuzzy searchable encryption supporting fuzzy retrieval [4]. The current searchable encryption mainly studies attributes as shown in Figure 1-2.

Figure 1-2 Main Research Attributes of Searchable Encryption

With the development of searchable encryption technology, people can more conveniently perform data retrieval and sharing while avoiding the risk of sensitive data being maliciously leaked and misused. Depending on the implementation method, searchable encryption technology can be divided into Symmetric Searchable Encryption (SSE) and Asymmetric Searchable Encryption (ASE), which will also be introduced from these two perspectives.

2. Symmetric Searchable Encryption Technology

Symmetric searchable encryption mainly relies on symmetric encryption algorithms, and its basic operations include initialization, data encryption, trapdoor generation, search, and data decryption [5]. In symmetric searchable encryption technology, the encryption and decryption processes use the same key, and trapdoor generation also requires the key’s participation. Therefore, this technology is usually suitable for single-user models, characterized by low computational overhead, simple implementation, and fast execution speed.

After Song et al. proposed the first symmetric searchable encryption scheme, several improvements have been made. In 2019, Kermanshahi et al. [6] proposed a multi-client symmetric searchable encryption scheme based on a single-user protocol. This scheme allows users to generate queries through a certain number of “helper” users, protecting the database content from being leaked by the server while hiding the query content from the “helper” users. Through a pseudo-random function, privacy protection for search keywords can be achieved. Additionally, this scheme supports user revocation and quick updates of encryption keys, providing security against passive and active collusion attacks between the server and subset users. In Zheng’s [7] research, they addressed the issue that existing dynamic searchable encryption schemes cannot protect search pattern privacy, leading to the leakage of key information. They first designed an obfuscation technique using k-anonymity and encryption technology. Assuming that the index stored on the server is a key-value pair, each key-value pair is associated with a keyword w, c represents the encrypted file ID, and loc represents the storage location of c, the implementation of the obfuscation technique is shown in Figure 2-1. Then, based on the obfuscation technique, pseudo-random functions, and pseudo-random generators, Zheng et al. designed a dynamic searchable encryption scheme. This scheme supports single-keyword queries while achieving search pattern privacy and enhanced backward privacy. Furthermore, this scheme has been extended to support more efficient Boolean queries. Security analysis shows that this scheme can achieve the required privacy attributes and is also efficient in terms of communication overhead and computational cost.

Figure 2-1 Obfuscation Method When k=3

Wang [8] implemented a symmetric searchable encryption technology that supports search result verification. In the scheme using a Trie tree to construct the index, search performance can be improved by segmenting each keyword label and storing them in the Trie tree, but this also incurs high storage costs. Additionally, when all keyword labels have the same prefix but different last segments, the index will degrade to a linear linked list, greatly affecting search efficiency. To address this issue, they proposed a verifiable symmetric searchable encryption scheme based on AVL trees, referred to as VSSE-AVL. Compared to Trie tree indexing, VSSE-AVL not only balances storage and search performance but also avoids degradation phenomena. Security analysis shows that VSSE-AVL meets privacy and verifiability, and performs better in storage, search, and verification compared to other verifiable searchable encryption schemes with the same level of security.

3. Asymmetric Searchable Encryption Technology

Asymmetric searchable encryption primarily relies on asymmetric encryption algorithms, also known as public key encryption with searching (PEKS). Its basic operations include initialization, public key encryption of data, private key generation of trapdoors, and searching [3]. In asymmetric searchable encryption technology, the encryption and decryption processes use public keys to encrypt plaintext information and retrieve the target ciphertext, while private keys are used to decrypt ciphertext information and generate keyword trapdoors. Compared to symmetric searchable encryption, asymmetric searchable encryption algorithms are more complex and have slower encryption and decryption speeds, usually suitable for many-to-one models.

In Zhang’s [9] work, a secure public key encryption keyword search scheme called SEPSE was proposed. This scheme employs multiple dedicated key servers to assist users in encrypting keywords without learning any keyword information. Meanwhile, SEPSE supports key updates on the key server to resist key leakage. Additionally, they proposed a blockchain-based rate-limiting mechanism and integrated it into SEPSE. Each user’s keyword requests derived from the server are integrated into a transaction on the public blockchain, and the key server can check the number of keyword requests made by that user by examining the number of transactions created by that user, stopping responses once a threshold is reached to resist online keyword attacks. Later, to address the issue that most public key encryption searchable encryption schemes are not suitable for multi-user scenarios, Chenam et al. [10] proposed a multi-user certificateless public key authenticated encryption and joint keyword search scheme based on designated cloud servers (dmCLPAECKS). This scheme ensures that the same document or email is encrypted only once, allowing different recipients to retrieve it, while supporting joint keyword searches. The implementation framework of dmCLPAECKS is shown in Figure 3-1.

Figure 3-1 Framework of dmCLPAECKS

By employing authenticated encryption technology, this scheme can prevent attackers from forging valid ciphertext and sending it to data recipients without knowing the data owner’s private key. Furthermore, this scheme uses designated cloud server technology, so even if attackers retrieve the trapdoor of the data recipient, they cannot perform keyword searches because they do not know the private key of the designated cloud server. Based on this, this scheme can prevent internal keyword guessing attacks under the random oracle model.

4. Security Threats and Defense Mechanisms

4.1 Keyword Guessing Attacks

Keyword guessing attacks [11] occur because the keyword space is much smaller than the key space, and users often use common keywords for retrieval, providing attackers with a shortcut for dictionary attacks. The reasons for keyword guessing attacks can be summarized as follows:

(1) The keyword space is small, and users tend to use common vocabulary, providing attackers with the possibility of traversing the keyword space;

(2) Algorithm consistency constraints allow attackers to have a pre-determination of whether this attack is successful: executing the Test algorithm, returning 1 indicates that the attack is successful; otherwise, they can continue guessing.

Preventive measures: To resist keyword guessing attacks, various searchable encryption schemes resistant to keyword guessing attacks have been proposed [9,10]. By limiting the frequency of query requests or the querying capabilities of users, the risk of malicious adversaries accurately guessing keywords can be prevented.

4.2 File Injection Attacks

In executing file injection attacks [12], attackers send some files to the client, which then encrypts these files using the searchable encryption scheme and uploads them to the server. Attackers can learn a large number of keywords searched by the client by injecting a small number of files. This is a relatively covert attack method, as attackers do not need to directly obtain the client’s private key or trapdoor but only need to observe the encrypted files uploaded by the client. Figure 4-1 illustrates the idea of file injection attacks.

Figure 4-1 Example of File Injection Attack When |K|=8

Assuming that there are 8 keywords in the keyword set K, the attacker injects files File1, File2, and File3, each containing 4 keywords, as shown in the shaded part of the figure. If File2 responds to a certain token while File1 and File3 do not, the corresponding keyword for that token is k2. The basic observation is that if the server injects a file F that contains exactly half of the keywords in the keyword set K, then by observing whether the token t sent by the client matches the file, the server can learn one bit of information about the keyword corresponding to t. Based on this, by injecting a small number of files, the server can accurately determine the keyword.

Preventive measures: Bost et al. proposed the concepts of forward privacy [13] and backward privacy [14] along with implementation schemes. By reducing file updates and historical query information leakage, the risk of users suffering from file injection attacks is avoided.

5. Conclusion

Searchable encryption technology has a wide range of application scenarios, allowing efficient data search and management while protecting data privacy. In the field of cloud computing, searchable encryption technology can help users store and manage sensitive data in the cloud while protecting data privacy. In the field of data sharing, searchable encryption technology can provide better data security and privacy protection capabilities while achieving efficient data retrieval and sharing. In the field of location privacy protection, searchable encryption technology can help users obtain necessary services and information while protecting personal location privacy.

Although significant progress has been made in searchable encryption technology, there are still some areas for improvement. For example, existing searchable encryption technologies still have some security vulnerabilities, necessitating research into new algorithms and protocols to enhance the security and privacy protection capabilities of searchable encryption technology. Furthermore, existing searchable encryption technologies have some limitations in performance, requiring research into new technologies and algorithms to improve the performance and efficiency of searchable encryption technology. Finally, searchable encryption technology can be combined with other security technologies, such as blockchain and differential privacy, to better meet the needs of practical applications.

References

[1] Song D X, Wagner D, Perrig A. Practical techniques for searches on encrypted data[C]//Proceeding 2000 IEEE symposium on security and privacy. S&P 2000. IEEE, 2000: 44-55.

[2] Goh E J. Secure indexes[J]. Cryptology ePrint Archive, 2003.

[3] Boneh D, Di Crescenzo G, Ostrovsky R, et al. Public key encryption with keyword search[C]//Advances in Cryptology-EUROCRYPT 2004: International Conference on the Theory and Applications of Cryptographic Techniques. Springer Berlin Heidelberg, 2004: 506-522.

[4] Li J, Wang Q, Wang C, et al. Enabling efficient fuzzy keyword search over encrypted data in cloud computing[J]. Cryptology ePrint Archive, 2009.

[5] Curtmola R, Garay J, Kamara S, et al. Searchable symmetric encryption: improved definitions and efficient constructions[C]//Proceedings of the 13th ACM conference on Computer and communications security. 2006: 79-88.

[6] Kermanshahi S K, Liu J K, Steinfeld R, et al. Multi-client cloud-based symmetric searchable encryption[J]. IEEE Transactions on Dependable and Secure Computing, 2019, 18(5): 2419-2437.

[7] Zheng Y, Lu R, Shao J, et al. Achieving practical symmetric searchable encryption with search pattern privacy over cloud[J]. IEEE Transactions on Services Computing, 2020, 15(3): 1358-1370.

[8] Wang Q, Zhang X, Qin J, et al. A verifiable symmetric searchable encryption scheme based on the AVL tree[J]. The Computer Journal, 2023, 66(1): 174-183.

[9] Zhang Y, Xu C, Ni J, et al. Blockchain-assisted public-key encryption with keyword search against keyword guessing attacks for cloud storage[J]. IEEE Transactions on Cloud Computing, 2019, 9(4): 1335-1348.

[10] Chenam V B, Ali S T. A designated cloud server-based multi-user certificateless public key authenticated encryption with conjunctive keyword search against IKGA[J]. Computer Standards & Interfaces, 2022, 81: 103603.

[11] Byun J W, Rhee H S, Park H A, et al. Off-line keyword guessing attacks on recent keyword search schemes over encrypted data[C]//Secure Data Management: Third VLDB Workshop. Springer Berlin Heidelberg, 2006: 75-83.

[12] Zhang Y, Katz J, Papamanthou C. All your queries are belong to us: The power of file-injection attacks on searchable encryption[C]//USENIX Security Symposium. 2016: 707-720.

[13] Bost R. ∑ oφoς: Forward secure searchable encryption[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016: 1143-1154.

[14] Bost R, Minaud B, Ohrimenko O. Forward and backward private searchable encryption from constrained cryptographic primitives[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017: 1465-1482.

China Secret Association

Scientific and Technological Branch

Long press to scan the code and follow us

Author: Long Hongping, Institute of Information Engineering, Chinese Academy of Sciences

University of Chinese Academy of Sciences, School of Cybersecurity

Editor: Xia Tiantian

2022 Top 5 Highlights Review

Cross-network Attacks: An Introduction to Techniques for Breaking Physical Isolation

Thoughts on the Top-Level Design of Smart City Security

Revisiting Some New Issues Faced by Digital Forensics Technology Development

Development and Challenges of Low-Earth Orbit Satellite Interconnection Networks

Introduction to LaserShark Non-contact Attack Implant Technology

Recent Highlights Review

Security Analysis of Electric Vehicle Charging Station Management Systems

Summary of Common Cybersecurity Threats and Protection Technologies

A Brief Analysis of Security Algorithm and Protocol Verification Issues

A Brief Analysis of IoT Security Issues in Blockchain

Overview of Federated Learning Security

Related posts

Leave a Comment Cancel reply