量子计算与密码学

二十世纪后期，美国学者提出了基于量子计算机的质因数分解算法——Shor算法，从理论上证明，在当前最快的计算机上需要上万年才能完成的计算任务，量子计算机瞬间即能完成，严重地威胁到了基于这类数学难题的公钥密码系统的安全性。紧随其后的Grover量子搜索算法，对于密码破译来说，相当于把密钥的长度减少一半，种种迹象表明，通用量子计算机一旦实现，对目前广泛使用的RSA、EIGamal、ECC公钥密码和DH密钥协商协议都构成了严重的威胁。随着量子技术的不断成熟，实用量子计算机总会有到来的一天，到了那一天，密码学，特别是基于NP困难问题的公钥密码系统又该做何准备呢?现在的量子计算机具有怎样的能力?研制量子计算机的困难是什么?真正的量子计算机离我们还有多远?

首先，我们回顾量子计算机研制的历史：

量子计算机研究进展及关键问题

量子计算机研制过程中的里程碑事件

• 2001年IBM研制出7个量子位的示例型量子计算机，向世界宣布了量子计算机原理的可行性。
• 2011年9月2日，美国加州大学圣塔芭芭拉分校的科学家宣布，研制出具有冯诺依曼计算机结构的量子计算机并成功地进行了小合数的因子分解实验。
• 2013年3月1日IBM宣布找到了一种可以大规模提升量子计算机量子位数的关键技术。
• 2015年谷歌、美国国家航空航天局(NASA)和加州大学圣塔芭芭拉分校(UCSB)公开报道，实现了九个超导量子比特的操纵。
• 2017年5月3日，中国科学院在上海召开新闻发布会，宣布世界首台超越早期经典计算机的光量子计算机在我国诞生。在光学体系方面，研究团队在2016年首次实现十光子纠缠操纵的基础上，利用高品质量子点单光子源构建了世界首台超越早期经典计算机的单光子量子计算机。

十超导量子比特的纠缠态

基于单光子的量子计算原型机结构

[[192739]]

国际上最高品质和最高效率的单光子源

量子计算的目标在于打造一款通用的量子计算机——不仅能够解决任何运算问题，而且其速度更超越当今最快的超级计算机，为了更早地让量子计算机展现出它的优势，物理学家们想到了针对一些特殊的问题，可以用专用量子计算机来解决，如加拿大D-wave System的专用量子计算机，可用于解决优化的问题，可执行Grover算法。2007年2月D- Wave公司宣布研制出世界上第一台商用16量子位的量子计算机，2008年5月提高到48量子位,2011年5月30日又提高到了128量子位,2013年初又提高到了512量子位。

量子技术主要研究内容

建造量子计算机的困难在于要找到一个可以编码量子比特，满足Divincenzo判据，包括具有可扩展性、可初始化、可读出、相干时间长、可构造普适量子逻辑门、可网络化等。其中可扩展性和相干时间长是选择物理实现系统的两项重要指标。根据DARPA的量子信息科学技术路线图和《欧洲量子信息处理与通信研究现状、远景与目标战略报告》，现在确定的主要物理实现系统有量子点、超导量子电路、离子阱体系、腔量子电动力学体系、光学体系、液态核磁共振、固态量子计算等量子计算的物理实现方案。其中超导量子电路方案是利用了超导体中的约瑟夫森结来产生量子比特，因为其具有良好的可扩展性，成为量子计算机物理实现系统的研究热点。

量子计算机的为什么具有超级计算能力?

简单地讲，量子计算机利用量子力学中的叠加态原理，量子计算最大的特性就是并行性，当量子计算机对一个n量子比特的数据进行处理时，量子计算机实际上是同时对2的n次方个数据状态进行了处理。正是这种并行性使得原来在电子计算机环境下的一些困难问题在量子计算机环境下变得容易。量子计算机的这种超强计算能力，使得基于计算复杂度的现有公钥密码的安全受到挑战。

量子计算机离我们有多远?

为提高量子计算机的计算能力，需要把量子比特都耦合起来，这一难度是指数级的。2016年，Gartner预测量子计算机技术将超过10年才能成熟(如图所示)。

Gartner预测2016年新兴科技技术成熟度曲线

与经典计算机计算能力相比，当量子计算机操纵25个量子的时候，其计算能力相当于现有的计算机四核计算能力，而当量子计算机能操纵50个量子的时候，其计算能力将超过现在世界上最快的计算机——天河二号。

抗量子计算公钥密码体制

量子计算机的每一步进展都为我们带来了惊喜，同时也带来了担忧。经典密码算法面临的危机是客观存在的。面对量子计算机的潜在威胁，如何设计能够抵御量子计算攻击的密码算法值得我们深入研究。现代密码学是建立在计算复杂性理论基础之上的。例如，RSA公钥密码体制的构造基础是大整数因子分解这一NP问题，然而在量子计算机上分解大整数在量子图灵机环境下是可解的，不再是难题。量子计算对现代密码学的威胁实质就是依赖于量子计算机的高度并行计算能力，将相应的NP问题转化成了QP问题，这对于基于NP问题设计的现代公钥密码而言，其潜在的威胁是致命的。

量子算对传统密码算法的冲击

虽然今天的量子计算能力还不足以真正撼动现有密码系统，但随着量子计算技术的发展，总会有一天对现有的密码构成实际威胁。为应对量子计算机的挑战，美国国家标准局NIST(National Institute of Standards and Technology)在2016年2月召开的“后量子密码”(Post Quantum Cryptography )会议上发布“抗量子计算密码：NIST未来研究计划”报告，征集后量子密码方案，并将其作为今后抗量子计算攻击的标准，对于方案在算法实现上要求具备参数可调和、使用平台多样化，其中算法抗侧信道攻击也是一项重要的指标。

事实上，对于某些问题(如NP完全问题)，量子算法相对于传统算法并没有明显的优势。紧跟着Shor算法的出现，国内外密码学家已对基于格、基于编码和基于多变元方程密码方案展开了大量的研究，力图设计可以对抗量子计算机的经典密码算法，同时也在不断设计新的抗量子计算密码方案。

[[192740]]

经过二十多年的发展，越来越多的量子计算领域的科学家意识到，实用的量子计算机不再仅仅存在于理论之中，尽管可能造价不菲、技术难度很高，但是制造一台实用的量子计算机现在更多地成为一个工程问题，在通用量子计算机出现之前，密码学家将积极准备好新的更安全的抗量子计算密码算法，保障人们各种活动的信息安全，迎接量子时代的到来。

【本文为专栏作者“中国保密协会科学技术分会”原创稿件，转载请联系原作者】

戳这里，看该作者更多好文