什么是椭圆曲线配对？

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

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

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

单向函数

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

通用示例：阿贝尔群

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

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

具体示例 1：模 n 的整数

一个简单的例子是单位映射 $\varphi: \mathbb{Z}/n\mathbb{Z} \rightarrow \mathbb{Z}/n\mathbb{Z}$，具有 $\varphi(x) = x$。在这种情况下，$\varphi$ 是其自身的逆，因此离散对数问题非常简单。

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

考虑 $\mathbb{Z}/p\mathbb{Z}$，即模素数 $p$ 的整数。我们所指的 $(\mathbb{Z}/p\mathbb{Z})^{\times}$ 是单位的乘法群，这在本例中意味着所有元素不包括 $0 + p\mathbb{Z}$，且具有乘法的群结构。设 $g$ 是 $(\mathbb{Z}/p\mathbb{Z})^{\times}$ 中具有阶 $n$ 的元素，并让 $G = \langle g \rangle = {g^0, g^1, \dots, g^{n-1}}$ 为由 $g$ 生成的子群。那么，我们可以考虑 $\varphi: \mathbb{Z}/n\mathbb{Z} \rightarrow G$，由下式给出 $\varphi(a + n\mathbb{Z}) = g^a$。在这种情况下，我们使用 $G$ 的乘法表示法，因此这个例子也可以作为说明为什么计算 $\varphi$ 的逆的问题称为离散 对数 问题。

具体示例 3：椭圆曲线

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

线性单向函数

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

线性关系

显然我们可以使用更多的加法项重复前面的例子。更一般地，我们可以使用在 $\varphi$ 下的像来检查每个 线性 关系。如果 $\vec{c} = (c_1, \dots, c_m) \in \mathbb{Z}^{\times m}$ 是 $m$ 倍数的整数，且 $(g_1, \dots, g_n)$ 是一些阿贝尔群的元素，我们可以写出 $\vec{c} \cdot (g_1, \dots, gm)$ 为群元素 $\sum{i=1}^{m} c_i \cdot g_i$。我们可以将 $\vec{c} \cdot -$ 表示为将 $(g_1, \dots, g_m)$ 映射到 $\vec{c} \cdot (g_1, \dots, g_m)$ 的映射。然后，主要的观察是 以下图表是交换的。

$$ \begin{array}{ccc} (\mathbb{Z}/n\mathbb{Z})^{\times m} & \xrightarrow{\varphi^{\times m}} & G^{\times m} \ \downarrow{\vec{c} \cdot -} & & \downarrow{\vec{c} \cdot -} \ \mathbb{Z}/n\mathbb{Z} & \xrightarrow{\varphi} & G \end{array} $$

让我们拆解一下这意味着什么。符号 $G^{\times m}$ 指的是 $G$ 的 $m$ 倍笛卡尔积，因此元素是 $(g_1, \dots, g_m)$，其中 $g_i \in G$。对应地，符号 $\varphi^{\times n}$ 指的是对每一分量应用 $\varphi$ 的映射，因此将 $(a_1, \dots, a_m)$ 的元素的 $(\mathbb{Z}/n\mathbb{Z})^{\times m}$ 映射到 $(\varphi(x_1), \dots, \varphi(x_m))$。该图表是交换的，意味着 $\varphi \circ (\vec{c} \cdot -) = (\vec{c} \cdot -) \circ \varphi^{\times n}$，因此从左上到右下的复合是一样的，无论我们选择哪条路径。

例如，若有人在左上角拥有一个元组 $(x_1, \dots, x_m)$，并声称底左的像 $\vec{c} \cdot (x_1, \dots, x_m)$ 等于某个值 $y$，那么即使我们仅拥有右侧在 $\varphi$ 下的像 — $(\varphi(x_1), \dots, \varphi(x_m))$ 和 $\varphi(y)$ — 也可以通过检查 $\vec{c} \cdot (\varphi(x_1), \dots, \varphi(x_m)) = \varphi(y)$ 来验证。

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

从线性到双线性

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

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

$$ \begin{array}{ccc} \mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z} & \xrightarrow{\varphi \times \varphi} & G \times G \ (x, y) \mapsto x \cdot y \downarrow & & \downarrow e \ \mathbb{Z}/n\mathbb{Z} & \xrightarrow{\psi} & H \end{array} $$

这里，$H$ 是一个阶为 $n$ 的其他循环阿贝尔群，$\psi: a + n\mathbb{Z} \mapsto a \cdot h$，$h$ 是 $H$ 的一个生成元，且 $e$ 是某个映射。

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

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

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

配对

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

1. 双线性：$e(a+a', b) = e(a, b) + e(a', b)$，以及 $e(a, b+b') = e(a, b) + e(a, b')$。
2. 非退化性：如果 $a \in G_1$ 满足其对每个 $b \in G_2$ 有 $e(a, b) = 0$，则 $a = 0$。同样地，如果 $b \in G_2$ 满足其对每个 $a \in G_1$ 有 $e(a, b) = 0$，则 $b = 0$。

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

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

相反，给定一个双线性且非退化的 $e: G_1 \times G_2 \rightarrow G_3$，可以通过任何可逆线性映射 $\varphi_1$ 和 $\varphi_2$ 构造一个类似的图表，并将 $\varphi_3$ 定义如下：

$\varphi_3(x) \coloneqq e(\varphi_1(x), \varphi_2(1))$

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

椭圆曲线的配对

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

幸运的是，在椭圆曲线的背景下存在可用的配对。然而，我们不会得到类似于 $E \times E' \rightarrow G$ 的配对，其中椭圆曲线 $E$ 和 $E'$ 是定义在 $\mathbb{F}_p$ 上的。相反，我们得到的配对看起来像这样：

$$en: E(\mathbb{F}{q^{k(q,r)}})[r] \times E(\mathbb{F}_{q^{k(q,r)}})[r] \rightarrow \mu_r$$

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

椭圆曲线的 KKK 点

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

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

现在要解释公式 (3) 中的 $E(\mathbb{F}_{q^{k(q,r)}})$，我们只缺少 $k(q,r)$ 的定义，接下来我们将定义它。

嵌入次数

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

一个重要的替代描述是 $k(q,n)$ 是使所有 n 阶单位根的信息最小整数（这意味着 $x^n=1$ 的解）都位于 $F_{q^k}$ 。我们用 $\mun$ 来表示 $F{q^k}$ 内的 n 阶单位根的子集。它可以通过乘法构建成为阿贝尔群的结构，因为如果 $x,y\in\mu_n$， 则 $(xy)^n=x^ny^n=1\cdot1=1$ 和 $(x^{-1})^n=(x^n)^{-1}=1$。

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

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

在我们之前的情况中，如果 $m\geq 1$，我们现在可以考虑 $E(F{q^m})[n]$ 作为 $E$ 的 $F{q^m}$-点中的 $n$-扭转元素。如果 $d\geq 1$，那么 $F{q^{m}} \subseteq F{q^{md}}$，我们也可以考虑 $E(F{q^m})$ 作为 $E(F{q^{md}})$ 的一个子群，因此 $E(F{q^m})[n]$ 作为 $E(F{q^{md}})[n]$ 的一个子群。现在可以问，替换 $m$ 为 $md_1$，然后 $md_1d2$，依此类推时 $E(F{q^m})[n]$ 是否会变得越来越大。

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

韦伯尔和塔特配对

我们现在可以引入在椭圆曲线背景下第一个可用的配对，即 韦伯尔 配对。为此，我们设 $E$ 是在 $F_q$ 上定义的椭圆曲线，并且 $n$ 是一个与 $q$ 互质的正整数。然后，韦伯尔配对的定义如下。

$e_n: E[n]\times E[n] \to \mu_n$

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

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

在这种情况下的另一个经典配对是(修改后的) 塔特配对 (或 塔特-利克腾鲍姆配对)。同样，设 $E$ 是在 $F_q$ 上定义的椭圆曲线，$n$ 是一个正整数。然后，修改后的塔特-利克腾鲍姆配对的定义如下：

$\taun: E(F{q^k})[n] \times E(F{q^k})/nE(F{q^k}) \to \mu_n$

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

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

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

MOV 和弗雷-吕克攻击

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

现在假设 $r$ 不整除 $q(q-1)$，我们可以在 $E(F_{q^{k(q, n)}})$ 中找到一个点 $T$，使得 $T$ 的阶为 $r$ 并且 $e_r(P, T) \neq 1$。根据 $e_r$ 的双线性性，我们有以下关系。

$e_r(Q, T) = e_r(m\cdot P, T) = e_r(P, T)^m$

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

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

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

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

结论

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

在这篇文章系列的第二部分（也是最后一部分）中，我们将仔细研究配对的密码学应用。特别是，我们将解释 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 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～