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

IET Information Security

Post‐quantum protocol for computing set intersection cardinality with linear complexity

Sumit Kumar Debnath, Pantelimon Stănică, Tanmay Choudhury, Nibedita Kundu

Published Jun 11, 2020• 11 citations
Publisher

Abstract

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.

DOI
10.1049/iet-ifs.2019.0315

Related papers

Efficient post-quantum private set-intersection protocol

Nibedita Kundu, Tanmay Choudhury, Sumit Kumar Debnath

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

Efficient Quantum Protocol for Private Set Intersection Cardinality

Runhua Shi

Recently, we proposed a quantum solution to the problem of private set intersection cardinality (PSI-CA) (Information Sciences 370–371 (2016) 147–158). Compared to classical solutions, the proposed quantum PSI-CA protocol achieves an exponential reduction in communication complexity, since it only needs$O(1)$communication cost. However, this protocol requires two additional assumptions about the cardinalities of the sets, which may limit its wider applications. In this paper, we successfully discard these assumptions and present a stronger quantum PSI-CA protocol without any limitation. The new protocol ensures the parties’ private security, i.e., unconditionally secure server privacy and statistically secure client privacy, and it achieves the constant computation and communication complexities, which are independent of the size of the sets. Therefore, it is more suitable for practical applications with big data sets.

IEEE Access•Jan 1, 2018•25 citations

Quantum Private Set Intersection Cardinality Protocol With Application to Privacy-Preserving Condition Query

Runhua Shi, Yi-Fei Li

Private Set Intersection Cardinality (PSI-CA) is one of the most concerned issues with the protection of privacy, in which two parties jointly compute the intersection cardinality without revealing their respective private sets. There are important applications of PSI-CA in real society, e.g., strongly privacy-preserving data statistics in contact tracing for health authorities to fight the outbreaks of highly contagious diseases. In this paper, we present a novel quantum PSI-CA protocol, in which we adopt oblivious quantum key distribution, secure quantum summation and quantum counting algorithm. The proposed PSI-CA protocol not only ensures the approximatively perfect security but also achieves the linear communication complexity, i.e.,${O(N)}$. Furthermore, we define a new privacy protection problem, i.e., Privacy-preserving Condition Query (PCQ), and provide an efficient solution to the PCQ problem based on the proposed quantum PSI-CA protocol. Finally, we verify the correctness and the feasibility of the proposed quantum PSI-CA protocol by circuit simulations in IBM Qiskit.

IEEE Transactions on Circuits and Systems I Regular Papers•Mar 3, 2022•46 citations

Quantum private set intersection cardinality based on bloom filter

Bai Liu, Ou Ruan, Runhua Shi +1 more

Private Set Intersection Cardinality that enable Multi-party to privately compute the cardinality of the set intersection without disclosing their own information. It is equivalent to a secure, distributed database query and has many practical applications in privacy preserving and data sharing. In this paper, we propose a novel quantum private set intersection cardinality based on Bloom filter, which can resist the quantum attack. It is a completely novel constructive protocol for computing the intersection cardinality by using Bloom filter. The protocol uses single photons, so it only need to do some simple single-photon operations and tests. Thus it is more likely to realize through the present technologies. The validity of the protocol is verified by comparing with other protocols. The protocol implements privacy protection without increasing the computational complexity and communication complexity, which are independent with data scale. Therefore, the protocol has a good prospects in dealing with big data, privacy-protection and information-sharing, such as the patient contact for COVID-19.

Scientific Reports•Aug 30, 2021•23 citations

Break Two PSI-CA Protocols in Polynomial Time

Yang Tan, Bo Lv

Private Set Intersection Cardinality(PSI-CA) is an important type of secure two-party computation. It has wide applications in federated machine learning. It enables two parties, each holding a private set, to jointly compute the cardinality of their intersection without revealing any other private information about their respective sets.

International Conference on Machine Learning and Computing (ICMLC)•Feb 2, 2024•1 citation

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
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.
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.
Recently, we proposed a quantum solution to the problem of private set intersection cardinality (PSI-CA) (Information Sciences 370–371 (2016) 147–158). Compared to classical solutions, the proposed quantum PSI-CA protocol achieves an exponential reduction in communication complexity, since it only needsO(1)O(1)O(1)communication cost. However, this protocol requires two additional assumptions about the cardinalities of the sets, which may limit its wider applications. In this paper, we successfully discard these assumptions and present a stronger quantum PSI-CA protocol without any limitation. The new protocol ensures the parties’ private security, i.e., unconditionally secure server privacy and statistically secure client privacy, and it achieves the constant computation and communication complexities, which are independent of the size of the sets. Therefore, it is more suitable for practical applications with big data sets.
Private Set Intersection Cardinality (PSI-CA) is one of the most concerned issues with the protection of privacy, in which two parties jointly compute the intersection cardinality without revealing their respective private sets. There are important applications of PSI-CA in real society, e.g., strongly privacy-preserving data statistics in contact tracing for health authorities to fight the outbreaks of highly contagious diseases. In this paper, we present a novel quantum PSI-CA protocol, in which we adopt oblivious quantum key distribution, secure quantum summation and quantum counting algorithm. The proposed PSI-CA protocol not only ensures the approximatively perfect security but also achieves the linear communication complexity, i.e.,O(N){O(N)}O(N). Furthermore, we define a new privacy protection problem, i.e., Privacy-preserving Condition Query (PCQ), and provide an efficient solution to the PCQ problem based on the proposed quantum PSI-CA protocol. Finally, we verify the correctness and the feasibility of the proposed quantum PSI-CA protocol by circuit simulations in IBM Qiskit.
Private Set Intersection Cardinality that enable Multi-party to privately compute the cardinality of the set intersection without disclosing their own information. It is equivalent to a secure, distributed database query and has many practical applications in privacy preserving and data sharing. In this paper, we propose a novel quantum private set intersection cardinality based on Bloom filter, which can resist the quantum attack. It is a completely novel constructive protocol for computing the intersection cardinality by using Bloom filter. The protocol uses single photons, so it only need to do some simple single-photon operations and tests. Thus it is more likely to realize through the present technologies. The validity of the protocol is verified by comparing with other protocols. The protocol implements privacy protection without increasing the computational complexity and communication complexity, which are independent with data scale. Therefore, the protocol has a good prospects in dealing with big data, privacy-protection and information-sharing, such as the patient contact for COVID-19.
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.