https://doi.org/10.1140/epjqt/s40507-024-00268-4
Research
Efficient quantum secure multi-party greatest common divisor protocol and its applications in private set operations
1
School of Software, Nanjing University of Information Science and Technology, No. 219 Ningliu Road, 210044, Nanjing, Jiangsu, China
2
Jiangsu Collaborative Innovation Center of Atmospheric Environment and Equipment Technology (CICAEET), Nanjing University of Information Science and Technology, No. 219 Ningliu Road, 210044, Nanjing, Jiangsu, China
3
Jiangsu Province Engineering Research Center of Advanced Computing and Intelligent Services, Nanjing University of Information Science and Technology, No. 219 Ningliu Road, 210044, Nanjing, Jiangsu, China
4
School of Computer Science, Nanjing University of Information Science and Technology, No. 219 Ningliu Road, 210044, Nanjing, Jiangsu, China
Received:
22
September
2023
Accepted:
28
August
2024
Published online:
9
September
2024
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.
Key words: Quantum computation / Secure multi-party computation / Private set intersection / Private set intersection cardinality / Private multi-set intersection / Greatest common divisor
© The Author(s) 2024
Open Access This article is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License, which permits any non-commercial use, sharing, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if you modified the licensed material. You do not have permission under this licence to share adapted material derived from this article or parts of it. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by-nc-nd/4.0/.
