量子计算在公钥密码安全中的应用
一．公钥密码安全与量子计算
二．量子与量子计算
如果一个物理量存在最小的不可分割的基本单位，那么我们就把这个不可分割的基本单位叫做量子。量子到量子计算是个漫长的发展过程，1985年，牛津大学的D. Deutsch（多伊奇）提出量子图灵机（quantum Turing machine）的概念，量子计算才开始具备了数学的基本型式。量子计算的确切定义是一种遵循量子力学规律调控量子比特进行计算的新型计算范式。量子比特不同于经典比特，只能处于0或者1，量子比特可以处在0和1的叠加态。叠加态是量子的基本状态，纠缠态是叠加态的一种特性，量子门（酉矩阵）可以对量子态做相应的计算。量子计算机在存储量、计算效率及计算效率扩展性上具有巨大的优势。在某些重要的计算场景中，量子计算最高可实现指数级的加速效果。
以当前最著名的两个量子算法为例：Shor算法相比当前最快的经典算法---数域筛法求解整数分解问题，可以达到指数级的加速。而对于搜索算法，量子搜索算法的搜索次数相比经典二分查找算法的搜索次数可达到平方级加速。由于划时代的算力优势和应用前景，量子计算领域目前正在飞速发展中。
三． 量子计算对公钥密码攻击的研究现状
目前Shor算法攻击n-比特的RSA所需的量子逻辑比特数至少是2n+1个，所需的物理比特与量子计算的容错率有很大关系。最新的研究表明，1万多个物理比特可以在177天内攻破RSA-2048。对于RSA的量子计算研究，微软谷歌做的工作比较多，还有一些大学的研究团队。针对ECDLP的量子计算研究比较少，主要是微软团队对量子攻击资源的理论估计。目前，国内对公钥的量子计算攻击，主要的团队有上海大学的王潮教授，主要利用量子优化算法实现对RSA的整数分解。
近几年，本源量子一直致力于量子算法对公钥密码的攻击实现与优化。目前已经实现了: 1. 利用量子优化算法实现32768以下整数的分解；2. 利用Shor 算法实现1024以下整数的分解；3. 利用Shor算法实现p<17以下ECDLP的求解；4. 利用Shor算法实现7维二元域下DLP的求解。基于性能考量，已将较小参数下的攻击实现通过API接口在本源量子云平台上公开展示。
四．后量子密码迁移展望
当前，量子计算的发展如火如荼，通过各国政府对量子计算的投入可以看到，很多国家都投入了大量资金发展量子计算事业。在最新的新闻中，IBM已推出了433个量子比特的芯片。在2031年之前有望交付第一台1000比特以上的通用量子计算机。这些量子计算的相关进展对于现代公钥密码算法来说，那即是处在山雨欲来风满楼的形势。
还好，很多国家政府未雨绸缪，以美国NIST为首，他们最先开展后量子密码算法的征集，目前正在按部就班地执行，预计2024年发布最终后量子密码标准。欧洲很早就开始了后量子密码的研究，2006年开始每年举办PQC会议。我国的PQC理论研究工作一直都在做，但是PQC征集以及部署相对国外较晚。
目前，部署PQC的迁移工作是重中之重。如何迁移，迁移需要哪些步骤，怎么做？如何做？这些都是问题。以简单的平台搭建为例，从硬件到软件，从软件到到协议层等，每一层又有很多细节分支，均要考虑迁移后的安全性、可用性、敏捷性和普适性。
当前，IBM不光在量子计算机方面进展迅速，他们也正在与通信技术公司沃达丰合作开发后量子密码技术。加拿大也预计将在2030年规划实现PQC的迁移。美国政府预计在2035年之前初步完成。我国政府也在积极部署后量子算法的标准制定和迁移工作。所以未来十年，后量子密码迁移工作是重中之重，也将困难重重，将面临除了工程外的其他问题，如专利问题、芯片市场的转变问题、IT生态圈、产业链和供应链的很多问题。总之，这些必须通过产学研政，各方协同联动，协同合作，一步一步攻克。
【作者简介】
合肥本源量子计算科技有限责任公司（简称“本源量子”），国内量子计算龙头企业，2017年成立于合肥市高新区，团队技术起源于中科院量子信息重点实验室。本源量子聚焦量子计算产业生态建设，打造自主可控工程化量子计算机，围绕量子芯片、量子计算测控一体机、量子操作系统、量子软件、量子计算云平台和量子计算科普教育核心业务，全栈研制开发量子计算，积极推动量子计算产业落地，聚焦生物科技、化学材料、金融分析、轮船制造、大数据等多行业领域，探索量子计算产业应用，争抢量子计算核心专利。