Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE European Symposium on Security and Privacy

Conjunctive Searchable Symmetric Encryption from Hard Lattices

Debadrita Talapatra, Sikhar Patranabis, Debdeep Mukhopadhyay

Published Jul 1, 2023• 11 citations
Publisher

Abstract

Searchable Symmetric Encryption (SSE) supports efficient keyword searches over encrypted outsourced document collections while minimizing information leakage. All practically efficient SSE schemes supporting conjunctive queries rely crucially on quantum-broken cryptographic assumptions (such as discrete-log hard groups) to achieve compact storage and fast query processing. On the other hand, quantum-safe SSE schemes based on purely symmetric-key cryptoprimitives either do not support conjunctive searches, or are practically inefficient. In particular, there exists no quantum-safe yet practically efficient conjunctive SSE scheme from lattice-based hardness assumptions.We solve this open question by proposing Oblivious Post-Quantum Secure Cross Tags (OQXT) – the first lattice-based practically efficient and highly scalable conjunctive SSE scheme. The technical centerpiece of OQXT is a novel oblivious cross-tag generation protocol with provable security guarantees derived from lattice-based hardness assumptions. We prove the post-quantum simulation security of OQXT with respect to a rigorously defined and thoroughly analyzed leakage profile. We then present a prototype implementation of OQXT and experimentally validate its practical efficiency and scalability over extremely large real-world databases. Our experiments show that OQXT has competitive end-to-end search latency when compared with the best (quantum-broken) conjunctive SSE schemes.

DOI
10.1109/eurosp57164.2023.00061

Related papers

QPASE: Quantum-Resistant Password-Authenticated Searchable Encryption for Cloud Storage

Jingwei Jiang, Ding Wang

Searchable encryption is a powerful tool that enables secure and private searches of encrypted data. It allows users to outsource their data to cloud servers while maintaining the confidentiality and privacy of their data. Password-authenticated symmetric searchable encryption (PASE) can help users avoid the complexity and security risks associated with key management while maintaining the advantages of searchable encryption. To the best of our knowledge, none of the existing PASE schemes can resist security threats in the post-quantum era, and there is an urgent need to design quantum-resistant solutions. However, post-quantum cryptography (e.g., lattice-based cryptography) varies significantly from traditional cryptography, and it is challenging to design a quantum-resistant PASE for cloud storage. In this work, we take the first step towards this challenge by proposing QPASE, a quantum-resistant password-authenticated symmetric searchable encryption for cloud storage. We employ lattice-based threshold oblivious pseudorandom function (TOPRF) to achieve password re-randomization and formally prove that QPASE is authentication secure and indistinguishability against chosen keyword attacks (IND-CKA) secure under quantum computers. QPASE can be extended to multi-keyword search and allows servers to update keys without affecting the users. The comparison results show that QPASE outperforms its foremost counterparts in security and computation overhead.

IEEE Transactions on Information Forensics and Security•Jan 1, 2024•26 citations

Secure and Privacy-Preserving Post-Quantum Attribute-Based Searchable Encryption for Edge-Driven Transportation Systems

Chintureena Thingom, Bhagavan Konduri, Isha Das +6 more

To address the risks of data leakage and unauthorized access in Intelligent Transportation Systems (ITS), particularly in the post-quantum era where traditional cryptographic algorithms are vulnerable, this paper proposes a novel Post-Quantum Attribute-Based Searchable Encryption (PQ-ABSE) scheme. The scheme is designed to resist quantum attacks while providing privacy-preserving search, key aggregation, and lightweight computation. The proposed PQ-ABSE scheme ensures end-to-end privacy protection during key generation, access control, and partial decryption phases. By embedding search keywords into the access policy, it achieves partial policy hiding and ensures keyword confidentiality under quantum-resilient assumptions. Moreover, by leveraging key aggregation techniques, the scheme consolidates all file identifiers that meet both the search and access conditions into a single aggregate key, significantly reducing user-side key storage overhead while ensuring file and data security. Security analysis confirms that the scheme achieves hidden access structure security, keyword ciphertext indistinguishability, and trapdoor indistinguishability in a post-quantum setting. Theoretical analysis and simulation results further demonstrate the scheme’s practicality and efficiency in terms of both computational and communication overhead, making it a promising solution for post-quantum secure ITS data management.

IEEE Transactions on Consumer Electronics•Nov 12, 2025•5 citations

Lattice-based searchable public-key encryption scheme for secure cloud storage

Run Xie, Chunxiang Xu, Chanlian He +1 more

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.

International Journal of Web and Grid Services•Nov 13, 2017•11 citations

Semantic Searchable Encryption Scheme based on Lattice in Quantum-era

Yang Yang, Maode Ma

Abstract. When data is outsourced to a remote storage server, search-able encryption plays an important role to protect data privacy while allowing users to retrieve data in the massive ciphertext. As far as we know, most of the existing searchable encryption schemes work based on the bilinear map. These schemes may not be secure in the quantum age. Both discrete logarithms and factorization can be solved by quantum computer in a polynomial time. There is very few searchable encryption scheme that can be proved secure in post quantum age. In this paper, in order to construct a post-quantum secure scheme for future cloud stor-age, we suggest a public key encryption with semantic keyword search using the lattice based mechanism. The suggested scheme is proved se-cure against indistinguishable chosen-keyword attacks (IND-CKA) based on learning with errors (LWE) problem. This scheme is believed to be secure in quantum-era due to the quantum intractability of the LWE problem.

Journal of information science and engineering•Jan 1, 2016•11 citations

An Efficient Lattice-Based Verifiable Public-Key Authenticated Encryption With Keyword Search Scheme

Saba Karimani, Taraneh Eghlidos

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.

IEEE Access•Jan 1, 2025•1 citation

Multi-Writer Searchable Encryption: An LWE-based Realization and Implementation

Lei Xu, Xingliang Yuan, Ron Steinfeld +2 more

Multi-Writer Searchable Encryption, also known as public-key encryption with keyword search(PEKS), serves a wide spectrum of data sharing applications. It allows users to search over encrypted data encrypted via different keys. However, most of the existing PEKS schemes are built on classic security assumptions, which are proven to be untenable to overcome the threats of quantum computers. To address the above problem, in this paper, we propose a lattice-based searchable encryption scheme from the learning with errors (LWE) hardness assumption. Specifically, we observe that the keys of each user in a basic scheme are composed of large-sized matrices and basis of the lattice. To reduce the complexity of key management, our scheme is designed to enable users to directly use their identity for data encryption. We present several optimization techniques for implementation to make our design nearly practical. For completeness, we conduct rigorous security, complexity, and parameter analysis on our scheme, and perform comprehensive evaluations at a commodity machine. With a scenario of 100 users, the cost of key generation for each user is 125s, and the cost of searching a document with 1000 keywords is 13.4ms.

ACM Asia Conference on Computer and Communications Security (ASIA CCS)•Jul 2, 2019•39 citations
Searchable Symmetric Encryption (SSE) supports efficient keyword searches over encrypted outsourced document collections while minimizing information leakage. All practically efficient SSE schemes supporting conjunctive queries rely crucially on quantum-broken cryptographic assumptions (such as discrete-log hard groups) to achieve compact storage and fast query processing. On the other hand, quantum-safe SSE schemes based on purely symmetric-key cryptoprimitives either do not support conjunctive searches, or are practically inefficient. In particular, there exists no quantum-safe yet practically efficient conjunctive SSE scheme from lattice-based hardness assumptions.We solve this open question by proposing Oblivious Post-Quantum Secure Cross Tags (OQXT) – the first lattice-based practically efficient and highly scalable conjunctive SSE scheme. The technical centerpiece of OQXT is a novel oblivious cross-tag generation protocol with provable security guarantees derived from lattice-based hardness assumptions. We prove the post-quantum simulation security of OQXT with respect to a rigorously defined and thoroughly analyzed leakage profile. We then present a prototype implementation of OQXT and experimentally validate its practical efficiency and scalability over extremely large real-world databases. Our experiments show that OQXT has competitive end-to-end search latency when compared with the best (quantum-broken) conjunctive SSE schemes.
Searchable encryption is a powerful tool that enables secure and private searches of encrypted data. It allows users to outsource their data to cloud servers while maintaining the confidentiality and privacy of their data. Password-authenticated symmetric searchable encryption (PASE) can help users avoid the complexity and security risks associated with key management while maintaining the advantages of searchable encryption. To the best of our knowledge, none of the existing PASE schemes can resist security threats in the post-quantum era, and there is an urgent need to design quantum-resistant solutions. However, post-quantum cryptography (e.g., lattice-based cryptography) varies significantly from traditional cryptography, and it is challenging to design a quantum-resistant PASE for cloud storage. In this work, we take the first step towards this challenge by proposing QPASE, a quantum-resistant password-authenticated symmetric searchable encryption for cloud storage. We employ lattice-based threshold oblivious pseudorandom function (TOPRF) to achieve password re-randomization and formally prove that QPASE is authentication secure and indistinguishability against chosen keyword attacks (IND-CKA) secure under quantum computers. QPASE can be extended to multi-keyword search and allows servers to update keys without affecting the users. The comparison results show that QPASE outperforms its foremost counterparts in security and computation overhead.
To address the risks of data leakage and unauthorized access in Intelligent Transportation Systems (ITS), particularly in the post-quantum era where traditional cryptographic algorithms are vulnerable, this paper proposes a novel Post-Quantum Attribute-Based Searchable Encryption (PQ-ABSE) scheme. The scheme is designed to resist quantum attacks while providing privacy-preserving search, key aggregation, and lightweight computation. The proposed PQ-ABSE scheme ensures end-to-end privacy protection during key generation, access control, and partial decryption phases. By embedding search keywords into the access policy, it achieves partial policy hiding and ensures keyword confidentiality under quantum-resilient assumptions. Moreover, by leveraging key aggregation techniques, the scheme consolidates all file identifiers that meet both the search and access conditions into a single aggregate key, significantly reducing user-side key storage overhead while ensuring file and data security. Security analysis confirms that the scheme achieves hidden access structure security, keyword ciphertext indistinguishability, and trapdoor indistinguishability in a post-quantum setting. Theoretical analysis and simulation results further demonstrate the scheme’s practicality and efficiency in terms of both computational and communication overhead, making it a promising solution for post-quantum secure ITS data management.
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.
Abstract. When data is outsourced to a remote storage server, search-able encryption plays an important role to protect data privacy while allowing users to retrieve data in the massive ciphertext. As far as we know, most of the existing searchable encryption schemes work based on the bilinear map. These schemes may not be secure in the quantum age. Both discrete logarithms and factorization can be solved by quantum computer in a polynomial time. There is very few searchable encryption scheme that can be proved secure in post quantum age. In this paper, in order to construct a post-quantum secure scheme for future cloud stor-age, we suggest a public key encryption with semantic keyword search using the lattice based mechanism. The suggested scheme is proved se-cure against indistinguishable chosen-keyword attacks (IND-CKA) based on learning with errors (LWE) problem. This scheme is believed to be secure in quantum-era due to the quantum intractability of the LWE problem.
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.
Multi-Writer Searchable Encryption, also known as public-key encryption with keyword search(PEKS), serves a wide spectrum of data sharing applications. It allows users to search over encrypted data encrypted via different keys. However, most of the existing PEKS schemes are built on classic security assumptions, which are proven to be untenable to overcome the threats of quantum computers. To address the above problem, in this paper, we propose a lattice-based searchable encryption scheme from the learning with errors (LWE) hardness assumption. Specifically, we observe that the keys of each user in a basic scheme are composed of large-sized matrices and basis of the lattice. To reduce the complexity of key management, our scheme is designed to enable users to directly use their identity for data encryption. We present several optimization techniques for implementation to make our design nearly practical. For completeness, we conduct rigorous security, complexity, and parameter analysis on our scheme, and perform comprehensive evaluations at a commodity machine. With a scenario of 100 users, the cost of key generation for each user is 125s, and the cost of searching a document with 1000 keywords is 13.4ms.