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 Transactions on Circuits and Systems I Regular Papers

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

Runhua Shi, Yi-Fei Li

Published Mar 3, 2022• 43 citations
Publisher

Abstract

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.

DOI
10.1109/tcsi.2022.3152591

Related papers

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•24 citations

Quantum Protocol for Secure Multiparty Logical AND With Application to Multiparty Private Set Intersection Cardinality

Runhua Shi, Yi-Fei Li

Like addition, subtraction, multiplication and division, logical AND is a fundamental arithmetic operation in scientific computing. In this paper, we first consider and define a new privacy-preserving problem, i.e., Secure Multiparty Logical AND (SMLA), in which multiple participants can jointly compute the logical AND of their respective private bits. Furthermore, we present a novel quantum SMLA protocol by employing phase-matching quantum conference key agreement and perfect quantum encryption, and design the corresponding quantum circuits. The proposed quantum SMLA protocol can ensure information-theoretical security. What’s more, we design a private grouping strategy to reduce the communicational complexity and accordingly present an improved quantum SMLA protocol with the linear communicational rounds. In addition, we investigate its applications and design a feasible quantum Multiparty Private Set Intersection Cardinality (MPSI-CA) protocol based on the improved quantum SMLA protocol, in which multiple participants jointly compute the intersection cardinality without revealing their respective private sets. Finally, we verify the correctness and the feasibility of the proposed quantum protocols by circuit simulations in IBM Qiskit.

IEEE Transactions on Circuits and Systems I Regular Papers•Aug 29, 2022•21 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•22 citations

A Feasible Quantum Protocol for Private Set Intersection Cardinality

Runhua Shi, Mingwu Zhang

Private Set Intersection Cardinality (PSI-CA) is to compute privately the cardinality of the intersection of two sets, and there are many practical applications of PSI-CA, e.g., data mining and data analysis with the privacy protection. The current classical protocols for PSI-CA could not resist the attacks of quantum computers. In this paper, we present a novel quantum protocol for PSI-CA based on the basic laws of quantum mechanics, which can resist well-known quantum attacks. This protocol utilizes single photons as quantum resources and only needs to apply simple single-photon operators and measurements. Therefore, it is more feasible to implement this protocol, compared with the related quantum protocols, which require entangled states and other complicated operators.

IEEE Access•Jan 1, 2019•19 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 novel quantum private query protocol and its application in private set intersection

Zeping Deng, Hongwei Sun, Kejia Zhang +3 more

As an important topic in quantum secure multiparty computing, quantum privacy query (QPQ) can solve the problem of information query between users and database owners without compromising privacy. In the existing research, most of them focus on its functions, not its applications. In this paper, a new QPQ protocol based on two-particle states is proposed. In our protocol, we use two-particle states combined with the Ctrl or Shift operations to give the user a partial key sequence and the database cannot recognize the user's key sequence. Meanwhile, we conduct simulation experiments at the IBM quantum experience and show that it is feasible. We discuss its application in the private set intersection (PSI), which is derived from QPQ. According to our analysis, the QPQ protocol and PSI protocol are secure.

Scientific Reports•Oct 14, 2025•2 citations
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.
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.
Like addition, subtraction, multiplication and division, logical AND is a fundamental arithmetic operation in scientific computing. In this paper, we first consider and define a new privacy-preserving problem, i.e., Secure Multiparty Logical AND (SMLA), in which multiple participants can jointly compute the logical AND of their respective private bits. Furthermore, we present a novel quantum SMLA protocol by employing phase-matching quantum conference key agreement and perfect quantum encryption, and design the corresponding quantum circuits. The proposed quantum SMLA protocol can ensure information-theoretical security. What’s more, we design a private grouping strategy to reduce the communicational complexity and accordingly present an improved quantum SMLA protocol with the linear communicational rounds. In addition, we investigate its applications and design a feasible quantum Multiparty Private Set Intersection Cardinality (MPSI-CA) protocol based on the improved quantum SMLA protocol, in which multiple participants jointly compute the intersection cardinality without revealing their respective private sets. Finally, we verify the correctness and the feasibility of the proposed quantum protocols 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.
Private Set Intersection Cardinality (PSI-CA) is to compute privately the cardinality of the intersection of two sets, and there are many practical applications of PSI-CA, e.g., data mining and data analysis with the privacy protection. The current classical protocols for PSI-CA could not resist the attacks of quantum computers. In this paper, we present a novel quantum protocol for PSI-CA based on the basic laws of quantum mechanics, which can resist well-known quantum attacks. This protocol utilizes single photons as quantum resources and only needs to apply simple single-photon operators and measurements. Therefore, it is more feasible to implement this protocol, compared with the related quantum protocols, which require entangled states and other complicated operators.
As an important topic in quantum secure multiparty computing, quantum privacy query (QPQ) can solve the problem of information query between users and database owners without compromising privacy. In the existing research, most of them focus on its functions, not its applications. In this paper, a new QPQ protocol based on two-particle states is proposed. In our protocol, we use two-particle states combined with the Ctrl or Shift operations to give the user a partial key sequence and the database cannot recognize the user's key sequence. Meanwhile, we conduct simulation experiments at the IBM quantum experience and show that it is feasible. We discuss its application in the private set intersection (PSI), which is derived from QPQ. According to our analysis, the QPQ protocol and PSI protocol are secure.