可能密码学总是充满遗憾吧

格密码完蛋了！吗？

2024年4月10日，一篇密码学论文发表在 IACR ePrint 上，作者是清华大学陈一镭，而这篇论文并非平平无奇，因为这篇论文的标题是 Quantum Algorithms for Lattice Problems，翻译成中文就是求解格问题的量子算法，说通俗点——格密码也不安全了。

这一研究引起了学界的广泛关注，但是事情反转了，一周之内就有多个实验室发现该攻击手段的漏洞，作者也公开承认该漏洞无法被修复。所以虚惊一场，虽然这篇论文提出了非常新颖的量子算法思路，对学术界依然有启发价值，但它并没有真正破解格密码。目前，基于格的后量子密码依然被认为是安全的。

这篇论文的 url 也十分有趣，正好是 2024 年编号为 555 的论文，即 https://eprint.iacr.org/2024/555.pdf （还是靓号嘞）。该论文需在量子计算机上对格进行攻击，所以作者并没有进行实验，也不能实验（没那么多量子比特嘞），最后因为与高斯函数相关的参数并不会按预期稳定（作者假设稳定来着），导致攻击失败。但是无论如何，格密码确实差点就完蛋了，论文刚发出来的最初那几天，没发现漏洞的人大概觉得那是密码学界的第二次 Shor 时刻——如果陈的论文成立，意味着全人类辛辛苦苦选拔了数年的格密码，还没全面部署就没了。

然而，一次攻击的失败不能等同于系统绝对安全，它只能证明这条进攻路线走不通，未来还都说不好的嘞。

加壳的曙光——多线性映射——但它死掉了

这件事情让我不由想起多线性映射的故事，大概是 2014 年或者 2015 年的样子，西安电子科技大学胡予濮教授团队用零化攻击给 GGH13 多线性映射打烂了。多线性映射能干嘛？双线性映射能三方一轮的密钥交换，那 N 线性映射理论上就可以 N+1 方一轮的密钥交换了！咳咳不止于此密码学有个叫 iO 的东东，翻译是不可区分混淆，说白了就和逆向里的加壳一样，但是不同的是，这里脱壳的难度等同于破解相应的数学困难问题，而不是和攻防里的脱壳一样拿工具就可以办到的，你得拿量子计算机——如果基于格的，那你拿一百万台量子计算机都不用想逆向的事情了。而 iO 这个东东能让加壳变得很轻松，如果 GGH13 是安全的，那可能现在的软件app 啥的都不可能被逆向了，也不用什么版权法了，你要是能逆，顶刊就是你的了；但是西电这个工作说了，这个多线性映射都是不安全滴！西电的这个工作看起来没漏洞，那咋办，那就别办了，所以现在多线性映射彻底似了。

直到 2020 年，才有用更基础的假设构造了 iO 并证明了其安全性，即 JLS20。但是其效率并非多线性映射的成百上千倍，还得再加个指数，工业根本想都不用想，加密个 S-box 就要到天荒地老了。