36.Weil配对

文档摘要

title: 36. Weil 配对 tags: zk abstract algebra elliptic curve group theory finite field pairing WTF zk 教程第 36 讲：Weil 配对这一讲，我们将介绍 Weil 配对，它在基于配对的加密算法和零知识证明中扮演着重要角色。 Weil 配对 1.1 推导 Weil 配对是一种基于椭圆曲线的双线性配对。我们定义在域 $K$ 上的椭圆曲线 $E(K)$，根据我们之前推导的挠群性质， $m$-挠群 $E[m]$ 同构于 $\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/m\mathbb{Z}$。


title: 36. Weil 配对
tags:
  - zk
  - abstract algebra
  - elliptic curve
  - group theory
  - finite field
  - pairing

WTF zk 教程第 36 讲：Weil 配对

这一讲，我们将介绍 Weil 配对，它在基于配对的加密算法和零知识证明中扮演着重要角色。

1. Weil 配对

1.1 推导

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.2 性质

性质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。

2. Weil 配对常用形式

上一节介绍的 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，同样满足上一节的性质：双线性，非退化性，和交错性。

2.1 例子

下面我们举个 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。

3. 总结

这一讲，我们介绍了 Weil 配对的推导和两种形式。推导比较繁琐，应用时记住结论就可以了。下一讲，我们将介绍计算 Weil 配对的有效算法。