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 Access

Efficient Quantum Protocol for Private Set Intersection Cardinality

Runhua Shi

Published Jan 1, 2018• 24 citations
Publisher

Abstract

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.

DOI
10.1109/access.2018.2872741

Related papers

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•43 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

Quantum Secure Multi-party Private Set Intersection Cardinality

Bai Liu, Mingwu Zhang, Runhua Shi

Abstract As we know that data sharing, a critical element in social networks, has the benefits of exploring important information, while also has the disadvantage of information leakage. Therefore, without the reliable third party arbitration agency, it is impossible to share information privately by distrustful multi-party. In this paper, we proposed a protocol called Quantum Secure Multi-party Private Set Intersection Cardinality (QSMS-IC), which has the capability of resisting quantum attacks. QSMS-IC, the extension of two-parity private set intersection cardinality which was proposed in Information Sciences(2016,147-158), utilizes quantum transformation, quantum measurements and quantum parallelism to solve multi-party private set intersection cardinality problems. Compared with two-party PSI-CA protocols, our proposed protocol can solve the data sharing among multi-party without the reliable third party arbitration agency. It also can be used in numerous applications and more suitable to the actual cases. For instance, large-scale social networks and privacy-preserving data ming.

International Journal of Theoretical Physics•May 7, 2020•20 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

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

Sumit Kumar Debnath, Pantelimon Stănică, Tanmay Choudhury +1 more

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.

IET Information Security•Jun 11, 2020•8 citations

Three-party quantum private computation of cardinalities of set intersection and union based on GHZ states

Cai Zhang, Yinxiang Long, Zhiwei Sun +2 more

Private Set Intersection Cardinality (PSI-CA) and Private Set Union Cardinality (PSU-CA) are two cryptographic primitives whereby two or more parties are able to obtain the cardinalities of the intersection and the union of their respective private sets, and the privacy of their sets is preserved. In this paper, we propose a three-party protocol to finish these tasks by using quantum resources, where every two, as well as three, parties can obtain the cardinalities of the intersection and the union of their private sets with the help of a semi-honest third party (TP). In our protocol, GHZ states play a role in encoding private information that will be used by TP to compute the cardinalities. We show that the presented protocol is secure against well-known quantum attacks. In addition, we analyze the influence of six typical kinds of Markovian noise on our protocol.

Scientific Reports•Dec 17, 2020•20 citations
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 (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.
Abstract As we know that data sharing, a critical element in social networks, has the benefits of exploring important information, while also has the disadvantage of information leakage. Therefore, without the reliable third party arbitration agency, it is impossible to share information privately by distrustful multi-party. In this paper, we proposed a protocol called Quantum Secure Multi-party Private Set Intersection Cardinality (QSMS-IC), which has the capability of resisting quantum attacks. QSMS-IC, the extension of two-parity private set intersection cardinality which was proposed in Information Sciences(2016,147-158), utilizes quantum transformation, quantum measurements and quantum parallelism to solve multi-party private set intersection cardinality problems. Compared with two-party PSI-CA protocols, our proposed protocol can solve the data sharing among multi-party without the reliable third party arbitration agency. It also can be used in numerous applications and more suitable to the actual cases. For instance, large-scale social networks and privacy-preserving data ming.
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.
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 Cardinality (PSI-CA) and Private Set Union Cardinality (PSU-CA) are two cryptographic primitives whereby two or more parties are able to obtain the cardinalities of the intersection and the union of their respective private sets, and the privacy of their sets is preserved. In this paper, we propose a three-party protocol to finish these tasks by using quantum resources, where every two, as well as three, parties can obtain the cardinalities of the intersection and the union of their private sets with the help of a semi-honest third party (TP). In our protocol, GHZ states play a role in encoding private information that will be used by TP to compute the cardinalities. We show that the presented protocol is secure against well-known quantum attacks. In addition, we analyze the influence of six typical kinds of Markovian noise on our protocol.