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

作     者：李子贤 刘文杰 LI Zi-Xian;LIU Wen-Jie

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

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

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2024年第47卷第6期

页      码：1393-1412页

摘      要：最小公倍数是解决很多数学问题的基础工具,在隐私保护的情况下如何对其进行多方协同计算具有一定的研究价值.部分经典安全多方计算协议虽然能够求解该问题,但计算复杂度为指数级.本文通过将最小公倍数问题转化为求多个周期函数的连接函数的周期,提出了一个基于量子周期查找算法的最小公倍数协议,将复杂度降为多项式级.在协议中,发起方对每个参与方发送一个粒子.每个参与方对粒子施加一个Oracle操作,其中Oracle函数的周期即各自的私有整数.然后,发起方通过运行量子周期查找算法来计算出连接函数的周期,即各自整数的最小公倍数.为了防御共谋和伪造攻击,采用星-环混合拓扑结构对粒子发送方进行诚实性检验.由于量子周期查找算法存在一定的失败概率,设计了一个量子匿名输出检验协议来检验最小公倍数结果的正确性.安全性分析表明了该协议在恶意模型下具有无条件安全性,且协议的计算复杂度和通信复杂度分别为O(n^(3)m^(2)log(nm))和O(n^(2)mlog(nm)),均为多项式级.此外,该协议具有较好的扩展性,可应用于安全多方最大公约数计算、有理数求和、最值计算等问题.

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

学科分类：08[工学] 0839[0839] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.11897/SP.J.1016.2024.01393

馆 藏 号：203127828...