什么是椭圆曲线配对？

配对，尤其是在椭圆曲线的上下文中，已成为重要的加密学构建块。特别是，配对用在流行的零知识证明协议中，能够启用各种应用。它们也是快速聚合 BLS 签名的关键成分。这些签名被以太坊使用，而高效的聚合是扩展到大量验证者的关键。

那么，配对是什么呢？本文是一个两部分系列的第一部分，提供了对配对及其解决的问题的介绍。在第二部分中，我们将研究具体应用，比如 BLS 签名和在某些 ZK 证明系统中使用的 KZG 承诺方案。

我们假设读者对阿贝尔群、有穷域和椭圆曲线等概念有基本的了解。

单向函数

为了逐步构建配对的定义，我们从更基本的加密原语开始。许多加密构造依赖于 单向函数：一个映射 φ:X→Y，简单计算但难以反转。例如，在加密哈希函数的上下文中，这正是前像抵抗的关键属性。

通用示例：阿贝尔群

作为一般示例，假设 G 是一个阶为 n 的循环阿贝尔群，g∈G 为生成元。然后，我们可以考虑映射 φ:Z/nZ→G，该映射由 φ(a+nZ)=a⋅g 定义。如果在 G 中进行加法的计算是快速的，那么 φ 可以高效计算。然而，虽然对于某些示例，φ的逆的计算可以高效完成，但在其他示例中预计是计算上不可解的。计算 φ−1(h) 对于元素 h ∈ G 的问题被称为 离散对数问题。

让我们看一些具体的例子，它们是这个通用形式的实例。

具体示例 1：模 n 的整数

一个简单的例子是单位映射 φ:Z/nZ→Z/nZ，具有 φ(x)=x。在这种情况下，φ 是其自身的逆，因此离散对数问题非常简单。

具体示例 2：模素数的整数的乘法子群

考虑 Z/pZ，即模素数 p 的整数。我们所指的 (Z/pZ)× 是单位的乘法群，这在本例中意味着所有元素不包括 0 + pZ，且具有乘法的群结构。设 g 是 (Z/pZ)× 中具有阶 n 的元素，并让 G=⟨g⟩={g0,g1,…,gn−1} 为由 g 生成的子群。那么，我们可以考虑 φ:Z/nZ→G，由下式给出 φ(a+nZ)=ga。在这种情况下，我们使用 G 的乘法表示法，因此这个例子也可以作为说明为什么计算 φ 的逆的问题称为离散 对数 问题。

具体示例 3：椭圆曲线

让 E 为椭圆曲线上的点作为阿贝尔群，g 是 E 的一个阶为 n 的元素，并且 G 是由 g 生成的 E 的子群。那么，φ:Z/nZ→G，具有 φ(a+nZ)=a⋅g 是一个例子。计算前像的问题被称为 椭圆曲线离散对数问题 (ECDLP)。ECDLP 的计算不可解性是许多基于椭圆曲线的加密系统所作的主要假设。

线性单向函数

我们上面给出的通用示例（以及我们讨论的三个具体实例）具有这样的性质：φ 不仅是集合的映射，而且是阿贝尔群的同态，即 φ 满足 φ(a+b)=φ(a)+φ(b) 和 φ(a,b+b′)=φ(a,b)+φ(a,b′)。这有一个有趣的结果，即我们可以在 Z/nZ 中检查加法关系，即使我们只知道涉及元素在 φ 下的像。具体来说，假设有人拥有一些整数 a、b 和 c，给我们 φ(a), φ(b), 和 φ(c)，并声称 c=a+b。如果计算 φ−1 是计算上不可解的，那么我们将无法恢复 a、b 或 c 以便直接检查这一点。然而，由于 φ 在我们的示例中是单射，当且仅当 φ(c)=φ(a+b) 成立时，c=a+b 成立。由于 φ 是加法的，我们实际上可以计算右侧为 φ(a)+φ(b)。

线性关系

显然我们可以使用更多的加法项重复前面的例子。更一般地，我们可以使用在 φ 下的像来检查每个 线性 关系。如果 c⃗=(c1,…,cm)∈Z×m 是 m 倍数的整数，且 (g1,…,gn) 是一些阿贝尔群的元素，我们可以写出 c⃗⋅(g1,…,gm) 为群元素 ∑i=1mci⋅gi。我们可以将 c⃗⋅− 表示为将 (g1,…,gm) 映射到 c⃗⋅(g1,…,gm) 的映射。然后，主要的观察是 以下图表是交换的。

(Z/nZ)×m→φ×mG×mc⃗⋅−↓↓c⃗⋅−Z/nZ→φG

让我们拆解一下这意味着什么。符号 G×m 指的是 G 的 m 倍笛卡尔积，因此元素是 (g1,…,gm)，其中 gi ∈ G。对应地，符号 φ×n 指的是对每一分量应用 φ 的映射，因此将 (a1,…,am) 的元素的 (Z/nZ)×m 映射到 (φ(x1),…,φ(xm))。该图表是交换的，意味着 φ∘(c⃗⋅−)=(c⃗⋅−)∘φ×n，因此从左上到右下的复合是一样的，无论我们选择哪条路径。

例如，若有人在左上角拥有一个元组 (x1,…,xm)，并声称底左的像 c⃗⋅(x1,…,xm) 等于某个值 y，那么即使我们仅拥有右侧在 φ 下的像 — (φ(x1),…,φ(xm)) 和 φ(y) — 也可以通过检查 c⃗⋅(φ(x1),…,φ(xm))=φ(y) 来验证。

在第三个具体示例（椭圆曲线）中，这样检查线性关系的一个实际例子是 ECDSA 签名验证。

从线性到双线性

如果我们对只检查线性关系感到不满足，该怎么办？下一步是验证二次关系，其中最简单的例子之一是 a⋅b=c。要像之前一样完成这项工作，我们希望有 φ(x⋅y)=φ(x)⋅φ(y)。然而，右侧在一般情况下甚至没有定义，因为 G 只是一个阿贝尔群（而不是环）。例如，将两个椭圆曲线上的点相乘是什么意思？

不过，我们使用交换图表的重新框架可能会帮助我们。注意，实际上我们并不使用底部映射也是图表（1）中的 φ，而只需保证图表是交换的，因此我们最好有如下的交换图表。

Z/nZ×Z/nZ→φ×φG×G(x,y)↦x⋅y↓↓eZ/nZ→ψH

这里，H 是一个阶为 n 的其他循环阿贝尔群，ψ:a+nZ↦a⋅h，h 是 H 的一个生成元，且 e 是某个映射。

实际上，我们甚至不需要顶部的两个 φ 相同，因此只需使用 φ1、φ2 和 φ3，它们都与我们的通用示例相同，以便得到的图表是交换的，其中 e 是某个映射。

如果我们有这个，并且有人声称 c=a⋅b，给我们 φ1(a), φ2(b), 和 φ3(c)，我们可以通过验证是否 e(φ1(a),φ2(b))=φ3(c) 来检查。这项工作能够成功，因为图表的交换性意味着 e(φ1(a),φ2(b))=φ3(a⋅b)，而且 φ3 是单射。

还有一种略微不同的方法可以使用图（2）。假设我们给出的是 φ1(a), φ2(b), 和 φ1(c)，而不是 φ1(a), φ2(b), 和 φ3(c)，那么由于 e(φ1(a),φ2(b))=φ3(a⋅b)且 e(φ1(c),φ2(1))=φ3(c⋅1)=φ3(c)，则可以用来检查 c=a⋅b，只需检查 e(φ1(a),φ2(b))=e(φ1(c),φ2(1))。

配对

现在可以非正式地定义配对为映射 e:G1×G2→G3，它符合像（2）这样的图表。更确切地说，我们定义 配对 为映射 e:G1×G2→G3（其中 G1、G2 和 G3 是阿贝尔群），具有以下性质：

1. 双线性：e(a+a′,b)=e(a,b)+e(a′,b)，以及 e(a,b+b′)=e(a,b)+e(a,b′)。
2. 非退化性：如果 a∈G1 满足其对每个 b∈G2 有 e(a,b)=0，则 a=0。同样地，如果 b∈G2 满足其对每个 a∈G1 有 e(a,b)=0，则 b=0。

术语 双线性 可以用这个条件来解释，即 e 对第一和第二因子分别必须是线性的。

确实，如果我们限制在顺序为 n 的循环阿贝尔群 G1、G2 和 G3，那么非正式的描述与此对应。例如，如果 e 如图（2）所示，则我们可以如下检查第一因子的线性性，使用图表的交换性和 φ1、φ2、φ3 是线性且可逆的事实。

相反，给定一个双线性且非退化的 e:G1×G2→G3，可以通过任何可逆线性映射 φ1 和 φ2 构造一个类似的图表，并将 φ3 定义如下：

φ3(x)≔e(φ1(x),φ2(1))

因为 e 对第一因子是线性的，故 φ3 是可逆的，而图表的交换性来自于 e 对第二因子的线性。

椭圆曲线的配对

我们现在已经讨论了我们希望拥有的 e 的类型，但可用这些映射真的存在吗？请注意，对于加密应用，我们希望 e 适合类似于（2）的图表，其中 e、φ1、φ2 和 φ3 计算效率高，但反转 φ1、φ2 和 φ3 是计算上不可解的，因此我们不能仅仅将乘法映射 Z/pZ×Z/pZ→Z/pZ 作为 e 和身份映射作为 φ1、φ2 和 φ3。

幸运的是，在椭圆曲线的背景下存在可用的配对。然而，我们不会得到类似于 E×E′→G 的配对，其中椭圆曲线 E 和 E' 是定义在 Fp 上的。相反，我们得到的配对看起来像这样：

en:E(Fqk(q,r))[r]×E(Fqk(q,r))[r]→μr

因此，我们将在接下来的几个小节解释所使用的符号。我们将首先解释括号的含义，因此 E(K) 的符号将被定义为 E(K)。接下来我们会定义符号 μr 和 k(q,r)。最后，我们将解释方括号 [r] 的含义。

椭圆曲线的 KKK 点

设 q 为素数的幂，E 为定义在 Fq 上的椭圆曲线。在许多椭圆曲线的应用中，q 是素数，人们仅考虑 E 的 Fq 点，可能也通过滥用符号将其标记为 E。这意味着具体来说，如果 E 例如由某个方程给出如 y2=x3+a⋅x+b (其中 a 和 b 是 Fq 的元素)，那么我们考虑满足此方程的 (x,y) 对，其中 x 和 y 也是 Fq 的元素。

然而，如果 K 是 Fq 的域扩展，那么我们也可以考虑满足该方程的元素 x 和 y。我们将这样的对 (x,y) 称为 E 的 KKK 点，并将 KKK 点的阿贝尔群标记为 E(K)。

现在要解释公式 (3) 中的 E(Fqk(q,r))，我们只缺少 k(q,r) 的定义，接下来我们将定义它。

嵌入次数

假设 E 如前所述，n 是与 q 互质的整数，并且 n 除 |E(Fq)|，即 E 的 Fq Points 的数量。在这种情况下，嵌入次数 是指最小整数 k(q,n)>0，使得 n 除 qk(q,n)−1。几乎总会在上下文中显而易见 q 和 n，只需写 k 即可表示 k(q,n)。

一个重要的替代描述是 k(q,n) 是使所有 n 阶单位根的信息最小整数（这意味着 xn=1 的解）都位于 Fqk 。我们用 μn 来表示 Fqk 内的 n 阶单位根的子集。它可以通过乘法构建成为阿贝尔群的结构，因为如果 x,y∈μn， 则 (xy)n=xnyn=1⋅1=1 和 (x−1)n=(xn)−1=1（x−1）n=(xn)−1=1。

因此，现在我们了解了公式 (3) 中 e 的值域的情况，而要理解值域，剩下的仅是 [r] 的定义。### 扭转点

如果 GGG 是一个阿贝尔群，我们可以考虑满足 n⋅g=0n⋅g = 0n⋅g=0 的 GGG 元素 ggg。这些元素通常称为 nnn-扭转元或指数为 nnn 的元素。GGG 的所有 nnn-扭转元素的集合形成 GGG 的一个子群，有时记作 G[n]G[n]G[n]。

在我们之前的情况中，如果 m≥1m \geq 1m≥1，我们现在可以考虑 E(Fqm)[n]E(\mathbb{F}_{q^m})[n]E(Fqm​)[n] 作为 EEE 的 Fqm\mathbb{F}_{q^m}Fqm​-点中的 nnn-扭转元素。如果 d≥1d \geq 1d≥1，那么 Fqm⊆FqmdF_{q^{m}} \subseteq F_{q^{md}}Fqm​⊆Fqmd​，我们也可以考虑 E(Fqm)E(\mathbb{F}_{q^m})E(Fqm​) 作为 E(Fqmd)E(\mathbb{F}_{q^{md}})E(Fqmd​) 的一个子群，因此 E(Fqm)[n]E(\mathbb{F}_{q^m})[n]E(Fqm​)[n] 作为 E(Fqmd)[n]E(\mathbb{F}_{q^{md}})[n]E(Fqmd​)[n] 的一个子群。现在可以问，替换 mmm 为 md1md_1md1​，然后 md1d2md_1d_2md1​d2​，依此类推时 E(Fqm)[n]E(\mathbb{F}_{q^m})[n]E(Fqm​)[n] 是否会变得越来越大。

然而，答案是否定的。我们可以得到一个最大的阿贝尔群，我们记作 E[n]E[n]E[n]。此外，如果 rrr 是一个不整除 q(q−1)q(q-1)q(q−1) 的质数，那么我们已经有 E(Fqk)[r]=E[r]E(\mathbb{F}_{q^{k}})[r] = E[r]E(Fqk​)[r]=E[r]，其中 k=k(q,r)k=k(q,r)k=k(q,r) 是前一小节中定义的嵌入度。因此，在这种情况下，只需考虑定义椭圆曲线的方程在 Fqk\mathbb{F}_{q^k}Fqk​ 中的解，以捕获 所有 rrr-扭转点。

韦伯尔和塔特配对

我们现在可以引入在椭圆曲线背景下第一个可用的配对，即 韦伯尔 配对。为此，我们设 EEE 是在 Fq\mathbb{F}_qFq​ 上定义的椭圆曲线，并且 nnn 是一个与 qqq 互质的正整数。然后，韦伯尔配对的定义如下。

en:E[n]×E[n]→μne_n: E[n]\times E[n] \to \mu_nen​:E[n]×E[n]→μn​

为了能够实际计算这样的配对，我们使用前一小节的设置：我们考虑一个不整除 q(q−1)q(q-1)q(q−1) 的质数 rrr，而不是一个一般的整数 nnn。然后， ene_nen​ 可以视为 E(Fqk)[r]×E(Fqk)[r]E(\mathbb{F}_{q^k})[r] \times E(\mathbb{F}_{q^k})[r]E(Fqk​)[r]×E(Fqk​)[r] 到 μn\mu_nμn​ 的映射，并且 μn\mu_nμn​ 包含在 Fqk\mathbb{F}_{q^k}Fqk​ 中。

如果嵌入度 k=k(q,r)k=k(q,r)k=k(q,r) 恰好很大，那么需要使用 Fqk\mathbb{F}_{q^k}Fqk​ 的元素当然是很不方便的。那么，我们为什么不能仅限制于 E(Fq)×E(Fq)E(\mathbb{F}_q) \times E(\mathbb{F}_q)E(Fq​)×E(Fq​) 呢？我们仍会得到一个双线性映射，那么我们为何要重视考虑 所有 rrr-扭转？原因是这种限制通常会出现退化，从而无法满足我们的目的。

在这种情况下的另一个经典配对是(修改后的) 塔特配对 (或 塔特-利克腾鲍姆配对)。同样，设 EEE 是在 Fq\mathbb{F}_qFq​ 上定义的椭圆曲线，nnn 是一个正整数。然后，修改后的塔特-利克腾鲍姆配对的定义如下：

τn:E(Fqk)[n]×E(Fqk)/nE(Fqk)→μn\tau_n: E(\mathbb{F}_{q^k})[n] \times E(\mathbb{F}_{q^k})/nE(\mathbb{F}_{q^k}) \to \mu_nτn​:E(Fqk​)[n]×E(Fqk​)/nE(Fqk​)→μn​

其中 k=k(q,n)k=k(q,n)k=k(q,n) 是嵌入度。在这里，符号 E(Fqk)/nE(Fqk)E(\mathbb{F}_{q^k})/nE(\mathbb{F}_{q^k})E(Fqk​)/nE(Fqk​) 意味着我们仅考虑 E(Fqk)E(\mathbb{F}_{q^k})E(Fqk​) 中的元素模 n⋅Pn⋅P 的形式。

实际上，韦伯尔和塔特-利克腾鲍姆配对都可以通过 米勒算法↗ 高效地计算。在实践中，最常用的配对是(最佳) 阿特配对↗。这些是塔特配对的变体，允许更快的计算，并且可以减少在领域中需要处理的扩展域的次数（例如，使其能够使用 Fq2\mathbb{F}_{q^2}Fq2​ 而不是 Fq12\mathbb{F}_{q^{12}}Fq12​），使用扭曲。

从以上内容来看，低嵌入度似乎非常有用，可以通过避免使用更大的域来提高我们选择的配对的计算效率。然而，这也有其反面，我们将在下一节中看到。

MOV 和弗雷-吕克攻击

设 EEE 是在 Fq\mathbb{F}_qFq​ 上定义的椭圆曲线。假设我们给定了 E(Fq)E(\mathbb{F}_q)E(Fq​) 中的两个点 PPP 和 QQQ，使得 PPP 的阶为 rrr 并且存在 m∈Zm\in\mathbb{Z}m∈Z 使得 Q=m⋅PQ = m\cdot PQ=m⋅P。恢复 mmm（模 rrr）从 PPP 和 QQQ 是我们在本文章开始时提到的 ECDLP，其计算困难性对许多基于椭圆曲线的密码系统至关重要。

现在假设 rrr 不整除 q(q−1)q(q-1)q(q−1)，我们可以在 E(Fqk(q,n))E(\mathbb{F}_{q^{k(q, n)}})E(Fqk(q,n)​) 中找到一个点 TTT，使得 TTT 的阶为 rrr 并且 er(P,T)≠1e_r(P, T) \neq 1er​(P,T)=1。根据 ere_rer​ 的双线性性，我们有以下关系。

er(Q,T)=er(m⋅P,T)=er(P,T)me_r(Q, T) = e_r(m\cdot P, T) = e_r(P, T)^mer​(Q,T)=er​(m⋅P,T)=er​(P,T)m

找到 mmm（模 rrr），使得 er(Q,T)=er(P,T)me_r(Q, T) = e_r(P, T)^mer​(Q,T)=er​(P,T)m 正是 Fqk(q,r)×\mathbb{F}_{q^{k(q, r)}}^{\times}Fqk(q,r)×​ 中的 DLP。找到一个满足该假设的 TTT 在实践中是很容易的，因此此方法将原始的 ECDLP 降级为 DLP 在 Fqk(q,r)×\mathbb{F}_{q^{k(q, r)}}^{\times}Fqk(q,r)×​ 中。

刚刚描述的方法被称为 MOV 攻击↗，得名于作者梅内泽斯、冈本和范斯通。弗雷-吕克攻击类似，但使用了塔特配对。

对于 ECDLP 和上述 DLP，目前没有已知的多项式时间解决算法。然而，在 Fqa\mathbb{F}_{q^a}Fqa​ 中解决 DLP 使用 指数微分法算法↗ 的速度比在 E(Fqa)E(\mathbb{F}_{q^a})E(Fqa​) 中使用现有最快泛用算法婴儿步-大步算法↗ 解 ECDLP 的速度更快。这意味着在上述情况下，如果嵌入度 k=k(q,r)k=k(q, r)k=k(q,r) 较小，则 ECDLP 可以比预期更快地解决。

因此，如果我们想利用基于配对的密码学，就必须使用具有精心选择的嵌入度的椭圆曲线——嵌入度应足够大，以确保 ECDLP 的必要安全级别，但在其他情况下应尽可能小，以确保配对能够高效计算。实践中，为了使用配对选择的嵌入度通常在 666 到 242424 之间，121212 是一个流行的选择。

结论

我们定义了配对，并阐明了它们可能的用途，同时也看到了椭圆曲线的配对的形式。

在这篇文章系列的第二部分（也是最后一部分）中，我们将仔细研究配对的密码学应用。特别是，我们将解释 BLS 签名，包括如何聚合它们，这是一个非常有用的属性使以太坊能够扩展到大量验证者↗。我们还将讨论 KZG 多项式承诺，这是用于 ZK 证明系统（如 Halo2）的构建块。

关于我们

Zellic 专注于保护新兴技术。我们的安全研究人员已经发现了从财富 500 强公司到 DeFi 巨头的最有价值目标中的漏洞。

开发者、创始人和投资者信任我们的安全评估，以快速、自信且无关键漏洞地交付。凭借我们在实际 offensive security research（攻防安全研究）中的背景，我们能够发现他人所忽略的内容。

联系我们↗，进行一次优于其他的审计。真正的审计，而非走过场。

末尾注释

1. 我们对密码散列函数需要额外的性质，例如抗碰撞性。但是这些不会在本文其余部分中发挥作用。↩

2. 使用 双倍加法↗ 方法。↩

3. 单元是一个在环中具有乘法逆的元素。↩

4. ggg 的阶为 nnn 意味着 gn=1+qZg^n = 1 + q\mathbb{Z}gn=1+qZ 且 gk≠1+qZg^k \neq 1 + q\mathbb{Z}gk=1+qZ 对于 1≤k<n1 \leq k < n1≤k<n。↩

5. ECDLP 是否可以高效解决特别依赖于曲线 EEE。例如，如果 EEE 是一个 异常 曲线，则存在一个高效算法。↩

6. 我们在此称之为 配对 的内容有时也称为 双线性配对 或 非退化双线性映射。↩

7. 精确地说，这是 Z\ZZ-双线性。↩

8. 我们放宽了 φi\varphi_iφi​ 必须是同构且其定义域必须精确为 Z/nZ\mathbb{Z}/n\mathbb{Z}Z/nZ 的要求。↩

9. 以下描述被简化，例如，忽略了无穷远点。但讨论 射影构造↗ 超出了本文的范围。↩

10. KKK 是 Fq\mathbb{F}_qFq​ 的域扩展意味着 Fq\mathbb{F}_qFq​ 是 KKK 的一个子域（即，具有相同加法和乘法的子集）。就我们的目的而言，我们仅需考虑 K=FqmK=\mathbb{F}_{q^m}K=Fqm​ 当 m≥1m\geq 1m≥1 时。↩

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