2022年2月8日，美国白宫总统行政办公室发布了最新修订的《关键和新兴技术（CET）清单》，后量子密码作为量子信息技术的一种也被列入了这个对美国国家安全战略具有潜在影响的清单。虽然看不懂这波操作，但像我这样人畜无害的理论工作者也大受震撼（颇有些蹭到热度的鼓舞）。
量子计算机是近年来一个时髦的话题，其计算能力较经典计算机有多大优势也是当前热门的研究方向。抛开量子计算机何时能够实用的争议，本文主要谈一下量子算法对现代密码学产生的影响以及后量子密码可能的发展方向。文中大多是常识性的内容，其它主观的观点受个人研究方向和知识储备的限制，难免有失偏颇甚至存在谬误，旨在抛砖引玉，供大家参考，同时也希望借此机会激励对理论计算机科学和密码学有兴趣的同学投身相关的研究。
古典密码学是研究如何保护信息在传输、存储和计算等过程中保密性、完整性、不可抵赖性、真实性等安全属性的一门学问。以发信为例，保证信件内容在传输过程中没有被他人偷窥是确保信息的保密性；确保内容没有被篡改则属于完整性保护；如果发送者在信中做了某些承诺，不可抵赖性确保其有履行承诺的义务；信件的真实性保证了收信人可确信信件的确是发信人写的（没有被冒名顶替）。
自古以来在较长的一段时间内密码主要用于军事用途和信息的保密性保护，该时期的密码称为古典密码，如罗马时期的凯撒密码和二战期间德军的恩尼格玛密码机。古典密码大多数属于对称密码范畴，双方都必须提前在安全的环境下共享一个密钥用于此后在非安全的环境下的信息保护。信息论的创始人香农证明了如果对称加密要达到无条件的安全性，那么被加密的消息长度不能超过密钥长度。
密钥安全分发的前提假设大大限制了对称密码的应用场景，而古典密码尝试用短密钥加密长消息的挑战因为安全性问题绝大多数以失败告终。
现代密码学的开创者是1976年Whitfield Diffie和Martin Hellman提出的密钥交换协议，1977年Ron Rivest、Adi Shamir和Leonard Adleman提出的RSA公钥加密，开创了现代密码学的新时代。
密钥交换协议和RSA加密都属于公钥密码，它们不再要求发送方和接收方提前安全地共享密钥：双方可通过密钥交换协议从无到有建立一个共享密钥用于对称加密，或者直接利用接收方公钥给他发加密的消息。然而，公钥密码不再具有信息论意义上的无条件安全性，而只是计算意义上的安全。
计算安全是指密码算法的安全性基于某个计算困难问题，比如Diffie-Hellman密钥交换协议的安全性可以近似理解为是基于“离散对数”问题的困难性；而RSA问题也可近似理解为随机选取两个等长的质数，从分解出是非常耗时的。
量子算法的密码优势在于，RSA等经典密码算法的计算意义安全性是建立在图灵机或与其等价的经典计算机模型基础上的。
到了上世纪90年代，Peter Shor提出的量子算法可在多项式时间内解决有限交换群的隐藏子群问题，该问题涵盖了RSA公钥加密、Diffie-Hellman密钥交换和椭圆曲线密码等常见公钥密码的底层问题。换句话说，如果一定规模的量子计算机成为现实，那么当前互联网和区块链广泛使用的公钥密码体系都不再安全。
总的来说，Grover算法与Simon算法主要针对对称密码，其对对称密码的影响在可控范围内。
为应对Grover算法，我们可将密码算法的安全参数加倍，达到与经典模型下同等的安全等级；对于Simon算法，我们可规避受到其影响的操作模式，使用量子模型下安全的操作模式。因此，量子算法对对称密码的影响较小，而Shor算法对现有的一些公钥算法的影响是致命的。目前，量子计算机还没有发展到可以分解比如RSA-1024合数的规模和量级，但密码学界已经未雨绸缪，开始准备应对后量子时代的密码危机。
后量子密码或抗量子密码主要是指设计仍然能够运行在经典计算机上且具备抵抗量子计算机攻击安全性的密码算法和协议。美国国家标准与技术研究院（NIST）在2017年展开了后量子密码标准的方案征集，进入NIST第三轮的决赛方案和备选方案包括数字签名与公钥加密。我们看到，格密码是后量子密码的最主流的技术路线。
总的来说，这些密码算法都是建立在底层问题的假想量子困难性之上，不能说哪个一定比另外某个更困难，只是那些相对较新的问题的安全性更有待公众和时间的检验。即使是比较主流的格密码算法，很多为了提升算法的效率和竞争力，引入了特殊的结构。同时带来的争议是这些结构是否同时也带来了额外攻击的可能性。
我国的研究人员在后量子密码也取得了较好的进展，其中Rainbow算法进入了NIST第三轮的决赛方案，LAC算法入选了NIST第二轮的候选算法，并且LAC的公钥加密算法和密钥交换协议分别获得了全国密码算法设计竞赛的公钥密码算法组的一等奖和二等奖各一项。我参与设计的Aigis公钥加密和签名算法也获得了该设计竞赛的两项一等奖，其它获得竞赛二等奖的算法还包括SIAKE认证加密协议、SCloud和ACKN。
值得一提的是，在全国密码算法设计竞赛公钥组一二等奖的获奖算法中，除了SIAKE是同源密码，其它都属于格密码算法，这与NIST后量子密码算法征集第三轮决赛算法中格密码占比绝大多数也是一致的。
数字签名可用于在数字世界中替代手写签名。在现实世界中，签名首先认证了签名者的身份，同时在文件上签名表达了签名者对于这份文件内容的认可。为实现以上功能，要求签名者的签名能够被大家验证认可，而难以被他人伪造。数字签名是公钥加密之外后量子密码的另一类重要的密码原语，广泛应用于公钥密码体系、网上银行、电子支付、数字钱包和区块链交易等场景。
经过四十多年的发展，现代密码学已经从对数据进行加密和签名等基本密码算法的阶段逐步过渡到对区块链、数据交易和计算进行隐私保护的后量子时代。Shor算法等量子算法对密码学的冲击总体来说是有惊无险，甚至为密码的转型和发展带来了契机，以LWE为代表的格密码等后量子密码的出现顺应也进一步推动了现代密码学的发展。