求解最小公倍数问题的量子安全多方计算协议  

Quantum Secure Multi-Party Computation Protocols for Solving Least Common Multiple Problem

作　　者：李子贤 刘文杰[1,2,3] LI Zi-Xian;LIU Wen-Jie(School of Software,Nanjing University of Information Science and Technology,Nanjing 210044;Jiangsu Collaborative Innovation Center of Atmospheric Environment and Equipment Technology,Nanjing 210044;Engineering Research Center of Advanced Computing and Intelligent Seroices,Nanjing 210044)

机构地区：[1]南京信息工程大学软件学院,南京210044 [2]江苏省大气环境与装备技术协同创新中心,南京210044 [3]江苏省先进计算与智能服务工程研究中心,南京210044

出　　处：《计算机学报》2024年第6期1393-1412,共20页Chinese Journal of Computers

基　　金：国家自然科学基金(62071240);科技创新2030-“量子通信与量子计算机”重大项目(2021ZD0302901);江苏省研究生科研创新计划项目(KYCX23_1370);江苏省自然科学基金(BK20231142)资助.

摘　　要：最小公倍数是解决很多数学问题的基础工具,在隐私保护的情况下如何对其进行多方协同计算具有一定的研究价值.部分经典安全多方计算协议虽然能够求解该问题,但计算复杂度为指数级.本文通过将最小公倍数问题转化为求多个周期函数的连接函数的周期,提出了一个基于量子周期查找算法的最小公倍数协议,将复杂度降为多项式级.在协议中,发起方对每个参与方发送一个粒子.每个参与方对粒子施加一个Oracle操作,其中Oracle函数的周期即各自的私有整数.然后,发起方通过运行量子周期查找算法来计算出连接函数的周期,即各自整数的最小公倍数.为了防御共谋和伪造攻击,采用星-环混合拓扑结构对粒子发送方进行诚实性检验.由于量子周期查找算法存在一定的失败概率,设计了一个量子匿名输出检验协议来检验最小公倍数结果的正确性.安全性分析表明了该协议在恶意模型下具有无条件安全性,且协议的计算复杂度和通信复杂度分别为O(n^(3)m^(2)log(nm))和O(n^(2)mlog(nm)),均为多项式级.此外,该协议具有较好的扩展性,可应用于安全多方最大公约数计算、有理数求和、最值计算等问题.Least common multiple(LCM)is a basic tool to solve many mathematical problems.It is worth to research how to calculate the LCM of multi parties collaboratively with privacy protection.Some classical secure multi-party computation protocols can solve this problem,but the computational complexity is exponential.In this paper,by transforming the LCM problem into finding the period of the connection of multiple periodic functions,an LCM protocol based on the quantum period-finding algorithm(QPA)is proposed,which reduces the complexity to polynomial level.In the protocol,the initiator sends a quantum register to each other participant.Each participant applies an Oracle operator on the register,where the Oracle function's period is the party's own private integer.Finally,the initiator runs QPA to obtain the period of the connection function,i.e.,the LCM of all private integers.In order to defend collusion and forgery attacks,we use a star-ring hybrid topology structure to test the honesty of the register sender.Since QPA has a certain failure probability,we design a quantum anonymous output validation protocol to validate the correctness of the LCM results.Security analysis shows that the proposed protocol is unconditionally secure under malicious model.Its computational complexity and communication complexity are O(n^(3)m^(2)log(nm))and O(n^(2)mlog(nm)),respectively,which are polynomial.In addition,the proposed protocol has good scalability,and can be applied to implement secure multi-party greatest common divisor computation,fraction summation,maximum(minimum)computation,etc.

关 键 词：量子计算 量子信息 安全多方计算 最小公倍数 量子周期查找算法 匿名输出检验 隐私计算 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]