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

EPJ Quantum Technology

Efficient quantum secure multi-party greatest common divisor protocol and its applications in private set operations

Zixian Li, Wenjie Liu, Bing-Mei Su

Published Sep 9, 2024• 6 citations
Publisher

Abstract

Private set intersection (PSI) has important application value, however, current quantum PSI protocols are either unsuitable for multi-party scenarios or inefficient. Recently, Imran (arXiv: 2303.17196v3 , 2023) proposed two quantum secure multi-party greatest common divisor (GCD) protocols that can be used for PSI, but with the downside of information leakage and resource consumption. In this paper, we propose a novel quantum secure multi-party GCD protocol that has higher security and lower complexity. To hide privacy, each party randomly selects a coefficient within a range determined by his input integer, and with the assistance of a semi-honest third party TP, all parties secretly calculate the linear combination of their inputs under these coefficients. Once enough linear combinations are collected, TP calculates the GCD of these combinations, which is equal to the GCD of all input integers. To verify the honesty of participants, a quantum zero-knowledge proof sub-protocol is designed. Analysis shows that our GCD protocol is correct and has security against malicious attacks. Moreover, its complexity is polynomial level and lower than Imran’s. Furthermore, we demonstrate the scalability of our GCD protocol in private set operations, such as private set intersection, private set intersection cardinality, private multi-set intersection, etc.

DOI
10.1140/epjqt/s40507-024-00268-4

Related papers

A multi-party quantum private set intersection based on greatest common divisor

Muhammad Imran

Private set intersection (PSI) is a cryptographic primitive that allows two or more parties to learn the intersection of their input sets and nothing else. In this paper, we introduce a new secure multi-party quantum computation for the greatest common divisor (GCD) and a PSI protocol based on it. The protocol extends the recent least common multiple (LCM)-based quantum private set union protocol by Liu et al. Performance analysis verifies the correctness and demonstrates the entire security of the suggested protocols in the semi-honest model. Additionally, it has been demonstrated that the complexity is efficient in terms of the input set size.

International Journal of Quantum Information•Dec 19, 2024•0 citations

Secure multiparty quantum computations for greatest common divisor and private set intersection

Muhammad Ali Imran

We present a secure multiparty quantum computation (MPQC) for computing greatest common divisor (GCD) based on quantum multiparty private set union (PSU) by Liu, Yang, and Li. As the first step, we improve the security of the MPQC protocol for computing least common multiple (LCM) by Liu and Li by constructing an efficient exact quantum period-finding algorithm (EQPA) as a subroutine instead of the standard (probabilistic) Shor's quantum period-finding algorithm (QPA). The use of EQPA instead of the standard QPA guarantees the correctness of the protocol without repetitions. The improvement of LCM protocol also improves the private set union protocol which is based on computing LCM. Finally, using the same idea of the PSU protocol, we construct a quantum multiparty private set intersection (PSI) by transforming the PSI problem into the problem of computing GCD. Performance analysis shows that the correctness and the unconditional security in the semihonest model are guaranteed directly from the correctness and the security of the subroutine protocols (LCM and PSU protocols). Moreover, we show that the complexity of the proposed protocols is polynomial in the size of the secret inputs and the number of parties.

arXiv:2303.17196•Mar 30, 2023•2 citations

Quantum private set intersection based on single qubits

Cai Zhang, Zhuoxuan Zhan, Zhiwei Sun

Abstract Private Set Intersection (PSI) is a crucial Secure Multi-Party Computation (SMPC) primitive which enables participants to securely obtain the intersection of their private sets without revealing their individual set information. The advent of quantum computing threatens classical PSI protocols, driving the development of Quantum PSI (QPSI) alternatives. We propose a two-party QPSI protocol based on a semi-honest third party. This protocol achieves set intersection using only single-qubit unitary operations and single-qubit states. Security analysis shows that our protocol can resist common attacks. Validation experiments conducted on the IBM Qiskit simulator confirm the protocol's correctness and feasibility. Furthermore, we compare the proposed protocol with existing QPSI protocols in terms of quantum states, unitary operations, measurements, and fairness, demonstrating gains in quantum resource efficiency, fairness, and practical feasibility.

EPJ Quantum Technology•Oct 20, 2026•0 citations

Authenticated Multi-Party Quantum Private Set Intersection with Single Particles

Gongde Guo, Li Zheng, Kai Yu +1 more

As an important branch of secure multi-party computation, privacy set intersection enables multiple parties to input their private sets and jointly compute the intersection of these sets without revealing any information other than the intersection itself. With the increasing demand for privacy protection of user data, privacy set intersection has been widely used in privacy computing and other fields. In this paper, we utilize the properties of mutually unbiased bases to propose a multi-party quantum private set intersection protocol that incorporates identity authentication mechanisms. A semi-honest third party (TP) is introduced to facilitate the secure execution of this task among the multiple participating parties. The TP establishes a shared master key with each party, which serves as the basis for authenticating the identity of each participant throughout the protocol. Single-particle quantum states, prepared by the TP, act as the information carriers and are sequentially transmitted among the participating parties. Each party performs a local unitary operation on the circulating particle, thereby encoding their private data within the quantum state. At the end of the protocol, the TP announces his measurement result, by which all participants can concurrently ascertain the intersection of their private data sets. Notably, the proposed protocol eliminates the need for long-term storage of single-particle quantum states, thereby rendering it feasible with existing quantum technological capabilities. Furthermore, a comprehensive security analysis demonstrates that the protocol effectively resists some common external and internal attacks, thereby ensuring its theoretical security.

Mathematics•Jun 18, 2025•4 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

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
Private set intersection (PSI) has important application value, however, current quantum PSI protocols are either unsuitable for multi-party scenarios or inefficient. Recently, Imran (arXiv: 2303.17196v3 , 2023) proposed two quantum secure multi-party greatest common divisor (GCD) protocols that can be used for PSI, but with the downside of information leakage and resource consumption. In this paper, we propose a novel quantum secure multi-party GCD protocol that has higher security and lower complexity. To hide privacy, each party randomly selects a coefficient within a range determined by his input integer, and with the assistance of a semi-honest third party TP, all parties secretly calculate the linear combination of their inputs under these coefficients. Once enough linear combinations are collected, TP calculates the GCD of these combinations, which is equal to the GCD of all input integers. To verify the honesty of participants, a quantum zero-knowledge proof sub-protocol is designed. Analysis shows that our GCD protocol is correct and has security against malicious attacks. Moreover, its complexity is polynomial level and lower than Imran’s. Furthermore, we demonstrate the scalability of our GCD protocol in private set operations, such as private set intersection, private set intersection cardinality, private multi-set intersection, etc.
Private set intersection (PSI) is a cryptographic primitive that allows two or more parties to learn the intersection of their input sets and nothing else. In this paper, we introduce a new secure multi-party quantum computation for the greatest common divisor (GCD) and a PSI protocol based on it. The protocol extends the recent least common multiple (LCM)-based quantum private set union protocol by Liu et al. Performance analysis verifies the correctness and demonstrates the entire security of the suggested protocols in the semi-honest model. Additionally, it has been demonstrated that the complexity is efficient in terms of the input set size.
We present a secure multiparty quantum computation (MPQC) for computing greatest common divisor (GCD) based on quantum multiparty private set union (PSU) by Liu, Yang, and Li. As the first step, we improve the security of the MPQC protocol for computing least common multiple (LCM) by Liu and Li by constructing an efficient exact quantum period-finding algorithm (EQPA) as a subroutine instead of the standard (probabilistic) Shor's quantum period-finding algorithm (QPA). The use of EQPA instead of the standard QPA guarantees the correctness of the protocol without repetitions. The improvement of LCM protocol also improves the private set union protocol which is based on computing LCM. Finally, using the same idea of the PSU protocol, we construct a quantum multiparty private set intersection (PSI) by transforming the PSI problem into the problem of computing GCD. Performance analysis shows that the correctness and the unconditional security in the semihonest model are guaranteed directly from the correctness and the security of the subroutine protocols (LCM and PSU protocols). Moreover, we show that the complexity of the proposed protocols is polynomial in the size of the secret inputs and the number of parties.
Abstract Private Set Intersection (PSI) is a crucial Secure Multi-Party Computation (SMPC) primitive which enables participants to securely obtain the intersection of their private sets without revealing their individual set information. The advent of quantum computing threatens classical PSI protocols, driving the development of Quantum PSI (QPSI) alternatives. We propose a two-party QPSI protocol based on a semi-honest third party. This protocol achieves set intersection using only single-qubit unitary operations and single-qubit states. Security analysis shows that our protocol can resist common attacks. Validation experiments conducted on the IBM Qiskit simulator confirm the protocol's correctness and feasibility. Furthermore, we compare the proposed protocol with existing QPSI protocols in terms of quantum states, unitary operations, measurements, and fairness, demonstrating gains in quantum resource efficiency, fairness, and practical feasibility.
As an important branch of secure multi-party computation, privacy set intersection enables multiple parties to input their private sets and jointly compute the intersection of these sets without revealing any information other than the intersection itself. With the increasing demand for privacy protection of user data, privacy set intersection has been widely used in privacy computing and other fields. In this paper, we utilize the properties of mutually unbiased bases to propose a multi-party quantum private set intersection protocol that incorporates identity authentication mechanisms. A semi-honest third party (TP) is introduced to facilitate the secure execution of this task among the multiple participating parties. The TP establishes a shared master key with each party, which serves as the basis for authenticating the identity of each participant throughout the protocol. Single-particle quantum states, prepared by the TP, act as the information carriers and are sequentially transmitted among the participating parties. Each party performs a local unitary operation on the circulating particle, thereby encoding their private data within the quantum state. At the end of the protocol, the TP announces his measurement result, by which all participants can concurrently ascertain the intersection of their private data sets. Notably, the proposed protocol eliminates the need for long-term storage of single-particle quantum states, thereby rendering it feasible with existing quantum technological capabilities. Furthermore, a comprehensive security analysis demonstrates that the protocol effectively resists some common external and internal attacks, thereby ensuring its theoretical security.
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.
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.