ACM通信
新闻
Post-Quantum密码学
信贷:ArtemisDiana
长期以来，数字信息的交换一直受到公钥加密技术的保护，这使得发送者可以放心地加密他们的数据，只有预期的接收者才能解密和读取它。接收者可以自由地共享他们的公钥进行加密，因为推导用于解密的私钥将需要不切实际的大计算，例如分解两个非常大的质数的乘积。
然而，在20世纪90年代，数学家Peter Shor(当时在贝尔实验室和继任者AT&T研究，现在在麻省理工学院)表明，量子计算机可以以指数级的速度进行因式分解和计算“离散对数”，极大地刺激了量子计算的研究。然而，尽管有数十亿美元的投资和重大的实验进展，量子计算机仍然太小，而且容易出错，还不足以构成加密威胁。不过，如果他们真的大规模成功，新数据和加密档案都可能容易受到窥探。
为了解决这种可能性，美国国家标准与技术研究所(NIST)一直在评估“后量子密码学”(PQC)的建议。虽然现在很清楚，量子计算机解决一些大问题的速度比经典计算机快得多，但人们希望有其他的密码方案永远超出它们的能力范围。
混合动力系统
安全风险是真实存在的，但事实并非如此直接威胁到绝大多数加密数据。“批量加密不存在量子问题，”安全技术专家布鲁斯·施奈尔说。大多数数据使用对称算法加密，例如高级加密标准(AES)，它使用相同的密钥进行解密。只要发送方和接收方能够保持共享密钥的秘密，这种计算效率高的方案就可以正常工作。由Lov Grover(当时也在贝尔实验室)在20世纪90年代开发的第二种量子算法可以比经典计算更快地破解对称加密，但施奈尔说，“用量子计算机加速计算的最好结果……是一个平方根的因素”，所以可以用稍微长一点的密钥击败攻击。
挑战在于安全地建立共享密钥。密钥分发曾经使用安全通道或物理交换等方法，但这些方法对于日常使用来说很麻烦。(量子密钥分发可以检测到任何窃听行为，但这项要求很高的技术不太可能对商业目的产生影响。)
这种情况随着1976年Whitfield Diffie和Martin Hellman(他们共享ACM的A.M.2015年图灵奖)，它描述了双方如何在不暴露秘密的情况下分享秘密。该方案利用了支持乘法运算的数学群，如椭圆曲线。各方商定一个起点，然后各自应用一个私有乘数，并将结果传递给另一方，后者再应用自己的私有乘数。通过这种方式，它们可以计算相同的密钥，但中间结果可以在不泄露密钥的情况下发送。
尽管乘法运算相对简单，但该方案的安全性取决于反转计算的指数级难度。然而，量子计算机使用肖尔算法可以更快地完成它，然后使用结果解密用对称算法加密的大量数据。
不是竞争
加密技术小组的小组经理、数学家莉莉·陈(Lily Chen)说，NIST从2011年开始准备这个项目，并从2016年开始征求PQC的建议。除了公开密钥协议，该项目还征求了用于密钥建立、签署文档和软件源代码验证的数字签名算法。
为了节约自己的资源和社区的关键关注，NIST将69个第一轮提交的文件缩小到26个候选人进入第二轮，然后缩小到7个决赛候选人和8个备选候选人进入第三轮。欧洲合作者在提案中有大量代表。
陈说，选择不仅评估了经典和量子安全性，还评估了性能要求，如处理能力和密钥大小，以及侧通道阻力。此外，她说，“我们想要来自不同类别的候选人”，所以列表包括基于格的、基于代码的、基于哈希的、多元二次的和基于等同性的算法。
陈说:“没有社区，我们无法完成这项工作。”他补充说，公开的公众评审对项目的成功至关重要。“没有多少人了解深层数学理论，也没有多少人了解破解它的密码学。”
2022年7月，NIST宣布了他们的标准的四个决赛选手——用于加密的crystals - kyber和用于数字签名的crystals - dlithium、FALCON和SPHINCS+。NIST还选择了其他几个候选项目进行进一步考虑。该机构预计将在2024年发布正式标准。
经典的消除
尽管进行了漫长的评估，但一些成功的候选人直到最近才被发现容易受到经典攻击。例如，多元公钥系统彩虹(Rainbow)曾被期待加入数字签名算法的行列。然而，2022年3月，瑞士苏黎世IBM研究院的沃德·布伦斯在“笔记本电脑上的周末”彻底破坏了彩虹。
另一种被称为SIKE(超奇异同源体密钥封装)的加密方案已被列入进一步研究的名单。然而，就在NIST宣布这一消息的几周后，比利时鲁汶大学的数学家沃特·卡斯特里克和托马斯·德克鲁演示了如何“在大约一小时内”在单个核上破解它。
“没有多少人了解深层数学理论，也没有多少人了解破解它的密码学。”
ike算法是对Diffie-Hellman协议的扩展。发送方和接收方不是在椭圆曲线上用秘密标量乘以点，而是在整个椭圆曲线上执行秘密的转换序列(等同性)。不幸的是，清楚地指定这个更抽象的过程需要交换一些辅助数据。
Castryck说，这“实际上是一个非常好的把戏，但也是一个从一开始就令人担忧的把戏”，这导致它只在第四轮获得了试用期批准。Castryck说，额外的信息“也是这次袭击的关键因素”。“我认为NIST的处理是正确的，”他说，“但事实上，它让你怀疑你是否标准化得太快了。”
德国波鸿市马克斯·普朗克安全和隐私研究所和荷兰奈梅亨大学的彼得·施瓦贝说:“这真的是对社会的一个很好的提醒，这类事情可能发生，而且确实发生了。”“有人提出了一个想法，然后很多很多聪明人研究了很长时间，都没能打破它，”CRYSTALS团队成员施瓦贝说。“理想的情况是，他们没有公开打破它，并描述他们是如何打破它的，然后我们就会对这个系统获得信任。”
漫长的学习过程
然而，Schwabe说:“除了基于哈希的签名，现在正在标准化的方案，以及仍然处于第四轮竞争中的方案，没有一个方案得到了与我们今天使用的椭圆曲线加密相同的研究程度。”
量子攻击更难评估，因为“我们还不知道量子计算机能做什么，”Schwabe说。研究人员已经令人信服地证明，量子计算机可以用多项式资源解决存在的问题，但对于经典计算机来说，这总是需要指数资源。谷歌和其他公司在一些选定的问题上展示了“量子优势”(最初称为“量子优势”)，即使是在今天的研究机器上。
然而，PQC的目标是实用的算法，即使有全面的、经过错误修正的量子计算机，也肯定需要指数级的资源。事实上，2011年Scott Aaronson(当时在麻省理工学院，现在在德克萨斯大学奥斯汀分校)和拉脱维亚大学Andris Ambainis的一篇论文认为，指数加速只能“针对某些‘结构化’问题”实现。例如，肖尔的算法通过同时识别多个量子比特(量子位)状态的周期性来处理因式分解和离散对数。然而，在2022年4月，NTT社会信息实验室的Takashi Yamakawa和NTT研究中心和普林斯顿大学的Mark Zhandry推测，对于搜索问题的指数加速来说，“结构”实际上并不需要(与Aaronson和Ambainis讨论的决策问题不同)。这代表了自20世纪90年代以来有效量子算法范围的首次重大扩展。
“它并没有立即说明现阶段是否存在经典攻击或量子攻击，”Zhandry警告说，但“它表明，相对于经典算法，存在更多潜在的量子优势问题。”他说，更重要的是，即使一种算法对经典攻击的安全性已经得到证明，对于量子攻击来说，“事情不一定会好起来”。
建立信任
Schwabe指出，有“压倒性的证据”表明，美国国家安全局(NSA)已经颠覆了协议，为自己保留了一些访问权限，但NIST早期的竞争涉及AES和安全哈希算法3 (SHA-3)，“他们获得了非常好的声誉，”他说。今天，“我发现很难想象在任何一个计划中会有那种只有美国国家安全局才能解密的后门”，或者他们会推广弱化的协议。
“我发现，很难想象在任何一个计划中，会有那种只有美国国家安全局才能解密的后门。”
“如果NIST的标准要被使用，就需要透明度，”Schneier表示同意。“我认为NIST是一个值得信赖的诚实的经纪人。”然而，“因为你看到东西到处都坏了，”他强调，未来的系统应该是敏捷的，让用户轻松地更换坏了的协议，就像他们可能会换前门的锁一样。
进一步的阅读
国家标准与技术研究院计算机安全资源中心，NIST后量子密码学项目算法选择，https://bit.ly/3SpCyvg
肖,毛重
量子计算机上质因数分解和离散对数的多项式时间算法，SIAM j。中央集权。第一版。26(1997) 1484。arxiv.org/abs/quant-ph/9508027
格罗弗，洛夫·K。
一种用于数据库搜索的快速量子力学算法，第二十八届ACM计算理论研讨会论文集。96年获得STOC”。计算机协会:212-219。arXiv: quant-ph / 9605043
Aaronson, S.和Ambainis, A。
量子加速对结构的需求，计算机科学学报，2011。arxiv.org/abs/0911.0996．
Yamakawa, T.和Zhandry, M。
无结构的可验证量子优势，(2022)。arxiv.org/abs/2204.02063
©2023 acm 0001-0782/23/02
本论文部分或全部的电子版或硬拷贝供个人或课堂使用的许可是免费的，前提是副本不是为了盈利或商业利益而制作或分发的，并且副本的第一页上必须有本通知和完整的引用。除ACM外，本作品的其他组件的版权必须受到尊重。允许有署名的摘要。以其他方式复制，重新发布，在服务器上发布，或重新分发到列表，需要事先特定的许可和/或费用。请求发布权限permissions@acm.org或传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2023 ACM, Inc.
没有找到条目