666 - 后量子密码巨兽的密文大小？

666 — PQC 巨兽的密文大小？

基于格签名方案的简易指南

因此，我们与 RSA、 ECDSA 和 EdDSA 长久告别，并向 ML-DSA（又名 Dilithium — 又名 FIPS 204）、FN-DSA（又名 Falcon — FIPS 206）和 SLH-DSA（又名 SPHINCS+ — FIPS 205）问好。总体而言，ML-DSA 和 FN-DSA 是基于格的方法，具有不同的实现方法。这些方法的直接对比如下：

• ML-DSA 通常比 FN-DSA 更快（签名和验证速度大约快两倍）。
• FN-DSA 可以从签名中恢复公钥，但 ML-DSA 不能（这在区块链应用中很有用）。
• FN-DSA 具有更小的密钥和密文大小。
• 对于客户端-服务器模型，FN-DSA 将更多的计算负载转移到服务器（这在物联网和边缘计算应用中很有用）。

性能和密钥大小

对于 Falcon-512（其安全性与 RSA-2048 相当），我们生成一个 897 字节的公钥、一个 1,281 字节的私钥和一个 690 字节的签名，而 FALCON-1024 提供一个 1,793 字节的公钥、一个 2,305 字节的私钥和一个 1,313 字节的签名 [ 这里 ]：

对于 ECDSA、RSA、Ed25519 和 Ed448，我们有：

Method        Public key size (B) Private key size (B)  Signature size (B)  Security level
------------------------------------------------------------------------------------------------------
Ed25519       32                  32                    64                  1 (128-bit) EdDSA
Ed448         57                  57                   112                  3 (192-bit) EdDSA
ECDSA         64                  32                    48                  1 (128-bit) ECDSA
RSA-2048     256                 256                   256                  1 (128-bit) RSA

以下提供了数字签名 PCQ 方法的分析：

Method                           Public key size    Private key size   Signature size  Security level
------------------------------------------------------------------------------------------------------
Crystals Dilithium 2 (Lattice)        1,312              2,528              2,420         1 (128-bit) Lattice
Crystals Dilithium 3                  1,952              4,000              3,293         3 (192-bit) Lattice
Crystals Dilithium 5                  2,592              4,864              4,595         5 (256-bit) Lattice
Falcon 512 (Lattice)                    897              1,281                690         1 (128-bit) Lattice
Falcon 1024                           1,793              2,305              1,330         5 (256-bit) Lattice
Rainbow Level Ia (Oil-and-Vineger)  161,600            103,648                 66         1 (128-bit) Multivariate (UOV)
Rainbow Level IIIa                  861,400            611,300                164         3 (192-bit) Multivariate (UOV)
Rainbow Level Vc                  1,885,400          1,375,700                204         5 (256-bit) Multivariate (UOV)
Sphincs SHA256-128f Simple               32                 64             17,088         1 (128-bit) Hash-based
Sphincs SHA256-192f Simple               48                 96             35,664         3 (192-bit) Hash-based
Sphincs SHA256-256f Simple               64                128             49,856         5 (256-bit) Hash-based
Picnic 3 Full                            49                 73             71,179         3 (192-bit) Symmetric
GeMSS 128                           352,188                 16                 33         1 (128-bit) Multivariate (HFEv-)
GeMSS 192                         1,237,964                 24                 53         1 (128-bit) Multivariate (HFEv-)

对于 M4 (ARM Cortex-M4 dev) [1] 上的性能，以每秒 CPU 操作数衡量。 请注意，[1] 中未执行 Rainbow 评估，因此 LUOV（一种 Oil-and-Vinegar 方法）已用于指示性能水平：

Method                           Key generation   Sign   Verify
----------------------------------------------------------------
Crystals Dilithium 2 (Lattice)        36,424     61,312   40,664
Crystals Dilithium 3                  50,752     81,792   55,000
Crystals Dilithium 5                  67,136    104,408   71,472
Falcon 512 (Lattice)                   1,680      2,484      512
Falcon 1024                            1,680      2,452      512
Rainbow Level Ia (Oil-and-Vineger)     2,969      4,720    2,732
Rainbow Level IIIa                     3,216      3,224    1,440
Rainbow Level Vc                       3,736      6,896    4,928
Sphincs SHA256-128f Simple             2,192      2,248    2,544
Sphincs SHA256-192f Simple             3,512      3,640    3,872
Sphincs SHA256-256f Simple             5,600      5,560    5,184

对于 ARM Cortex-M4 设备 [1] 上的堆栈内存大小，以字节为单位测量。 请注意，[1] 中未执行 Rainbow 评估，因此 LUOV（一种 Oil-and-Vinegar 方法）已用于指示性能水平：

Method                           Memory (Bytes)
-------------------------------------------------
Crystals Dilithium 2 (Lattice)        13,948
Crystals Dilithium 3                  13,756
Crystals Dilithium 5                  13,852
Falcon 512 (Lattice)                 117,271
Falcon 1024                          157,207
Rainbow Level Ia (Oil-and-Vineger)   404,920
Rainbow Level IIIa                   405,412
Rainbow Level Vc                     405,730
Sphincs SHA256-128f Simple             4,668
Sphincs SHA256-192f Simple             4,676
Sphincs SHA256-256f Simple             5,084

FN-DSA 方法

因此，让我们看一个 NTRU 如何工作的简单示例。 总体而言，Falcon 基于 Gentry、Peikert 和 Vaikuntanathan 方法生成基于格的签名方案，以及一个陷门采样器 — 快速傅里叶采样。 最初，我们选择三个参数：$N$、$p$ 和 $q$。 为了生成密钥对，我们选择两个多项式：f 和 g。 由此我们计算：

并且其中 f 和 f_$q$ 是私钥。 公钥是：

Bob 和 Alice 同意共享 $N$（这限制了最大的多项式幂）、$p$ 和 $q$，然后 Bob 生成两个短多项式（f 和 g），并由此生成他的密钥对。 这些多项式的系数为 -1、0 和 1。例如，对于 $N$ =11、$p$ =3 和 $q$ =32。 如果 Bob 选择以下值：

f =[−1,1,1,0,−1,0,1,0,0,1,−1]

那么作为多项式表示：

f =−1+ $x$ + $x²$ − $x^4$+ $x^6$+ $x⁹$ − $x^{10}$

然后选择 g：

g =−1+ $x²$+ $x³$+ $x⁵$− $x⁸$− $x^{10}$

然后我们应该能够计算 f 对于 (mod $p$) 和 (mod $q$) 的逆。 因此：

f ⋅ f_$p$(mod $p$)=1

f ⋅ f_$q$(mod $q$)=1

使用逆函数，我们得到 [ 这里 ]：

f_$p$ =[9,5,16,3,15,15,22,19,18,29,5]

f_$p$ =9 $x^{10}$ +5 $x$⁹+16 $x$⁸+3 $x$⁷+15 $x$⁶+15 $x$⁵+22 $x$⁴+19 $x$³+18 $x$²+29 $x$ +5

然后公钥变为：

h = $p$ ⋅ f_$q$. f(mod $q$)

在这种情况下，我们得到：

f_$q$ ⋅ g =[−5,−9,−1,−2,11,12,13,3,22,15,16,29,60,19,−2,−7,−36,−40,−50,−18,−30]

为了创建一个环，我们然后除以 $x^{N}-1$，得到：

H (Bob's Public Key): [24, 19, 18, 28, 4, 8, 5, 17, 4, 17, 16]

私钥是 f 和 f_$q$。

为了加密，我们采用 Bob 的公钥 ($h$)、一个随机多项式（r）和一个消息（M），然后计算：

$Enc$ = r ⋅ h + M

为了解密，首先我们乘以 Bob 的私钥 f_$q$ 并取 (mod $q$)：

$Dec$ =( r ⋅ h + M). f(mod $q$)

得到：

$Dec$ =( $p$ ⋅ r ⋅ f_$q$ ⋅ g + M). f(mod $q$)

由于 (f_$q$. f)(mod $q$) 为 1，我们得到：

$Dec$ =( $p$ ⋅ r ⋅ g + M ⋅ f)

最后，我们乘以 f_$p$(mod $p$)：

$Dec$ =( $p$ ⋅ r ⋅ g + M ⋅ f). f_$p$(mod $p$)

这将是：

$Dec$ = $p$ ⋅ r ⋅ f ⋅ f$p$ + M ⋅ f ⋅ f$p$(mod $p$)

由于我们有一个 $p$ 的乘数，我们将得到第一个项的零值，因为我们有 (mod $p$) 操作：

$Dec$ =0+ M ⋅ f ⋅ f_$p$(mod $p$)

由于 f ⋅ f_$p$(mod $p$) 将为 1，我们得到：

$Dec$ = M

参数的示例值为：

• 最低安全性：$N$ =167, $p$ =3, $q$ =128。
• 良好安全性：$N$ =251, $p$ =3, $q$ =128。
• 强安全性：$N$ =347, $p$ =3, $q$ =128。
• 卓越安全性：$N$ =503, $p$ =3, $q$ =256。

编码

一系列方法都在 这里。 总体而言，JavaScript 允许代码在浏览器中运行。

带有 JavaScript 的 NIST FIPS 206 (FN-DSA)

我们可以使用许多环度大小来实现 NTRU 方法 [ 这里 ]：

总体而言，我们需要 Falcon-512 的环度为 9，公钥为 1,281 字节，私钥为 897 字节：

然后我们可以使用 [ 这里 ] 实现签名：

我们可以看到签名和验证非常快，并且密文是 666 字节。

结论

Falcon 的性能比 Dilithium 慢，但密钥大小和密文小得多：

Method                           Public key size    Private key size   Signature size  Security level
------------------------------------------------------------------------------------------------------
Crystals Dilithium 2 (Lattice)  1,312            2,528              2,420         1 (128-bit) Lattice
Falcon 512 (Lattice)            897              1,281                666         1 (128-bit) Lattice

参考文献

[1] Kannwischer, M. J., Rijneveld, J., Schwabe, P., & Stoffelen, K. (2019). pqm4: 在 ARM Cortex-M4 上测试和基准测试 NIST PQC

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