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.
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.
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.
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.
This note describes a key exchange method based on the ring-LWE (RLWE)
assumption. It builds upon several results, including Regev's
landmark quantum reduction from certain worst case lattice problems
(approx. GapSVP and SIVP) to random instances of the search variant of
a particular learning problem (LWE). It also builds on the follow on
work of Lyubashevsky, Peikert and Regev on the average case hardness
of the RLWE search variant for polynomially bounded numbers of RLWE
samples, along with novel applications of automorphism groups in
number fields for a RLWE search to decision reduction (thereby
demonstrating pseudorandomness of RLWE in these number fields).
Subsequently, these results were adopted for the construction of
Diffie-Hellman like key exchange methods by Peikert, and then by
Lindner and Peikert followed by Ding and then by Ding, Xie and Lin who
proposed efficient variants of such protocols. Subsequent work by
Peikert proposed another efficient variant, phrased as a key
encapsulation method, incorporating a low bandwidth reconciliation
technique allowing two parties to exactly agree on a uniformly
distributed secret value from noisy RLWE instances. This was followed
by a concrete instantiation with parameter sets by Bos, Costello,
Naehrig, Stebila, followed by another instantiation by Alkim, Ducas,
Poppelmann and Schwabe with the same ring polynomial but a smaller
modulus and a different reconciliation method. Unlike most other
public key cryptography based key exchange methods, it is believed
that RLWE based key exchange would remain secure in the event that an
adversary is able to build a quantum computer. This document is a
product of the Crypto Forum Research Group (CFRG).
Nowadays, the necessity of electronic information increases rapidly. As a consequence, often, that information needs to be shared among mutually distrustful parties. In this area, private set intersection (PSI) and its variants play an important role when the participants wish to do secret operations on their input sets. Unlike the most modern public key cryptosystems relying on number theoretic problems, lattice‐based cryptographic constructions provide security in the presence of a quantum computer. Consequently, developing PSI and its variants using lattice based cryptosystem becomes an interesting direction for research. This study presents the first size‐hiding post quantum PSI cardinality (PSI‐CA) protocol whose complexity is linear in the size of the sets of the participants. The authors use space‐efficient probabilistic data structure (Bloom filter) as its building block. Further, they extend the authors’ PSI‐CA to its authorised version, i.e. authorised PSI‐CA. Security for both of them is achieved in the standard model based on the hardness of the decisional learning with errors problem.
Ring Learning With Errors (RLWE)-based key exchange is one of the most efficient and secure primitive for post-quantum cryptography. One common approach to achieve key exchange over RLWE is error reconciliation. Recently, an efficient attack against reconciliation-based RLWE key exchange protocols with reused keys was proposed. This attack can recover a long-term private key if a key pair is reused. We also know that in the real world, key reuse is commonly adopted in applications like the Transport Layer Security (TLS) protocol to improve performance. Directly motivated by this attack, we construct a new randomized RLWE-based key exchange protocol against this attack. Our lightweight approach incorporates an additional ephemeral public error term into key exchange materials, so that this attack no longer works. With the same attack, we practically show that the signal value of our protocol is indistinguishable from uniform random, therefore, this attack no longer works. We explain how the attack fails, present 200-bit classic and 80-bit quantum secure parameter choice, efficient implementations, comparisons and discussion. Benchmark shows our protocol is truly efficient and even faster than related vulnerable protocols.