POKEx: Performance analysis of POKE-key exchange and SIDH-variants

想象一下，互联网是一个巨大的、繁忙的城市，每个人都在向彼此发送秘密信件。为了保护这些信件不被小偷窃取，我们使用被称为“加密”的“锁”。几十年来，最好的锁是利用那些“易于单向进行但极难逆向还原”的数学问题构建的，就像将颜料混合在一起一样。然而，科学家们担心在未来，超级强大的计算机（称为量子计算机）能够瞬间解开这些锁，让我们的秘密处于完全暴露的状态。为了阻止这种情况，研究人员正在构建一种基于一种奇特且美丽的数学分支——“同源”（isogenies）的新型锁。你可以把“同源”想象成连接不同形状（数学曲线）的一种特殊的桥梁。长期以来，最受欢迎的桥梁设计被称为 SIDH。它之所以闻名，是因为其锁非常小巧且快速，使其成为了保护我们未来数字世界的有力竞争者。

但是，在 2 enough 2023 年，一对研究人员发现了一个可以破解 SIDH 桥梁的巧妙技巧。他们发现，桥梁的设计者不小心让路径的地图变得清晰可见，使得任何人只要观察就能推导出秘密路线。这造成了沉重的打击，因为这意味着最受期待的“量子安全”锁实际上已经被破解了。自那以后，科学家们一直在拼命尝试构建能够更好地隐藏地图的新桥梁。有些人试图用毯子遮盖地图（掩蔽法），而另一些人则试图用不同的材料来建造桥梁。悬而未决的大问题是：我们能否建造一座既坚不可摧又足够快、能在现实世界中使用的桥梁？

这篇题为“POKEx”的论文，步入了这片混乱的施工现场，去测试一种名为 POKÉ 的新型闪亮桥梁设计。作者 Hyeonhak Kim 和 Suhri Kim 决定将 POKÉ 加密方法转化为一个完整的密钥交换系统（他们称之为 POKEx），并让它与其他试图修复破碎 SIDH 桥梁的顶尖选手进行竞赛。他们不仅仅是在猜测；他们构建了这些系统的运行版本，并在一台强大的计算机上进行了计时。他们的主要发现是，POKEx 是目前所有基于同源的桥梁中最快且最高效的一个。在测试中，它的速度大约是次优替代方案（terSIDH）的 21 倍，是另一种流行设计（CSIDH）的近 65 倍。虽然它仍然比其他类型的量子安全锁要慢，但其速度和极小的体积使其成为一个非常有前景的候选方案，为保护我们的数字秘密提供了一种既不会减慢互联网速度的方法。

关于破碎桥梁与新解决方案的故事

要理解为什么这篇论文很重要，我们首先需要了解“桥梁”问题。在密码学领域，“密钥交换”就像两个人达成一个秘密密码的共识，而无需大声说出来。长期以来，SIDH 系统一直是明星选手。它使用了超奇异椭圆曲线——可以将这些想象成数学宇宙中复杂且扭曲的形状。SIDH 的魔力在于它使用“扭折点”（torsion points），这些点就像是这些曲线上特定的地标，以此来构建桥梁。该系统非常高效，拥有极小的密钥（数字层面的轻量化锁）并且运行速度极快。

然而，SIDH 桥梁有一个致命缺陷。为了建造这座桥，系统必须公布一些关于所使用的地标（扭折点）的信息。2023 年，Castryck 和 Decru 发现了一种方法，可以利用这些公布的地标，结合一种被称为“Kani 的粘合与分裂”（Kani's glue-and-split）的巧妙数学技巧，来重建秘密路径。这就像是留下了一串面包屑，直接通向宝藏。一旦这种攻击被发现，SIDH 就被认为已经失效，并从未来互联网安全的候选名单中被移除。

修复桥梁的竞赛

在 SIDH 倒下后，密码学界并没有放弃。他们开始建造新的桥梁来取代它。有些人试图通过用随机噪声覆盖地标来隐藏它们（一种称为 M-SIDH 的方法）。另一些人则试图通过使用“人工定向”（artificial orientation）来彻底改变桥梁的形状（terSIDH）。还有 CSIDH，这是另一种不同的桥梁类型，它不受同样的攻击影响，但自身存在速度问题。

问题在于，这些新桥梁要么太慢，要么体积太大。用噪声覆盖地标需要更大的数字来保持安全性，这使得锁变得沉重且难以使用。改变桥梁的形状（terSIDH）虽然有所帮助，但它仍然存在可能带来危险的速度波动。社区需要一个既安全又快速的解决方案。

POKEx 登场：速度之王

这就是论文中的新英雄 POKEx 进入舞台的时候。POKEx 基于 Basso 和 Maino 最近提出的 POKÉ 方案。本文的作者将 POKÉ 转化为了一个完整的密钥交换系统，具备了生成密钥和安全交换秘密所需的所有必要步骤。

POKEx 的秘诀在于它如何处理“地标”。它不像旧的 SIDH 那样只使用一维路径，而是使用“二维表示”。想象一下尝试横渡河流。SIDH 就像是走在单块木板上，如果有人看到了你的落脚点，他们就能推算出你的路径。然而，POKEX 就像是走在一个格状的木板阵列上，你可以同时向两个方向移动。这使得路径变得更难被猜中。此外，POKEx 使用了一种特殊的数学域（形式为 $2^a3^b5^c-1$ 的素数），这使得计算非常快速，而不像其他新桥梁必须使用更大、更慢的数字。

大对决：数据说明了什么

作者不仅是在空谈 POKEx；他们对其进行了实测。他们构建了软件，让 POKEx 与其他顶尖选手（M-SIDH、terSIDH 和 CSIDH）同台竞技。他们将所有系统都设定在相同的安全等级（NIST 安全等级 1，即保护国家机密数据的标准），并记录了交换密钥所需的时间。

结果令人震惊：

• M-SIDH 是其中最慢的，完成 POKEx 仅需一瞬间的任务，它却需要近 190 秒。作者指出，这使得 M-SIDH 在实际应用中并不切实际。
• terSIDH 比 M-SIDH 快得多，但仍需约 6.5 秒。
• CSIDH 用时约 20 秒。
• 然而，POKEx 仅用了 306.95 毫秒（约 0.3 秒）就完成了任务。

直观来看，POKEx 的速度是 terSIDH 的 21.21 倍，是 CSIDH 的 64.97 倍。这使 POKEx 成为了目前基于同源密钥交换的冠军。

它完美吗？

论文谨慎地没有称其为“完美”的解决方案。虽然 POKEx 是所有同源桥梁中最快的，但它仍然比其他类型的量子安全锁（如 ML-KEM，在测试中仅耗时 0.10 毫秒）要慢得多。然而，作者指出了一项至关重要的权衡。ML-KEM 虽然快，但其“锁”（公钥和密文）非常巨大，占据了大量的互联网带宽。相比之下，POKEx 拥有非常小的密钥（公钥仅为 324 字节），这意味着它占用的带宽更少。在互联网速度和数据限制至关重要的世界里，这种小巧的体积是一个巨大的优势。

总结

这篇论文表明，虽然旧的 SIDH 桥梁已经破碎，但通往新、安全桥梁的道路是敞开的。POKEx 是目前同源家族中最具前景的候选者，它提供了高速与小体积这一罕见的结合。它证明了我们可以构建出既能抵御量子攻击，又不会拖慢我们数字生活的锁。虽然它仍需更多努力来追赶其他量子安全方法的速度，但其效率表明，它可能成为保护我们未来互联网安全的关键工具，尤其是在节省数据空间与节省时间同样重要的场景下。