基于格子的密码系统和量子密码分析
2024-05-24量子计算机可能即将到来——当它们到来时，它们很可能能够破解我们的标准公钥加密算法。
来源:贝尔弗科学与国际事务中心研究量子计算机可能即将到来，尽管我们不知道何时到来——而且当它们到来时，它们很可能会破解我们的标准公钥加密算法。为了应对这种可能性，密码学家一直在研究抗量子公钥算法。美国国家标准与技术研究所 (NIST) 自 2017 年以来一直在举办竞赛，并且已经提出了几项标准。其中大部分都是基于格问题。
举办竞赛 拟议标准格密码学的数学围绕在多维空间中组合向量集（即格）。这些格充满了多维周期性。密码学中使用的难题是在一个大的、随机的格中找到最短的周期性。这可以通过多种不同的方式转变为公钥密码系统。自 1996 年以来，研究一直在进行，从那时起已经取得了一些非常出色的成果，包括许多实用的公钥算法。
难题 变成4 月 10 日，来自北京清华大学的陈一雷发表了一篇论文，描述了针对最短路径格问题的一种新量子攻击。这是一篇非常密集的数学论文——长达 63 页——我猜只有少数密码学家能够理解它的所有细节。（我不是其中之一。）但结论相当具有破坏性，基本上打破了所有基于格的全同态加密方案，并且更接近针对最近提出的（并获得 NIST 批准的）格密钥交换和签名方案的攻击。
发表了一篇论文然而，论文中有一个很小但很关键的错误，位于第 37 页底部。八天后，伯克利的吴宏勋和以色列魏茨曼研究所的 Thomas Vidick 分别发现了这一错误。目前形式的攻击算法不起作用。