🔢 mathematics

MCSI: A Masked Commutative Supersingular Isogeny Key Exchange with Blinded Ephemeral Keys

本文介绍了 MCSI，这是一种基于 CSIDH 类群作用的两消息密钥交换协议，它利用认证加密来屏蔽临时密钥，从而实现隐式双向认证、向窃听者隐藏临时元素，并通过允许接收方在进行昂贵的群作用计算之前丢弃未认证的消息，显著降低计算开销。

原作者： Furkan Cifci (M.Emin Sarac High School), Osman Emre Donder (Bilkent University), Reyyan Cifci (King Fahd University of Petroleum and Minerals)

发布于 2026-08-25✓ Author reviewed ⓘ

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Furkan Cifci (M.Emin Sarac High School), Osman Emre Donder (Bilkent University), Reyyan Cifci (King Fahd University of Petroleum and Minerals)

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在争夺保护未来量子计算机时代的数字通信的竞赛中，密码学家们正在探索一个并非建立在大数字之上，而是建立在曲线几何学之上的领域。想象一个广阔、平坦的场，其中的每一个点都代表一个独特的数学形状，即椭圆曲线。在这个场中，存在一条特殊的规则，允许一种形状被转化为另一种形状，这种转化方式在已知秘密路径时易于执行，但如果不知道路径，则几乎无法逆转。这就是基于同源（isogeny-based）的密码学的基石。与其他依赖巨型密钥的方法不同，这种方法使用极小的密钥，使其在存储和传输方面具有极高的效率。然而，几年前，一个相关的系统中发现了一个重大漏洞，迫使研究人员重新思考如何使用这些曲线。挑战在于，如何找到一种方法，利用这些微小的几何形状来交换秘密密钥，同时既不向可能进行利用的强大观察者泄露任何信息，又确保双方确实是其声称的身份。

一组研究人员推出了一种名为 MCSI 的新协议，全称是“掩码交换超奇异同源密钥交换”（Masked Commutative Supersingular Isogeny Key Exchange）。该系统旨在让两个人（我们称之为爱丽丝和鲍勃）能够在开放网络上建立共享密钥，而窃听者无法得知他们在对话过程中使用的临时值。创新的核心在于他们如何隐藏这些临时值。在以往的尝试中，临时值是直接发送的，这要求接收方执行复杂的、耗时的数学运算来检查消息是否有效。这产生了一个安全风险：恶意攻击者可以通过向服务器发送大量虚假消息，迫使服务器在无用的计算上浪费计算能力。MCSI 通过将临时值包裹在一个安全的、经过身份验证的信封中解决了这个问题。在接收方打开信封进行数学检查之前，它会先验证数字封条。如果封条破损或缺失，消息会被立即丢弃，从而避免接收方进行繁重的计算工作。这一简单的改变保护了系统免受不良行为者的冲击。

研究人员证明，只要双方遵循规则，这种方法每次都能完美运行，最终生成的密钥误差为零。他们还展示了信封内的临时值对监听者而言是隐藏的，并且数字封条能有效防止攻击者篡改消息。至关重要的是，该系统的安全性并不依赖于已被证明对于此类特定曲线失效的数学假设，而是依赖于解决一个涉及这些曲线排列的特定谜题的难度，即使对于量子计算机来说，这个问题仍然很难。团队还表明，一种常见的做法——即在加密消息中添加一层简单的随机字节替换以使其看起来更随机——实际上并没有增加真正的安全性，这一发现有助于优化未来的设计。

为了确保理论在现实世界中站得住脚，该团队构建了两次该系统，一次使用高级编程语言，另一次使用用于快速软件的低级语言。他们进行了数千次测试，通过比较两个版本的运行结果来确保它们完全匹配。他们的测量结果显示，该协议是一个可工作的参考实现，其中加密和解密层所花费的时间相对于核心数学运算所需的时间来说微乎其微，几乎可以忽略不计。然而，他们也在自己的代码中发现了一个显著的弱点。由于执行核心计算所需的时间取决于密钥本身，攻击者如果能够测量多次会话的时间，就有可能推测出部分密钥。研究人员明确指出了这个缺陷：目前的实现版本在被重写为“常数时间”（constant time）运行——即计算持续时间必须与密钥无关——之前，并不具备在现实世界中部署的安全性能。

论文还讨论了一个关于该系统应使用哪种数学素数的常见误解。许多专家在处理其他类型的加密时使用了特定的特大素数，并假设它们在这里同样适用。研究人员证明，其中一个最著名的素数（用于标准曲线 P-521）对于这种特定类型的密钥交换是完全无法使用的。他们表明，该系统所需的数学结构在那个素数下根本不存在，因此必须使用一个专门构造的数字。这一发现对于任何试图构建此类系统的人来说都至关重要，因为它防止了使用会导致设计崩溃的标准工具。

虽然该协议成功隐藏了临时值并防止了拒绝服务攻击，但作者谨慎地指出了一些尚未证明的内容。他们尚未证明如果攻击者能够揭示会话期间使用的临时秘密，系统是否仍能保持安全；也尚未证明系统在面对攻击者以更复杂的方式主动干扰消息时是否安全。此外，隐藏临时值并不具备前向安全性（forward secret）；如果攻击者在未来窃取了长期密钥，他们可以回溯并剥离旧记录消息中的保护层以查看临时值，尽管最终的会话密钥可能依然安全。研究人员总结道，虽然 MCSI 是一个具有工作参考实现的可靠规范，但它尚未准备好面向公众。前进的道路需要构建一个常数时间运行的版本以消除时间泄漏，并证明系统能够抵御更激进的攻击。在这些步骤完成之前，这里描述的协议仅是一个带有工作参考的规范，不应被任何人投入实际部署。

技术摘要：MCSI —— 一种掩码交换型超奇异同源密钥交换协议

1. 问题陈述

本文针对基于交换型超奇异同源（CSIDH）群作用的后量子认证密钥交换（AKE）协议的设计进行了研究。虽然 CSIDH 在后量子家族中提供了最小的公钥尺寸，但基于该群作用的标准未认证交换存在两个主要问题：

拒绝服务（DoS）漏洞： 在标准交换中，响应者必须在验证消息真实性之前，对发起者提供的曲线进行昂贵的群作用计算（耗时数十毫秒）。一个未认证的攻击者可以迫使响应者重复执行这种高成本的计算。
缺乏临时机密性： 标准 CSIDH 交换在明文中传输临时公元素（曲线），这使得被动窃听者能够观察到密钥交换的中间状态。

此外，本文澄清了一个常见的误解：与 SIDH 分支的同源密码学不同，交换型 CSIDH 分支并不发布扭点图像。因此，在此语境下的“掩码”（masking）并非针对扭点攻击（这类攻击破坏了 SIDH）的防御措施，而是一种隐藏临时公元素并防止 DoS 的机制。

2. 方法论与协议设计

作者提出了 MCSI（掩码交换型超奇异同源），这是一种将 CSIDH 群作用与认证加密相结合的两消息密钥交换协议。

核心机制

静态密钥： 双方各持有一对由 CSIDH 类群作用导出的长期静态密钥对 $(a, pk_A)$ 和 $(b, pk_B)$ 。
静态-静态共享值 ( $Z_{ss}$ )： 在任何会话开始前，双方使用其静态私钥和对方的静态公钥计算共享值 $Z_{ss} = (ab) \star x_0$ 。由于类群的交换性，双方都会得到相同的 $Z_{ss}$ 。
遮蔽层： 静态-静态共享值 $Z_{ss}$ 被用于派生对称密钥，以进行关联数据认证加密（AEAD）。
协议流程：
1. 发起者： 生成临时私密值 $u$ ，计算临时公元素 $T_A = u \star x_0$ ，并使用由 $Z_{ss}$ 密钥化的 AEAD 方案对 $T_A$ 进行加密。随后发送密文。
2. 响应者： 使用从 $Z_{ss}$ 缓存的密钥解密消息。如果认证标签（tag）校验失败，响应者会在一次哈希/标签检查后立即中止，从而避免昂贵的群作用计算。如果校验通过，响应者恢复 $T_A$ ，生成自身的临时私密值 $w$ ，计算 $T_B = w \star x_0$ ，并将其加密后发回。
3. 密钥派生： 双方使用通过哈希处理的传输记录（transcript）以及三个共享值来计算会话密钥：
  - $Z_{ee} = (uw) \star x_0$ （临时-临时，提供前向安全性）。
  - $Z_{es} = (ub) \star x_0$ （临时-静态，提供认证）。
  - $Z_{se} = (aw) \star x_0$ （静态-临时，提供认证）。
  - $Z_{ss}$ （静态-静态，用于掩码）。

设计原理

作者明确拒绝从会话密钥本身派生遮蔽密钥，因为这会产生循环依赖。相反，它依赖于预先共享的静态-静态值。作者还证明了在密文中添加公开的字节替换层（S-box）不会提供额外的安全性，从而证明了使用标准 AEAD 而无需此类修改的合理性。

3. 核心贡献

本文做出了以下具体贡献：

协议规范： 提供了一个在抽象有效群作用上的 MCSI 完整规范，并以 CSIDH 作为实例化。其中包含了一个设计论证，证明遮蔽密钥必须从静态密钥而非会话密钥中派生。
正确性证明： 一个证明零误差正确性的定理，该定理严格依赖于类群的交换性、群作用公理以及蒙哥马利曲线代表元的唯一性。
安全性证明： 在随机预言机模型（ROM）下的三个安全性定理，均归约至强并行假设（GA-StCDH）：
- 会话密钥不可区分性： 对于被动攻击者而言，会话密钥与随机值不可区分。
- 遮蔽机密性： 临时元素对被动观察者是隐藏的。
- 传输完整性： 没有静态密钥的攻击者无法伪造会被接收方接受的消息。
- 注：证明过程显式地避开了已知在 CSIDH 中失效的判定群作用假设（GA-DDH），这是由于亏格理论导致的。
参数分析： 对素数选择进行了批判性分析。作者证明，为标准椭圆曲线离散对数问题选择的素数（例如 NIST P-521， $p = 2^{521}-1$ ）对于 CSIDH 是不可用的，因为 $p+1$ 缺乏生成高效可计算类群作用所需的平滑性（小素因子）。
参考实现： 提供了一个使用已知答案向量进行交叉验证的可移植 C 语言和 Python 双重实现。
侧信道审计： 对参考实现的计时行为进行了详细测量，揭示了未优化的实现会通过执行时间泄露私钥的一范数（one-norm）。

4. 结果与测量

性能与开销

代价： 该协议每方每会话需要四次群作用计算（外加每个对端一次用于 $Z_{ss}$ 的缓存计算）。这比未认证的 CSIDH 交换高出两倍，但对称层（AEAD）的开销（约 4 $\mu$ s）相对于群作用（约 130 ms）而言可以忽略不计。
DoS 防御： 主要的性能提升在于抗 DoS 能力。未认证的消息会在标签检查后（约 2.4 $\mu$ s）被拒绝，而不是在群作用计算之后（约 130 ms），这实现了约 50,000 倍的加速。
尺寸： MCSI 提供的公钥显著小于基于格（ML-KEM）或基于编码（Classic McEliece）的替代方案。对于 512 位安全等级，公钥为 64 字节，总会话流量为 192 字节。

实现发现

计时泄露： 参考实现并非恒定时间（constant-time）。作者测量到私钥的一范数与执行时间之间存在强相关性（皮尔逊相关系数 0.90）。
泄露严重程度： 两个一范数仅相差 5（在 370 个可能值中）的密钥可以通过大约 200 次计时测量进行区分。
验证： 在审计中发现，Validate 函数（检查是否为超奇异曲线）不存在依赖于秘密的控制流，尽管群作用计算本身由于构造原因会泄露信息。

5. 重要性与局限性

本文将 MCSI 定位为一个带有工作参考实现的规范，而并非一个部署就绪的解决方案。

重要性：

它证明了在 CSIDH 上实现具有隐式相互认证和临时机密性的认证密钥交换是可行的。
它提供了一个严谨的证明，表明对临时元素的“掩码”并不依赖于已失效的判定假设（GA-DDH）。
它强调了对于交换型同源方案，素数的选择必须专门为平滑性而构建，而非直接沿用现有的 ECC 标准，这是一个经常被忽视的关键约束。

明确的局限性（本文未证明的内容）：

遮蔽性的前向安全性： 如果攻击者随后获得了静态密钥，他们可以重新计算 $Z_{ss}$ 并剥离传输记录中的遮蔽，从而揭示临时元素。
强安全模型： 证明并未涵盖 Canetti-Krawczyk (CK) 模型或扩展 CK 模型（例如，针对临时密钥泄露或密钥交换冒充的抵抗力）。
主动攻击者： 虽然证明了传输完整性，但尚未建立针对控制消息传递的主动攻击者的完整会话密钥安全性。
实现安全性： 参考实现不是恒定时间的，并且容易受到计时攻击。作者指出，恒定时间执行是部署前的必要前提。
恶意对端： 该协议不包含 Fujisaki-Okamoto 变换，因此无法防御持有有效静态密钥但表现恶意的对端。

总之，MCSI 提供了一个在理论上完善、高效且占用空间小的后量子密钥交换设计，但作者强调，当前的实现需要经过显著的加固（特别是恒定时间执行）后，才能被认为在现实世界中使用是安全的。