| title |
tags |
36. Weil 配对 |
zk |
abstract algebra |
elliptic curve |
group theory |
finite field |
pairing |
|
这一讲，我们将介绍 Weil 配对，它在基于配对的加密算法和零知识证明中扮演着重要角色。
Weil 配对是一种基于椭圆曲线的双线性配对。我们定义在域 $K$ 上的椭圆曲线 $E(K)$，根据我们之前推导的挠群性质， $m$-挠群 $E[m]$ 同构于 $\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/m\mathbb{Z}$。Weil 配对 $e_m(P,Q)$ 将 $E[m]$ 上的两点 $P, Q$ 映射到 $\mu_m$ 上，也就是：
$$
e_m(P,Q): E[m] \times E[m] \to \mu_m
$$
其中 $\mu_m$ 为 $m$ 次单位根群，指所有满足方程 $z^m = 1$ 的元素 $z$ 构成的集合。
对于在椭圆曲线上的有理函数 $f$，我们可以定义它的主除子（椭圆曲线上点的形式和）：
$$
D_f = \text{div}(f) = \sum_{P \in E}{n_P[P]}
$$
根据主除子定理，我们总能找到一个有理函数 $f = f_Q$，它的除子满足：
$$
D_f = \text{div}(f) = m[Q] - m[O]
$$
因为该除子满足 $\text{deg}(D_f) = m - m = 0$ 和 $\text{sum}(D_f) = mQ - mO = O - mO = O$（点 $Q$ 在 $m$-挠群上）。
接下来，我们定义 $[m]$ 次标量乘法映射 $[m]: E \to E$，设 $Q' \in E[m^2]$ 为椭圆曲线上满足 $[m]Q' = Q$ 的点；再定义 $[m]$ 的逆映射 $[m]^*$，在这里它指的是找到那些被 $m$ 倍映射到特定点的所有点，即满足 $Q' = [m]^*Q$ 的点 $Q$。根据主除子定理，我们也总能找到一个有理函数 $g = g_Q$，它的除子满足：
$$
D_g = \text{div}(g) = [m]^* [Q] - [m]^* [O] = \sum_{R \in E[m]}{[Q' + R] - [R]}
$$
表示 $g$ 在所有 $[m]^* Q$ 上都有零点，在所有 $[m]^* O$ 上都有极点。因为 $[m]Q'=Q$，因此 $[m]^* (Q)$ 就是 $Q'$ 加上所有的 $E[m]$ 中的点（ $[m]$ 映射是 $m$-挠群到自身的一个满射）。根据挠群定义， $[m]^*O$ 就是所有 $E[m]$ 中的点。容易知道 $\text{deg}(D_g) = m^2 - m^2 = 0$ 和 $\text{sum}(D_f) = m^2 Q' + \sum_{R \in E[m]}{R - R} = O - m^2O = O$（挠群 $E[m]$ 共有 $m^2$ 个元素）。
我们容易验证 $f \circ [m]$ 和 $g^m$ 有相同的除子。其中 $f \circ [m] = f([m]Q)$，相当于在每个点 $Q$ 上应用 $f$ 前，先将 $Q$ 变换成它的 $m$ 倍点 $[m]P$，因此 $f \circ [m]$ 在所有 $[m]^*Q$ 上都有零点，每个零点重数为 $m$；在所有 $[m]^*O$ 上都有极点，每个极点重数也为 $m$。对于 $g^m$，它的零点和极点与 $g$ 的位置相同，只不过重数乘以 $m$。因此有 $\text{div}(f \circ [m])=\text{div}(g^m)$。根据除子的唯一性定理，函数 $f \circ [m]$ 和 $g^m$ 成常数比例，我们不妨设：
$$
f \circ [m] = g^m
$$
现在，让我们假设挠群 $E[m]$ 上的另一点 $P$，有 $[m]P = O$，那么对于椭圆曲线上任意一点 $X$，有：
$$
g(X+P)^m = f([m]X + [m]P) = f([m]X) = g(X)^m
$$
也就是说 $g^m$ 在点 $X$ 和 $X+P$ 处有相同的值。我们可以定义一个新的函数 $e_m(P, Q) = \frac{g_Q(X+P)}{g_Q(X)}$，根据上面的等式，有 $e_m(P, Q)^m = 1$，因此 $e_m(P, Q) \in \mu_m$ 是 $m$ 次单位根之一，是有限的。另外根据代数几何的态射性质（不在本教程覆盖范围内）， $e_m(P, Q)$ 是个常数，与点 $X$ 的选取无关。
这个 $e_m(P,Q)$ 就是 Weil 配对，现在我们给出它的定义：Weil 配对 $e_m$ 将椭圆曲线 $m$-挠群上的两个点 $P, Q$ 映射到 $m$ 次单位根上：
$$
e_m: E[m] \times E[m] \to \mu_m
$$
它的具体形式：
$$
e_m(P, Q) = \frac{g_Q(X+P)}{g_Q(X)}
$$
其中 $X$ 是椭圆曲线 $E$ 上的可以使得 $g_Q(X+P)$ 和 $g_Q(X)$ 定义良好且非零的点。
性质1. 双线性： 对于 $E[m]$ 上的挠点 $P, Q, R$，满足 $e_m(P + R, Q) = e_m(P, Q) e_m(R, Q)$ 和 $e_m(P, Q + R) = e_m(P, Q) e_m(P, Q)$。
点我展开证明👀
证明 $e_m(P + R, Q) = e_m(P, Q) e_m(R, Q)$
根据 Weil 配对定义：
$$
e_m(P + R, Q) = \frac{g_Q(X+P + R)}{g_Q(X)}
$$
$$
= \frac{g_Q(X+P + R)}{g_Q(X+P)} \frac{g_Q(X+P)}{g_Q(X)}
$$
令 $X+P = Y$，原式：
$$
= \frac{g_Q(Y + R)}{g_Q(Y)} \frac{g_Q(X+P)}{g_Q(X)}
$$
$$
= e_m(R, Q) e_m(P, Q)
$$
证毕。
证明 $e_m(P, Q + R) = e_m(P, Q) e_m(P, R)$
这个证明相对困难，需要用到除子理论的相关内容。首先，我们先设 $f_Q, f_R, f_S, g_Q, g_R, g_S$ 分别是点 $Q, R, S= Q+R$ 的函数。然后我们设椭圆曲线上的函数 $h$ 满足：
$$
\text{div}(h) = (Q+R) - (Q) - (R) + (O)
$$
根据除子定理，有：
$$
\text{div}(\frac{f_S}{f_Qf_R}) = m \text{div}(h)
$$
因此 $f_S = c f_Q f_R h^m$，其中 $c$ 是常数。又因为 $f_i \circ [m] = g_i^m$，我们将上式两边复合上 $[m]$，得到：
$$
g_S = c'g_Qg_R(h \circ [m])
$$
因此：
$$
e_m(P, Q+R) = \frac{g_S(X + P)}{g_S(X)} = \frac{g_Q(X+P)g_R(X+P)h([m]X + [m]P)}{g_Q(X)g_R(X)h([m]X)}
$$
又因为 $[m]P = O$，因此原式：
$$
= \frac{g_Q(X+P)g_R(X+P)}{g_Q(X)g_R(X)} = e_m(P, Q) e_m(P,R)
$$
证毕。
性质2. 非退化性： 若对于所有的 $P \in E[m]$，有 $e_m(P,Q) = 1$ 成立，那么 $Q = O$。
性质3. 交错性： $e_m(P, Q) = e_m(Q, P)^{-1}$，且 $e_m(P, P) = 1$。
上一节介绍的 Weil 配对中的 $g$ 函数非常难求，因此我们经常用另一种形式：
$$
e_m(P, Q) = \frac{f_P(Q+X)}{f_P(X)} / \frac{f_Q(P-X)}{f_Q(-X)}
$$
其中点 $P, Q$ 属于椭圆曲线的 $m$-挠群 $E[m]$，点 $X$ 为椭圆曲线上满足 $X \notin \set{O, P, -Q, P-Q}$ 的任意一点，函数 $f_P$ 和 $f_Q$ 为定义在椭圆曲线上的有理函数，满足：
$$
\text{div}(f_P) = m[P] - m[O]
$$
$$
\text{div}(f_Q) = m[Q] - m[O]
$$
这个形式的 Weil 配对 $e_m(P, Q) \in \mu_m$，同样满足上一节的性质：双线性，非退化性，和交错性。
下面我们举个 Weil 配对的例子。我们设定义在 $F_5$ 上的椭圆曲 $E: y^2 = x^3 - x \pmod{5}$。它有3个根 $\alpha_1, \alpha_2, \alpha_3$，分别为 $0, -1, 1$，对应椭圆曲线上的3个点 $P_1(0,0), P_2(-1,0), P_3(1,0)$。由于他们满足 $2P_1 = 2P_2 = 2P_3 = O$，因此它们加上无穷远点 $O$ 构成了椭圆曲线的 $2$-挠群 $E[2] = \set{P_1, P_2, P_3, O}$。对于点 $P_i$，我们可以定义有理函数 $f_{Pi} = x - \alpha_i$，对应的主除子满足：
$$
\text{div}(f_{Pi}) = 2[P_i] - 2[O]
$$
我们取 $P_1, P_3$ 和椭圆曲线上的另一点 $X = (2,1)$ 来计算 Weil 配对：
$$
e_2(P_1, P_3) = \frac{f_1(P_3+X)}{f_1(X)} / \frac{f_3(P_1-X)}{f_3(-X)}
$$
其中 $P_3 + X = (3,3)$, $P1 - X = (2, 1)$, $-X = (2, 4)$, $f_1(P_3+X) = 3$, $f_1(X)= 2$, $f_3(P-X) = 1$, $f_3(-X) = 1$。因此 Weil 配对：
$$
e_2(P_1, P_3) = \frac{3}{2} / \frac{1}{1} = 3 * 3 = -1 \pmod 5
$$
可以看到， $e_2(P_1, P_3) = -1 \in \mu_2$。
这一讲，我们介绍了 Weil 配对的推导和两种形式。推导比较繁琐，应用时记住结论就可以了。下一讲，我们将介绍计算 Weil 配对的有效算法。