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

Electronics

Post-Quantum Private Set Intersection with Ultra-Efficient Online Performance

Yue Qin, Bei Liang, Hongyuan Cai, Jíntai Ding

Published Dec 19, 2025• 0 citations
Publisher

Abstract

While tremendous progress has been made towards achieving highly efficient and practical Private Set Intersection (PSI) protocols during the last decade, the development of post-quantum PSI is still far from satisfactory. Existing post-quantum PSI protocols encounter a dilemma: while those based on fully homomorphic encryption (FHE) achieve low online communication, they suffer from significant online computation; conversely, protocols based on post-quantum Oblivious Pseudorandom Functions (OPRFs) exhibit excellent online computational performance but incur substantially high online communication. To overcome this dilemma, we present a lattice-based PSI protocol that achieves optimal online performance in both communication and computation. Our solution introduces two core innovations: a robust signal comparison algorithm based on RLWE key exchange, which determines the intersection through signal consistency rather than direct shared key comparison, and an optimized Oblivious Key–Value Stores (OKVS) implementation featuring a composite key–value mapping for efficient handling of high-dimensional RLWE polynomials. We implement the protocol and conduct extensive benchmarks in both symmetric and asymmetric set-size settings. The results show that our construction achieves the lowest online overhead in both computation and communication among all tests. For example, with asymmetric set sizes (212,11041), the online phase requires only 0.132 s, yielding 19× and 282× improvements over FHE-based (CCS’21) and OPRF-based (EUROCRYPT’25) protocols, respectively. Even at (224,11041), our online communication time is only 0.201 s, which is 226× and 184× that of FHE-based and OPRF-based PSI, respectively. Additionally, our online communication overhead is the lowest in all tests; however, this comes at the cost of heavy offline communication overhead for very large set sizes, revealing a clear trade-off between pre-computation and online efficiency. This work addresses a critical gap in post-quantum PSI by delivering a protocol that achieves balanced online communication and computational overhead, thereby enabling broader practical deployment.

DOI
10.3390/electronics15010013

Related papers

A Signal‐Matching Approach to RLWE‐Based PSI: Achieving Optimal Online Efficiency in 3 Rounds

Yue Qin, Bei Liang, Hongyuan Cai +2 more

In this study, we propose a novel post‐quantum private set intersection (PSI) protocol based on the ring learning with errors (RLWE) assumption. Different from existing PSI protocols based on post‐quantum oblivious pseudorandom functions (EUROCRYPT’25) and fully homomorphic encryption (FHE) (CCS’21), our construction follows the Diffie–Hellman (DH)‐based PSI paradigm and uses post‐quantum key exchange to achieve PSI functionality. Our key technique is a signal matching (SigMa) mechanism, which determines whether two items match by checking the consistency of the reconciliation signals derived from their corresponding shared keys. The resulting PSI protocol completes in three rounds. In the first two rounds, the parties exchange RLWE‐based public keys associated with their items; in the third round, the sender transmits the corresponding signals. The receiver then applies SigMa to compare the received signals with its locally computed signals and thereby identify the intersection. We implement our protocol and compare it with Cong et al. (CCS’21) and Heimberger et al. (EUROCRYPT’25). Our protocol achieves the lowest online communication across all evaluated symmetric and asymmetric set‐size configurations, at the cost of additional offline communication. It also achieves the lowest online and total times among the evaluated protocols for all symmetric settings with | X | = | Y | ∈ {2 12 , 2 16 , 2 20 } and all asymmetric settings with | X | ∈ {2 12 , 2 16 , 2 20 } and | Y | ∈ {5535, 11041}. We believe that our work not only supplements existing post‐quantum PSI frameworks but also opens the opportunity for broader applications of post‐quantum PSI.

IET Information Security•Jan 1, 2026•0 citations

On the Homomorphic Properties of Kyber and McEliece with Application to Post-Quantum Private Set Intersection

Anas Ahmad Abudaqa, Khaled A. Alshehri, Muhamad Felemban

Crystals-Kyber and Classic-McEliece are two prominent post-quantum key encapsulation mechanisms (KEMs) designed to address the challenges posed by quantum computing to classical cryptographic schemes. While the former has been standardized by the National Institute of Standards and Technology (NIST), the latter is well-known for its exceptional robustness and as one of the finalists of the fourth round of post-quantum cryptography standardization. Private set intersection (PSI) is a privacy-preserving technique that enables two parties, each possessing a dataset, to compute the intersection of their sets without revealing anything else. This can be achieved thanks to homomorphic encryption (HE), which allows computations on encrypted data. In this paper, firstly, we study Kyber and McEliece, apart from being KEMs, as post-quantum public key encryption (PKE), and examine their homomorphic properties. Secondly, we design two different two-party PSI protocols that utilize the homomorphic capabilities of Kyber and McEliece. Thirdly, a practical performance evaluation under NIST’s security levels 1, 3, and 5 is conducted, focusing on three key metrics: storage overhead, communication overhead, and computation cost. Insights indicate that the Kyber-based PSI Protocol, which utilizes the multiplicative homomorphic property, is secure but less efficient. In contrast, the McEliece-based PSI protocol, while efficient in practice, raises concerns regarding its security as a homomorphic encryption scheme.

Cryptography•Oct 20, 2025•2 citations

Efficient Post-Quantum OPRF from TFHE Key Transformation with Application to OPAQUE

Mihail Plesa, Robert Poenaru, S Ebert David

Abstract We present a highly efficient post-quantum Randomized Oblivious Pseudorandom Function (OPRF) construction based on a novel TFHE key transformation technique. Unlike prior lattice-based OPRF schemes that rely on complex homomorphic PRF evaluation, our approach leverages the algebraic structure of TFHE to enable direct ciphertext transformation, resulting in significant performance improvements. Our protocol achieves strong security under the Learning With Errors (LWE) assumption and provides session unlinkability, making it well-suited for privacy-preserving applications. We demonstrate the practical efficiency of our construction with a Rust implementation, achieving substantial speedups over existing schemes. Furthermore, we show how our Randomized OPRF can be adapted for use in the OPAQUE password-authenticated key exchange protocol by employing a singularization technique to ensure deterministic outputs when required. This work highlights a new, practical path for post-quantum OPRFs with strong privacy and efficiency guarantees.

•Mar 18, 2026•0 citations

Turning Uncertainty into Efficiency: Toward Practical, Quantum-Resistant Verifiable Privacy Tools

Jie Xu

Verifiable Random Functions (VRFs) and Oblivious Pseudorandom Functions (OPRFs) are essential cryptographic primitives in privacy-preserving applications such as anonymous authentication, private set intersection (PSI), and decentralized identity. Existing constructions, however, rely on number-theoretic assumptions that are vulnerable to quantum attacks. This PhD research project focuses on constructing efficient and practical VRFs and OPRFs from lattice-based assumptions to ensure post-quantum security. A key obstacle in these constructions is the overhead of zero-knowledge proofs (ZKPs), particularly range proofs, which are costly in terms of size and prover complexity. To address this, we investigate probabilistic techniques that relax exact correctness. In particular, we explore approximate range proofs and algebraic transformations, such as using automorphisms in polynomial rings to simulate inner product arguments via polynomial multiplication. These methods enable more efficient and scalable lattice-based constructions of VRFs, including group and context-bound variants, as well as OPRFs. The goal is to make these primitives practical for deployment in post-quantum privacy-preserving systems.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 19, 2025•0 citations

Efficient post-quantum private set-intersection protocol

Sumit Kumar Debnath, Nibedita Kundu, Tanmay Choudhury

Private set intersection (PSI) is a cryptographic protocol that enables two parties to securely determine the intersection of their private datasets without revealing anything except the intersection. Most of the existing PSI protocols are based on traditional number theoretic problems, such as discrete logarithm problem and factorisation problem. Unfortunately, these protocols would be broken if efficient quantum computer emerges. The post-quantum PSI is an important alternative to traditional PSI protocols for its potential to resist future attacks of quantum computers. In this work, we present first post-quantum PSI protocol that achieves size-hiding property. Space-efficient probabilistic data structure Bloom filter along with lattice-based public key encryption are used as building blocks of our construction. It attains linear complexity and security in standard model under the decisional learning with errors (DLWE) assumption. Moreover, we extend our post-quantum PSI to its authorised variant APSI retaining all the properties.

International Journal of Information and Computer Security•Jan 1, 2022•2 citations

Updatable Private Set Intersection with Low Communication Overhead

Chao Qi, Mingmei Zheng, Aoxiang Xu +3 more

Private set intersection (PSI) is a fundamental cryptographic task that allows two mutually distrusting parties, each holding a private set of elements, to jointly compute the intersection of their sets. It ensures a symmetric information structure where neither party gains any knowledge about the other’s elements beyond those in the shared intersection. Traditional PSI protocols are primarily designed for static settings, which limits their applicability and efficiency in dynamic scenarios where input sets continuously evolve. To address this challenge, the notion of updatable PSI (UPSI) was introduced, enabling repeated PSI computations over changing inputs while preserving the symmetric privacy guarantees between participants. Despite the numerous recent advancements in UPSI research, it still suffers from significant communication overhead. In this paper, we address this challenge by introducing LcUPSI (low-communication UPSI), a new updatable PSI protocol that achieves remarkably low communication overhead. We formally prove that LcUPSI is secure in the semi-honest model. Furthermore, we compare the LcUPSI protocol with the state-of-the-art UPSI protocol BMSTZ24 (ASIACRYPT). The results demonstrate that LcUPSI significantly reduces communication overhead, highlighting its advantages in low-bandwidth conditions.

Symmetry•Apr 12, 2026•0 citations
While tremendous progress has been made towards achieving highly efficient and practical Private Set Intersection (PSI) protocols during the last decade, the development of post-quantum PSI is still far from satisfactory. Existing post-quantum PSI protocols encounter a dilemma: while those based on fully homomorphic encryption (FHE) achieve low online communication, they suffer from significant online computation; conversely, protocols based on post-quantum Oblivious Pseudorandom Functions (OPRFs) exhibit excellent online computational performance but incur substantially high online communication. To overcome this dilemma, we present a lattice-based PSI protocol that achieves optimal online performance in both communication and computation. Our solution introduces two core innovations: a robust signal comparison algorithm based on RLWE key exchange, which determines the intersection through signal consistency rather than direct shared key comparison, and an optimized Oblivious Key–Value Stores (OKVS) implementation featuring a composite key–value mapping for efficient handling of high-dimensional RLWE polynomials. We implement the protocol and conduct extensive benchmarks in both symmetric and asymmetric set-size settings. The results show that our construction achieves the lowest online overhead in both computation and communication among all tests. For example, with asymmetric set sizes (212,11041), the online phase requires only 0.132 s, yielding 19× and 282× improvements over FHE-based (CCS’21) and OPRF-based (EUROCRYPT’25) protocols, respectively. Even at (224,11041), our online communication time is only 0.201 s, which is 226× and 184× that of FHE-based and OPRF-based PSI, respectively. Additionally, our online communication overhead is the lowest in all tests; however, this comes at the cost of heavy offline communication overhead for very large set sizes, revealing a clear trade-off between pre-computation and online efficiency. This work addresses a critical gap in post-quantum PSI by delivering a protocol that achieves balanced online communication and computational overhead, thereby enabling broader practical deployment.
In this study, we propose a novel post‐quantum private set intersection (PSI) protocol based on the ring learning with errors (RLWE) assumption. Different from existing PSI protocols based on post‐quantum oblivious pseudorandom functions (EUROCRYPT’25) and fully homomorphic encryption (FHE) (CCS’21), our construction follows the Diffie–Hellman (DH)‐based PSI paradigm and uses post‐quantum key exchange to achieve PSI functionality. Our key technique is a signal matching (SigMa) mechanism, which determines whether two items match by checking the consistency of the reconciliation signals derived from their corresponding shared keys. The resulting PSI protocol completes in three rounds. In the first two rounds, the parties exchange RLWE‐based public keys associated with their items; in the third round, the sender transmits the corresponding signals. The receiver then applies SigMa to compare the received signals with its locally computed signals and thereby identify the intersection. We implement our protocol and compare it with Cong et al. (CCS’21) and Heimberger et al. (EUROCRYPT’25). Our protocol achieves the lowest online communication across all evaluated symmetric and asymmetric set‐size configurations, at the cost of additional offline communication. It also achieves the lowest online and total times among the evaluated protocols for all symmetric settings with | X | = | Y | ∈ {2 12 , 2 16 , 2 20 } and all asymmetric settings with | X | ∈ {2 12 , 2 16 , 2 20 } and | Y | ∈ {5535, 11041}. We believe that our work not only supplements existing post‐quantum PSI frameworks but also opens the opportunity for broader applications of post‐quantum PSI.
Crystals-Kyber and Classic-McEliece are two prominent post-quantum key encapsulation mechanisms (KEMs) designed to address the challenges posed by quantum computing to classical cryptographic schemes. While the former has been standardized by the National Institute of Standards and Technology (NIST), the latter is well-known for its exceptional robustness and as one of the finalists of the fourth round of post-quantum cryptography standardization. Private set intersection (PSI) is a privacy-preserving technique that enables two parties, each possessing a dataset, to compute the intersection of their sets without revealing anything else. This can be achieved thanks to homomorphic encryption (HE), which allows computations on encrypted data. In this paper, firstly, we study Kyber and McEliece, apart from being KEMs, as post-quantum public key encryption (PKE), and examine their homomorphic properties. Secondly, we design two different two-party PSI protocols that utilize the homomorphic capabilities of Kyber and McEliece. Thirdly, a practical performance evaluation under NIST’s security levels 1, 3, and 5 is conducted, focusing on three key metrics: storage overhead, communication overhead, and computation cost. Insights indicate that the Kyber-based PSI Protocol, which utilizes the multiplicative homomorphic property, is secure but less efficient. In contrast, the McEliece-based PSI protocol, while efficient in practice, raises concerns regarding its security as a homomorphic encryption scheme.
Abstract We present a highly efficient post-quantum Randomized Oblivious Pseudorandom Function (OPRF) construction based on a novel TFHE key transformation technique. Unlike prior lattice-based OPRF schemes that rely on complex homomorphic PRF evaluation, our approach leverages the algebraic structure of TFHE to enable direct ciphertext transformation, resulting in significant performance improvements. Our protocol achieves strong security under the Learning With Errors (LWE) assumption and provides session unlinkability, making it well-suited for privacy-preserving applications. We demonstrate the practical efficiency of our construction with a Rust implementation, achieving substantial speedups over existing schemes. Furthermore, we show how our Randomized OPRF can be adapted for use in the OPAQUE password-authenticated key exchange protocol by employing a singularization technique to ensure deterministic outputs when required. This work highlights a new, practical path for post-quantum OPRFs with strong privacy and efficiency guarantees.
Verifiable Random Functions (VRFs) and Oblivious Pseudorandom Functions (OPRFs) are essential cryptographic primitives in privacy-preserving applications such as anonymous authentication, private set intersection (PSI), and decentralized identity. Existing constructions, however, rely on number-theoretic assumptions that are vulnerable to quantum attacks. This PhD research project focuses on constructing efficient and practical VRFs and OPRFs from lattice-based assumptions to ensure post-quantum security. A key obstacle in these constructions is the overhead of zero-knowledge proofs (ZKPs), particularly range proofs, which are costly in terms of size and prover complexity. To address this, we investigate probabilistic techniques that relax exact correctness. In particular, we explore approximate range proofs and algebraic transformations, such as using automorphisms in polynomial rings to simulate inner product arguments via polynomial multiplication. These methods enable more efficient and scalable lattice-based constructions of VRFs, including group and context-bound variants, as well as OPRFs. The goal is to make these primitives practical for deployment in post-quantum privacy-preserving systems.
Private set intersection (PSI) is a cryptographic protocol that enables two parties to securely determine the intersection of their private datasets without revealing anything except the intersection. Most of the existing PSI protocols are based on traditional number theoretic problems, such as discrete logarithm problem and factorisation problem. Unfortunately, these protocols would be broken if efficient quantum computer emerges. The post-quantum PSI is an important alternative to traditional PSI protocols for its potential to resist future attacks of quantum computers. In this work, we present first post-quantum PSI protocol that achieves size-hiding property. Space-efficient probabilistic data structure Bloom filter along with lattice-based public key encryption are used as building blocks of our construction. It attains linear complexity and security in standard model under the decisional learning with errors (DLWE) assumption. Moreover, we extend our post-quantum PSI to its authorised variant APSI retaining all the properties.
Private set intersection (PSI) is a fundamental cryptographic task that allows two mutually distrusting parties, each holding a private set of elements, to jointly compute the intersection of their sets. It ensures a symmetric information structure where neither party gains any knowledge about the other’s elements beyond those in the shared intersection. Traditional PSI protocols are primarily designed for static settings, which limits their applicability and efficiency in dynamic scenarios where input sets continuously evolve. To address this challenge, the notion of updatable PSI (UPSI) was introduced, enabling repeated PSI computations over changing inputs while preserving the symmetric privacy guarantees between participants. Despite the numerous recent advancements in UPSI research, it still suffers from significant communication overhead. In this paper, we address this challenge by introducing LcUPSI (low-communication UPSI), a new updatable PSI protocol that achieves remarkably low communication overhead. We formally prove that LcUPSI is secure in the semi-honest model. Furthermore, we compare the LcUPSI protocol with the state-of-the-art UPSI protocol BMSTZ24 (ASIACRYPT). The results demonstrate that LcUPSI significantly reduces communication overhead, highlighting its advantages in low-bandwidth conditions.