我们离网络隐私被攻克还有多远？

原文作者：Davide Castelvecchi

研究人员表示，虽然一种新算法可能还无法快速破解当前的加密密钥，但这不是我们自满的理由。

一个中国团队揭示了一项新技术，该技术——理论上——可以用一台很简单的量子计算机破解用来保护数字隐私的最常见技术。

研究团队称，这项技术成功完成了小规模演示，但其他专家怀疑这个程序扩展后能否在该任务上打败普通计算机。他们提醒道，这篇上个月发布在arXiv预印本服务器上的论文[1]再次提醒我们，网络隐私有多么不堪一击。

位于纽约IBM托马斯·J·沃森研究中心的一台量子计算机。来源：Connie Zhou for IBM

已知量子计算机会对当前的加密系统构成潜在威胁，但量子计算机的发展仍处于起步阶段。研究人员普遍认为，量子计算机破解密钥的速度超过普通计算机还要等很多年。这里的密钥是指用来保护数据的加密算法中的一串字符。

研究人员在1990年代就意识到，量子计算机可以利用物理学的一些奇异特性执行“经典”计算机无法完成的任务。如今就职于美国麻省理工学院的数学家Peter Shor在1994年证明[2]了如何利用量子叠加态（描述原子大小对象同时处于多种状态的能力）和量子干涉（类似于池塘里水波的相互叠加或抵消）的现象，将整数分解成素数——素数是无法进一步分解成没有余数的整数。

对于当前保护网络隐私和安全的常见加密技术以及一种基于大素数的加密系统来说，Shor的算法能让量子计算机破解这些系统的速度远超经典计算机，后一种基于大素数的加密系统名为Rivest–Shamir–Adleman，以三位发明者的首字母命名，简称RSA。不过，Shor的技术需要一台比现有原型机大很多倍的量子计算机。量子计算机的大小取决于量子比特（qubit）的数量。研究人员表示，破解RSA可能需要100万或以上的量子比特。当前最大的量子计算机是IBM去年11月宣布的Osprey芯片，该芯片有433个量子比特。

新方法

北京量子信息科学研究院的魏世杰与合作者尝试用另一种方法破解RSA，这种方法没有用Shor算法，而是用了Schnorr算法。Claus Schnorr是德国法兰克福大学的数学家，他也在1990年代设计出了一种分解整数的方法。Schnorr算法最初是为经典计算机设计的，但魏世杰团队使用量子近似优化算法（QAOA）在量子计算机上运行了其中部分流程。

在这篇尚未经过同行评审的论文中，作者称他们的算法只要372个量子比特就有望破解很强的RSA密钥——这类数字有600位以上的十进制数。在代表全体作者写给《自然》的一封邮件中，清华大学物理学家龙桂鲁提醒道，光靠增加量子比特是不够的，当前的量子计算机很容易出错，无法准确进行这么大的计算。“一味地增加量子比特数目，却不降低错误率并无帮助。”

中国科学技术大学研制量子计算机的物理学家陆朝阳未参与这项研究，他说，在这么小的计算机上运行QAOA算法需要这372个量子比特在99.9999%的时间里都能无错误工作。而当前最先进的量子比特只能勉强达到99.9%的准确率。

该团队在一台10量子比特的量子计算机上演示了该技术，他们分解了一个较易操作的15位数字——261,980,999,226,229。（这个数字可以分解成两个素数，15,538,213×16,860,433。）研究团队表示，这是目前在量子计算机辅助下分解过的最大数字，但仍然比现代网页浏览器使用的加密密钥要小很多。

研究争议

问题在于，没人知道QAOA是否能让大数分解的速度比在笔记本电脑上单独运行Schnorr的经典算法更快一些。作者写道，“需要指出的是，现在对该算法的量子加速还不清楚。”换句话说，虽然Shor算法能确保在有足够大的量子计算机的情况下快速破解加密，但这种基于优化的技术也可以在小很多的机器上运行，只是完成任务的时间可能会遥遥无期。

滑铁卢大学数学家Michele Mosca也指出，QAOA不是第一个已知能用少数量子比特分解整数的量子算法。他与合作者在2017年描述过一个这种算法[3]。因此研究人员很清楚，没有什么根本原因非得用很大的量子计算机才能分解数字。

其他研究人员也指出，虽然这篇最新论文可能是正确的，但它对速度的警告只出现在了论文末尾。得克萨斯大学奥斯汀分校的量子计算理论学家Scott Aaronson在他的博客中写道，“总而言之，这是我在过去25年里看到的最误导人的量子计算论文。”

龙桂鲁在邮件中表示，他与合作者打算修改论文，把警告部分提到前面来。邮件中还写道，“我们欢迎同行的评审，也愿意与全球科学家交流。”

就算这项基于Schnorr 算法的技术无法攻克互联网，量子计算机也可能通过运行Shor算法最终实现这一步。安全研究员一直在设计各种被认为不易受量子攻击的替代加密系统，这类系统被称为后量子（post-quantum）或量子安全（quantum-safe）。当然，研究人员今后可能会发现打败这些系统的量子算法，造成不堪设想的后果。

“对于数字基础设施的信心可能会崩塌，”Mosca说，“我们对量子安全迁移的管理将从技术生命周期管理突然过渡到危机管理，”他说，“到时候无论从哪方面看都会很糟。”

参考文献：

1. Yan, B.et al. Preprint at https://arxiv.org/abs/2212.12372 (2022).

2. Shor, P. W.Phys. Rev. A52, R2493–R2496 (1995).

3. Bernstein, D. J., Biasse, J.-F. & Mosca, M. inPost-Quantum CryptographyVol. 10346 (eds Lange, T. & Takagi, T.) 330–346 (Springer, 2017).

原文以Historic US research strike ends — but energizes a movement标题发表在2022年1月12日《自然》的新闻版块上