清华浙大在量子计算破解RSA密码方面取得重要突破

在一项最新研究中，清华大学龙桂鲁、浙江大学王浩华等组成的团队创建了一种算法，仅用10个超导量子比特就实现了48位因式分解。

01 相关人物简介

龙桂鲁教授，1978年在高中一年级跳级考入山东大学，1982提前半年毕业，获得山东大学理学学士，并考入清华大学读研，分别于1985、1987年获得清华大学理学硕士和博士学位。1987年开始在清华大学任教至今。1989-1993年在英国萨塞克斯大学从事博士后研究。研究方向包括量子信息、原子分子光物理、高能物理与原子核物理。1997年获得国家自然科学奖三等奖，1999年当选英国物理学会会士（IOP Fellow），2003年获“国家杰出青年基金”资助，2007年获得汤森路透卓越研究奖，2008年获得中国物理学会饶毓泰物理奖，2011年当选美国物理学会会士（APS Fellow），同年获得教育部自然科学奖一等奖，2013年获得国家自然科学奖二等奖，2018年获得中国电子学会自然科学奖一等奖、IBM全球杰出学者奖，2020年获得中国通信学会科学技术奖一等奖。

王浩华教授，1999年毕业于南开大学物理系，获得学士学位。2006年在美国宾州州立大学物理系获理学博士学位，2007年至2010年在美国加州大学圣塔芭芭拉分校物理系从事博士后研究工作。现为浙江大学物理学系教授，博士生导师，研究方向为超导量子计算和量子模拟实验研究。在国际上首次制备了十和二十超导比特纠缠态，在浙江大学建立了超导量子芯片的全流程制备工艺，研发天目1号、莫干1号两款芯片，基于超导多比特集成器件构建了量子模拟机用于研究多体物理中的重要科学问题。先后获得中组部青年拔尖人才计划和基金委优秀青年、杰出青年科学基金资助，承担基金委重点项目和科技部重点基础研究发展计划（973）课题，共发表SCI论文70余篇，包括Nature、Science、Nature Physics、Nature Communications、Science Advances 和 Physical Review Letters 40余篇，总引近七千次。

王浩华教授（右三）和他的团队

02 全新整数分解算法，刷新历史记录

大多数专家认为这项任务将需要数百万个量子比特。

该团队的最新实验表明，依靠整数因子化的公钥密码技术可能很快就会受到当今原始的NISQ（含噪声中等规模）量子计算机的攻击。

据研究人员称，该算法是基于经典的Schnorr算法——使用格约化来分解整数，同时依靠量子近似优化算法（QAOA）来优化Schnorr算法中最耗时的部分，以提高因式分解的速度。

研究人员表示，“使用这种算法，我们已经成功地对整数1961（11位）、48567227（26位）和261980999226229（48位）进行了因式分解，在超导量子处理器中分别使用了3、5和10个量子比特。对于48位的整数，261980999226229，我们也刷新了真正的量子设备中用一般方法算出的最大整数。”

使用这种算法的近期量子计算机可能能够处理更大的整数分解问题，可能打破广泛用于保护计算机数据和系统的RSA-2048加密方案。

次线性资源量子整数分解（SQIF）算法的工作流。

实验装置和SQIF算法的QAOA电路

RSA数字的资源估计。提到的主要量子资源是量子比特的数量、QAOA的量子电路深度与三种典型拓扑结构的单次迭代。

03 即将在NISQ设备实现，算法加速有待确认

研究人员表示，“通过估算RSA-2048因式分解所需的量子资源来进行。我们发现，即使在最简单的一维链系统中，也需要一个具有372个物理量子比特和数千深度的量子电路来挑战RSA-2048。这样规模的量子资源最有可能在不久的将来在NISQ设备上实现。”

该团队在论文中指出，由于QAOA的收敛性不明确，该算法的量子加速还不清楚：“然而，通过QAOA优化Babai算法中的‘size-reduce’程序的想法可以作为一大批广泛使用的格约化算法中的子程序使用。进一步说，它可以帮助分析基于格的抗量子密码问题。”

该团队包括来自数学工程与先进计算国家重点实验室、清华大学、浙江大学、北京量子信息科学研究院、信息工程大学和量子信息前沿科学中心的科学家。

论文链接：

https://arxiv.org/pdf/2212.12372.pdf

【安全圈】新 Linux 恶意软件：利用多款 WordPress 插件和主题漏洞注入恶意脚本

【安全圈】“Eternity”组织：持续活跃的商业武器库

【安全圈】不法黑客滥用Google Ads分发恶意软件

安全圈

←扫码关注我们

网罗圈内热点 专注网络安全

实时资讯一手掌握！

好看你就分享 有用就点个赞

支持「安全圈」就点个三连吧！