量子鲁棒签名的未来——多元密码学时代即将开启？

我开门见山。我最喜欢的两种密码学方法是多元密码学和同源密码学。为什么是同源？因为它们将使我们能够将椭圆曲线扩展到量子鲁棒时代。在我看来，离散椭圆曲线是美丽的，并且几乎用于每一次互联网连接。

数字签名是数字信任的基本构件。为此，Bob 创建了一个密钥对——一个公钥和一个私钥。然后他用私钥对消息的哈希值进行签名，然后 Alice 用他的公钥（并且该公钥已由 Trent 验证）验证签名：

但我们现有的签名方法 RSA、ECDSA 和 Ed25519 由于缺乏量子鲁棒性，统治地位即将终结。为此，NIST 已经提前行动，并标准化了 ML-DSA (FIPS 204)、SLH-DSA (FIPS 205) 和 FN-DSA (FIPS 206)。由此，我们有了两种格密码方法 ML-DSA 和 FN-DSA，以及一种基于哈希的方法 SLH-DSA。

然而，在性能上，格密码方法完全碾压 SLH-DSA。SLH-DSA 的签名体积也很大，因此 NIST 正在努力开发这些方法的替代方案，以提供抵御失败的能力，并（希望）提升性能水平。

为此，NIST 启动了数字签名新标准的评估，并于上周宣布了九种将进入后续评估的方法：

• 同源签名：SQIsign
• 基于格的签名：HAWK
• MPC-in-the-Head 签名：MQOM（MQ on my Mind）和 SDitH（Syndrome Decoding in the Head）
• 多元签名：MAYO、QR-UOV、SNOVA 和 UOV（不平衡油醋签名）
• 基于对称密码的签名：FAEST

可以看出，多元签名是数量最多的类别。

多元密码学

在多元密码学中，我们在多项式方程中有 n 个变量。例如，如果我们有四个变量（w、x、y、z）且阶数为 2，我们可以得到 [来源]：

w² + 4wx + 3x² + 2wy − 4wz + 2wx + 6xz = 5

多元密码学是一个已知的困难问题，并且对量子计算机具有鲁棒性。使用多元密码学的方法包括油醋签名、不平衡油醋签名和 Rainbow。总体而言，Rainbow 曾是上一轮 NIST PQC（后量子密码学）签名竞赛的决赛入围者之一，但被破解了。总的来说，Liboqs 支持大多数决赛入围者，例如 MAYO 和 SNOVA [此处]：

使用 SNOVA 25.5.4 的运行示例如下 [此处]：

Liboqs. Algorithm: SNOVA_24_5_4
Message: Hello

Private key: 76e8316f3395bbaa709422304632f8be36767a2097d42dd5c30cdb8694e02a16f98bfa43671d4126294ad7cf5aab3a75 Length: 48

Public key (first 200 bytes): 76e8316f3395bbaa709422304632f8be68fb4d85f2730779d29b6ee9cf5caf8ea55641565e40aa0e44808aa9515c1e1129a3b7caf92906c617e227d4349f6365727e3ce8137d6d2b263bc2c2394122b94023a4a84d586f43ec11c16a7d1467f1a737b36282914fa40f1eb2b9d5924011bbe068cd6267c354c562a62565f10726a0f940be31066f931d8a25e9f3a2ed4ca41340cc74bf1f6344b643fcfd789f433f95c367af375563b921c95c6d2f9e3040894aa132487d99ba3f9198349c7035ce35e9391528da43
Length: 1016

Signature (first 200 bytes): 7466e0bf5acd06c1f22bcca0232b6a78f31dcc58df924c08e688d71b62547ffed79f54fbd3ff69f45e213727781e3309e03a731ebc14812f92fccfe1b70d7595eaaf200c5fc346cee52897630668f8e579173575a1757251ab2cb5f5cd1484e7793d6cf7bb20e70aa93c1dee1d15a5e2328a486167574366e988960b109d682b63bf866d3c9592ecb2b47888cdc0eb6d0d7c1cc2e86c781209980157ed6910b36d0e2b8a4c7eed77a8dfd822e7d714b0956284be7b715b7b0c50c9bf532e00394e53320b8332eae5
Length: 248

Verify: OK

我们可以看到它的签名相对较小，为 248 字节，公钥大小合理，为 1,016 字节。MAYO-1 的公钥为 1,420 字节，签名为 454 字节，但具有更好的性能水平 [此处]：

Liboqs. Algorithm: MAYO-1
Message: Hello

Private key: 79eda4b2f8428939f5ed794ad8c9b8a258cdb1642f7f1a7b Length: 24

Public key (first 200 bytes): d3c58bfa7f1db9117e423e9a4c08a1bd588fc96aeb52973c8da558ec161fafa70b0b0004f06d9d2c29e61b643c6adb95a94600f99409885a8ce2b4d43aaf2fcdb51a73d48c07b9680c29ffc100b7e5f1ac1d1bb5b9d178a114e21ef70d24c72d5487d476e432bda43d5585f7781e9fb0e8861c5c38fb491369ad054d8224a18dde5219c51d7f03cb742ad6253c7a5b4983e1b87f6a5d68b81c378dddd78911add31138a6ef1cffc887f841a50bb2ff4113eb95c132a283ba2ca096774c752a284fbb6149837db61e
Length: 1420

Signature (first 200 bytes): 80986d9acaed98ad820b58d81b274b8b1fd96c6dd84400055dc80a7d2e19bcca1effddf85856cf210d2cc4505ad69b3fb853366e3822adeffd873b633105cfa8b869da81bc9328a315002b77ef0d271a58e01d79ad641d636b2ee7e3f3ce78e790f6e9da16c799d4e0ce51e4aca05f1865f14ecb0f2d9fd22e028b212783b899b8d3e66e2635e5c7c38f1f2f27684d10d861cf79ef9d4926fb998e14073cac348f2b6ff53f6ef1c0662e4f4ff30f2761f9101f5362dc511ab382fcf00d8591f2ede729de35b11e6d
Length: 454

Verify: OK

MPC-in-the-Head 签名

被选中的方法是 MQOM（MQ on my Mind）和 SDitH（Syndrome Decoding in the Head）。这些方法使用非交互式 零知识证明 和 MPC（多方计算）。使用 MPC，我们可以将一个问题拆分成多个计算元素，这些元素可以协作以产生结果，并且没有任何一个元素能在中间阶段看到计算过程。这种方法的一大优势是只使用对称密钥方法（分组密码和哈希函数）。

为了生成她的签名密钥，Peggy（证明者）生成一个随机的对称密钥。这将是她的 私钥 (sk)。然后她创建一个公开的明文块，并用她的对称密钥将其加密成一个 公钥密文块。这两个元素成为她的公钥，如图 1 所示。

图 1：生成私钥 (sk) 和公钥 (pk)

虽然许多零知识证明方法使用 Fiat-Shamir 或 Schnorr 方法，但 Picnic 使用了一种 MPC-in-the-Head 方法，其中 Peggy 采用一个任意电路（由 AND 和 XOR 门组成），执行 MPC 中的主要步骤，然后向 Victor（验证者）展示计算结果。选择 LowMC 电路是因为它允许 Peggy 为 Victor 计算一个零知识证明，以表明她知道她的密钥（sk）。LowMC 定义了一族分组密码，可用于多方计算 (MPC) 和全同态加密方法。

在该方法中（如图 2 所示），我们生成一个随机明文块（p）和一个随机密钥（sk）。接下来，我们计算 C = LowMC(sk, p)，然后确定公钥 pk = (C, p)。为了签名，我们定义对 sk 的知识，使得 C = LowMC(sk, p)，并且消息 m 和公钥 pk 被整合到签名证明中。因此，签名本质上就是使用消息作为 nonce 值对 sk 的知识证明。

图 2：密钥生成和签名

MPC-in-the-Head 的一个例子是 Picnic：

同源密码学

SQIsign。此处

如果我们有两条椭圆曲线（E₁ 和 E₂），我们可以创建一个函数，将 E₁ 上的点 (P) 映射到 E₂ 上的点 Q。这个函数被称为 同源 (isogeny)。如果我们能实现这个映射，E₁ 上的每个点都可以映射到 E₂ 上。那么我们的私钥就是同源，公钥就是椭圆曲线。对于密钥交换，Bob 和 Alice 混合他们的同源和对方的曲线，生成一个秘密曲线。

因此，对于同源椭圆曲线，我们处理的不是单条椭圆曲线，而是一族椭圆曲线 [论文]。一个同源是一个映射 ϕ: E₁ -> E₂，其中源曲线 E₁ 上的点映射到目标曲线 E₂ 上。事实证明，对于每个同源 ϕ: E₁ -> E₂，都有一个对偶同源 ϕ: E₂ -> E₁，因此我们可以说，如果两条曲线由一个同源连接，则它们互为同源：

让我们以 Bob 和 Alice 生成相同共享密钥（就像在 Diffie-Hellman 方法中那样）为例。首先，Alice 有一条起始曲线 E₀，以及该曲线上的四个点：PA、QA、PB、QB。

然后 Alice 选择两个随机值 ma 和 nA 并保密。这些将是标量值。

然后她确定一个秘密点 Ra，即：

Ra = ma × Pa + na × Qa

这是她的秘密同源（ϕa）。然后她使用这个同源变换 Pb 和 Pq，Alice 在点 Pb 和 Qb 处计算 ϕA。

然后她将 Ea（她的公钥）以及两个变换后的点（ϕA(Pb) 和 ϕA(Qb)）发送给 Bob。

Bob 做同样的事情，但交换 a 和 b 的值，将 Pa 换成 Pb，Qa 换成 Qb，反之亦然。他将生成自己的随机值 mb 和 nb。Bob 计算他的秘密：（ϕB）。

以下定义了交换过程 [1]：

接下来，Alice 使用 Ea、ϕa(Pa)、ϕb(Qa) 来构造一个同源 ϕ′a，使用 ma × ϕa(Pa)+ na × ϕb(qa)。

Bob 使用 Ea、ϕa(Pb)、ϕa(Qb) 来构造一个同源 ϕ′b，使用 mb × ϕa(Pb)+ nb × ϕa(Qb)。

现在 ϕ′a 映射到曲线 Eab，而 ϕ′b 映射到 Eba，我们可以证明它们是同构的。之后，我们可以从 j-不变量计算一个值，其中 j(Eab) 等于 j(Eba)，并且这将是 Bob 和 Alice 之间相同的共享秘密。对于曲线 y² = x³ + px + q，j-不变量是：

最后，Bob 和 Alice 将拥有相同的密钥，并且他们会知道量子计算机无法破解它，并且之前的任何密钥也无法被破解。

同源密码学的一个例子是 SIKE：

SIKE（超奇异同源密钥封装）用于 KEM

不幸的是，SIKE 在上一轮中被破解了。

格密码学

HAWK 是一种基于格的签名方法，它使用格同构问题 (LIP) 创建签名。它在签名和验证方面比 Dilithium 更快。它还具有低内存占用，并支持多种硬件。目前没有掩码功能，这可能容易受到侧信道攻击。对于 HAWK 涉及的安全证明存在一些担忧。HAWK.

对称密钥

FAEST 使用对称密钥原语。这直接关联到 AES128（Level 1）、AES192（Level 3）和 AES256（Level 5）的安全性。密钥对 (pk, sk) 定义为：pk = (x, y) 且 sk = k，其中 Ek(x) = y。总的来说，E 是使用的分组密码，k 是私钥，x 是一个明文块。然后签名即为 sk 的非交互式知识论证。这与 Picnic 方法类似，但不同的是它使用 VOLE-in-the-Head 框架，而不是 MPC-in-the-Head (MPCitH) 框架。FAEST.

结论

如果一种多元密码学方法和一种同源密码学方法进入标准化阶段，我会非常高兴。两者在以前的方法中都失败了，但它们以更强大的姿态回归——而这正是研究的全部意义所在：先打破，再修复！

• 原文链接： medium.com/asecuritysite...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～