A lot of interest has been drawn recently into public-key encryption with keyword search (PEKS), which keeps publickey encrypted documents amendable to secure keyword search. However, PEKS resist against keyword guessing attack by assuming that the size of the keyword space is beyond the polynomial level. But this assumption is ineffective in practice. PEKS are insecure under keyword guessing attack. As we observe, the key to defend such attack is to avoid the availability of the exact search trapdoor to adversaries. Accordingly, we compromise the exactness of search trapdoor by mapping at least two different keywords into a fuzzy search trapdoor. We propose a novel concept called public-key encryption with fuzzy keyword search (PEFKS), by which the un-trusted server only obtains the fuzzy search trapdoor instead of the exact search trapdoor, and define its semantic security under chosen keyword attack (SS-CKA) and indistinguishability of keywords under non-adaptively chosen keywords and keyword guessing attack (IK-NCK-KGA). For the keyword space with and without uniform distribution, we respectively present two universal transformations from anonymous identity-based encryption to PEFKS, and prove their SSCKA and IK-NCK-KGA securities. To our knowledge, PEFKS is the first scheme to resist against keyword guessing attack on condition that the keyword space is not more than the polynomial level.
A lot of interest has been drawn recently into public-key encryption with keyword search (PEKS), which keeps publickey encrypted documents amendable to secure keyword search. However, PEKS resist against keyword guessing attack by assuming that the size of the keyword space is beyond the polynomial level. But this assumption is ineffective in practice. PEKS are insecure under keyword guessing attack. As we observe, the key to defend such attack is to avoid the availability of the exact search trapdoor to adversaries. Accordingly, we compromise the exactness of search trapdoor by mapping at least two different keywords into a fuzzy search trapdoor. We propose a novel concept called public-key encryption with fuzzy keyword search (PEFKS), by which the un-trusted server only obtains the fuzzy search trapdoor instead of the exact search trapdoor, and define its semantic security under chosen keyword attack (SS-CKA) and indistinguishability of keywords under non-adaptively chosen keywords and keyword guessing attack (IK-NCK-KGA). For the keyword space with and without uniform distribution, we respectively present two universal transformations from anonymous identity-based encryption to PEFKS, and prove their SSCKA and IK-NCK-KGA securities. To our knowledge, PEFKS is the first scheme to resist against keyword guessing attack on condition that the keyword space is not more than the polynomial level.
With the improvement of awareness of data privacy, the user's sensitive data are usually encrypted before uploading them to cloud. Searchable encryption is a critical technique on promoting secure and efficient cloud storage. In particular, publickey encryption with keyword search (PEKS) provides an elegant approach to achieve data retrieval in encrypted storage. All existing searchable publickey encryption schemes only provide the security based on classical cryptography hardness assumption. With the development of quantum computers, these schemes will be insecure. Based on the lattice hardness assumptions, we propose a new searchable publickey encryption scheme with a designated tester (dPEKS). Our scheme has advantages: First, our scheme is the first searchable publickey encryption scheme that is considered to be secure even if quantum computers are ever developed. Second, our scheme achieves the trapdoor indistinguishability. The trapdoor indistinguishability implies the security against outside offline keyword guessing attacks (KGAs). Last, our scheme can achieve the trapdoor anonymity for server.
Public key encryption scheme with keyword search (PEKS) enables us to search the encrypted data in a cloud server with a keyword, and no one can obtain any information about the encrypted data without the trapdoor corresponding to the keyword. The PEKS is useful to keep the management of large data storages secure such as those in a cloud. In this paper, to protect against quantum computer attacks, we present a lattice-based identity-based encryption scheme with keyword search. We have proved that our scheme can achieve ciphertext indistinguishability in the random oracle model, and our scheme can also achieve trapdoor security. In particular, our scheme can designate a unique tester to test and return the search results, therefore it does not need a secure channel. To the best of our knowledge, our scheme is the first identity- based encryption scheme with keyword search from lattice assumption.
With the rapid development of cloud computing, an increasing number of companies are adopting cloud storage technology to reduce overhead. However, to ensure the privacy of sensitive data, the uploaded data need to be encrypted before being outsourced to the cloud. The concept of public-key encryption with keyword search (PEKS) was introduced by Boneh et al. to provide flexible usage of the encrypted data. Unfortunately, most of the PEKS schemes are not secure against inside keyword guessing attacks (IKGA), so the keyword information of the trapdoor may be leaked to the adversary. To solve this issue, Huang and Li presented public key authenticated encryption with keyword search (PAEKS) in which the trapdoor generated by the receiver is only valid for authenticated ciphertexts. With their seminal work, many PAEKS schemes have been introduced for the enhanced security of PAEKS. Some of them further consider the upcoming quantum attacks. However, our cryptanalysis indicated that in fact, these schemes could not withstand IKGA. To fight against the attacks from quantum adversaries and support the privacy-preserving search functionality, we first introduce a novel generic PAEKS construction in this work. Then, we further present the first quantum-resistant PAEKS instantiation based on lattices. The security proofs show that our instantiation not only satisfies the basic requirements but also achieves enhanced security models, namely the multi-ciphertext indistinguishability and multi-trapdoor privacy. Furthermore, the comparative results indicate that with only some additional expenditure, the proposed instantiation provides more secure properties, making it suitable for more diverse application environments.
With the improvement of awareness of data privacy, the user's sensitive data are usually encrypted before uploading them to cloud. Searchable encryption is a critical technique on promoting secure and efficient cloud storage. In particular, publickey encryption with keyword search (PEKS) provides an elegant approach to achieve data retrieval in encrypted storage. All existing searchable publickey encryption schemes only provide the security based on classical cryptography hardness assumption. With the development of quantum computers, these schemes will be insecure. Based on the lattice hardness assumptions, we propose a new searchable publickey encryption scheme with a designated tester (dPEKS). Our scheme has advantages: First, our scheme is the first searchable publickey encryption scheme that is considered to be secure even if quantum computers are ever developed. Second, our scheme achieves the trapdoor indistinguishability. The trapdoor indistinguishability implies the security against outside offline keyword guessing attacks (KGAs). Last, our scheme can achieve the trapdoor anonymity for server.
Searchable encryption enables efficient retrieval of encrypted data stored in cloud environments while preserving data confidentiality. Within this context, Public Key Encryption with Keyword Search (PEKS) allows data users to perform keyword-based searches using their public-private key pairs. However, traditional PEKS schemes remain vulnerable to Inside Keyword Guessing Attacks (IKGA), which led to the introduction of the Public-Key Authenticated Encryption with Keyword Search (PAEKS) paradigm to enhance resilience against insider threats. Despite this advancement, most existing PAEKS schemes rely on number-theoretic assumptions, such as the discrete logarithm problem, thereby becoming insecure in the presence of against quantum adversaries. Consequently, recent research has focused on developing quantum-resistant, lattice-based PAEKS schemes. Although schemes based on the Learning with Errors (LWE) problem provide strong post-quantum security, they often incur high computational and communication costs, limiting their practicality in large-scale cloud environments. To overcome these limitations, this work presents an efficient and verifiable PAEKS scheme based on the Middle-Product LWE (MP-LWE) problem, which preserves the underlying security guarantees while significantly improving performance. Formal security analysis demonstrates resistance against Chosen Keyword Attack (CKA) and IKGA in the random oracle (RO) model. Experimental results confirm that the proposed scheme achieves substantially lower computational and communication overheads compared to existing schemes, while maintaining robust post-quantum security.
Since the convenience and advancement of cloud applications, many users (e.g., companies or individuals) adopt remote cloud services to reduce the local storage overload and computing consumption. However, before transferring them to the cloud server, users always encrypt outsourced data for the privacy of important data, which deprives flexible usage of these data. Public key encryption with keyword search (PEKS) undoubtedly offers a precise resolution to this issue. Unfortunately, most PEKS schemes cannot fight against quantum computing attackers, which is increasingly a research hotspot. To achieve postquantum security and privacy-preserving search function, we propose a quantum-resistant PEKS scheme named IsoqurPEKS. Our proposed instantiation satisfies basic semantic security indistinguishable against chosen keyword attack (IND-CKA), and IsoqurPEKS is proved to be secure under the security model. Furthermore, we compare IsoqurPEKS with the other eight current PEKS schemes with respect to security properties, communication, and computation costs. The comparison results indicate that the proposed scheme has the best security and performance among the nine PEKS schemes.