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

arXiv:2210.08165

A Secure Multiparty Quantum Least Common Multiple Computation Protocol

Zixian Li, Wenjie Liu

Published Oct 15, 2022• 2 citations
arXivHTMLPDF

Abstract

In this paper, we present a secure multiparty computation (SMC) protocol for least common multiple (LCM) based on Shor's quantum period-finding algorithm (QPA). Our protocol is based on the following principle: the connection of multiple periodic functions is also a periodic function whose period is exactly the least common multiple of all small periods. Since QPA is a probabilistic algorithm, we also propose a one-vote-down vote protocol based on the existing secure multi-party quantum summation protocol, which is used to verify the results of the proposed LCM protocol. Security analysis shows that under the semi-honest model, the proposed protocol is secure with high probability, while the computational consumption remains at polynomial complexity. The protocol proposed in this paper solves the problem of efficient and secure multiparty computation of LCM, demonstrating quantum computation potential.

DOI
10.48550/arxiv.2210.08165

Related papers

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 multi-party private set union protocol based on least common multiple and Shor’s algorithm

Wenjie Liu, Qi Yang, Zixian Li

Private set union (PSU) allows several parties to obtain the union of their private sets without disclosing each party’s private information. Existing PSU protocols often have polynomial complexity for the complete set size or complicated process. In this paper, a quantum multi-party PSU protocol based on least common multiple (LCM) and Shor’s algorithm is proposed, which enables the union of multiple sets to be computed all at once. In order to increase the one-time success probability of the protocol, we first improved Shor’s period-finding algorithm, which is used in LCM computation and integer factoring. Each party’s private set is encoded into an integer obtained by multiplying several prime numbers, thus the PSU problem is transformed into an LCM problem. The LCM of these integers is computed by using the improved Shor’s period-finding algorithm, and then factored to derived the union set. We prove the correctness of the proposed protocol, and its unconditional security against semi-honest attacks. Complexity analysis shows that our protocol has logarithmic complexity for the complete set size.

International Journal of Quantum Information•Feb 9, 2023•5 citations

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

An efficient secure multiparty quantum computation protocol

Song Lin, Ning Wang, LIU Xiao-Fen

Secure multiparty computing is an important class of cryptographic primitives and is widely used in electronic voting, data mining, blockchain, cloud computing and other fields. In this paper, we propose an efficient secure multiparty quantum computation protocol based on quantum entanglement and the Euler theorem. In this protocol, all participants can safely compute multivariate polynomial functions with the help of a semitrusted third party. A performance analysis shows that the protocol is correct and can resist some common external and internal attacks. Additionally, the proposed protocol not only improves particle detection efficiency but also effectively reduces the communication complexity.

Zhongguo kexue. Wulixue Lixue Tianwenxue•Feb 15, 2023•8 citations

Quantum Secure Multiparty Summation Based on Quantum Walks

Justin Joseph, Syed Taqi Ali

We propose an efficient Quantum Secure Multiparty Summation protocol based on quantum walk states. It enables multiple participants to find the sum of all the data without revealing it to anyone else. With the help of quantum walks, we can achieve this with fewer quantum resources and minimal communication costs. The protocol also requires a semi-honest third party (TP) to facilitate the protocol. The semi-honest TP follows the protocol but attacks passively. Finally, we prove its correctness and security, making it a viable solution for quantum secure multiparty summation.

International Conference on Quantum Technologies, Communications, Computing, Hardware and Embedded Systems Security (iQ-CCHESS)•Sep 15, 2023•0 citations

An efficient simulation for quantum secure multiparty computation

Kartick Sutradhar, Hari Om

The quantum secure multiparty computation is one of the important properties of secure quantum communication. In this paper, we propose a quantum secure multiparty summation (QSMS) protocol based on (t, n) threshold approach, which can be used in many complex quantum operations. To make this protocol secure and realistic, we combine both the classical and quantum phenomena. The existing protocols have some security and efficiency issues because they use (n, n) threshold approach, where all the honest players need to perform the quantum multiparty summation protocol. We however use a (t, n) threshold approach, where only t honest players need to compute the quantum summation protocol. Compared to other protocols our proposed protocol is more cost-effective, realistic, and secure. We also simulate it using the IBM corporation's online quantum computer, or quantum experience.

Scientific Reports•Jan 26, 2021•36 citations
In this paper, we present a secure multiparty computation (SMC) protocol for least common multiple (LCM) based on Shor's quantum period-finding algorithm (QPA). Our protocol is based on the following principle: the connection of multiple periodic functions is also a periodic function whose period is exactly the least common multiple of all small periods. Since QPA is a probabilistic algorithm, we also propose a one-vote-down vote protocol based on the existing secure multi-party quantum summation protocol, which is used to verify the results of the proposed LCM protocol. Security analysis shows that under the semi-honest model, the proposed protocol is secure with high probability, while the computational consumption remains at polynomial complexity. The protocol proposed in this paper solves the problem of efficient and secure multiparty computation of LCM, demonstrating quantum computation potential.
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.
Private set union (PSU) allows several parties to obtain the union of their private sets without disclosing each party’s private information. Existing PSU protocols often have polynomial complexity for the complete set size or complicated process. In this paper, a quantum multi-party PSU protocol based on least common multiple (LCM) and Shor’s algorithm is proposed, which enables the union of multiple sets to be computed all at once. In order to increase the one-time success probability of the protocol, we first improved Shor’s period-finding algorithm, which is used in LCM computation and integer factoring. Each party’s private set is encoded into an integer obtained by multiplying several prime numbers, thus the PSU problem is transformed into an LCM problem. The LCM of these integers is computed by using the improved Shor’s period-finding algorithm, and then factored to derived the union set. We prove the correctness of the proposed protocol, and its unconditional security against semi-honest attacks. Complexity analysis shows that our protocol has logarithmic complexity for the complete set size.
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.
Secure multiparty computing is an important class of cryptographic primitives and is widely used in electronic voting, data mining, blockchain, cloud computing and other fields. In this paper, we propose an efficient secure multiparty quantum computation protocol based on quantum entanglement and the Euler theorem. In this protocol, all participants can safely compute multivariate polynomial functions with the help of a semitrusted third party. A performance analysis shows that the protocol is correct and can resist some common external and internal attacks. Additionally, the proposed protocol not only improves particle detection efficiency but also effectively reduces the communication complexity.
We propose an efficient Quantum Secure Multiparty Summation protocol based on quantum walk states. It enables multiple participants to find the sum of all the data without revealing it to anyone else. With the help of quantum walks, we can achieve this with fewer quantum resources and minimal communication costs. The protocol also requires a semi-honest third party (TP) to facilitate the protocol. The semi-honest TP follows the protocol but attacks passively. Finally, we prove its correctness and security, making it a viable solution for quantum secure multiparty summation.
The quantum secure multiparty computation is one of the important properties of secure quantum communication. In this paper, we propose a quantum secure multiparty summation (QSMS) protocol based on (t, n) threshold approach, which can be used in many complex quantum operations. To make this protocol secure and realistic, we combine both the classical and quantum phenomena. The existing protocols have some security and efficiency issues because they use (n, n) threshold approach, where all the honest players need to perform the quantum multiparty summation protocol. We however use a (t, n) threshold approach, where only t honest players need to compute the quantum summation protocol. Compared to other protocols our proposed protocol is more cost-effective, realistic, and secure. We also simulate it using the IBM corporation's online quantum computer, or quantum experience.