readme.md

title	tags
39. 扩域上的 Weil 配对	zk abstract algebra elliptic curve group theory finite field pairing

WTF zk 教程第 39 讲：扩域上的 Weil 配对

这一讲，我们将介绍扩域上的 Weil 配对，主要涉及两个概念：嵌入度和MOV算法，它们会让你更深入的理解双线性配对和椭圆曲线。

1. 嵌入度

在构造配对的时候，我们需要使用挠群，它有个很重要的性质：对于椭圆曲线 $E({\mathbb{F}}_p)$，若 $m$ 与 $p$ 互质，那么存在正整数 $k$，使得

$$E({\mathbb{F}}_{p^k})[m]\cong \mathbb{Z}/m\mathbb{Z}\times \mathbb{Z}/m\mathbb{Z}$$

成立。也就是说，我们必须找到 $k$ 才能构造配对。而嵌入度就是满足上述条件的最小 $k$ 值。

1.1 计算嵌入度

假设椭圆曲线 $E({\mathbb{F}}_p)$ 的阶为 $n$，设 $m$ 为 $n$ 的质因子。对于 $E({\mathbb{F}}_p)$ 上的 $m$-挠群来说，嵌入度是最小的正整数 $k$，使得群的阶 $m$ 整除 $p^k-1$，也就是：

$$m|(p^k-1)$$

根据费马小定理，有 $p^{m-1}\equiv 1(\mathrm{mod}m)$ 成立。因此对于任意曲线和任意 $m$ 值，嵌入度都存在。同时，由于 $m$ 的取值决定了嵌入度，我们将它记为 $k(m)$。

1.2 例子

让我们以椭圆曲线 $E({\mathbb{F}}_{19})$ 为例，方程为 $y^2=x^3-x+1$。椭圆曲线上共有 22 个元素，也就是阶 $n=22$。我们取 22 最大的质因数 $m=11$，计算椭圆曲线 $11$-挠群，它有 $11$ 个点。很明显， $E({\mathbb{F}}_{19})[11]$ 不同构于 $\mathbb{Z}/11\mathbb{Z}\times \mathbb{Z}/11\mathbb{Z}$，因为前者的阶为 11，而后者的阶为 121。

下面我们来计算嵌入度 $k(11)$：

$$({19}^1-1)÷11=7(\mathrm{mod}19)$$

$$({19}^2-1)÷11=8(\mathrm{mod}19)$$

$$({19}^3-1)÷11=5(\mathrm{mod}19)$$

$$({19}^4-1)÷11=3(\mathrm{mod}19)$$

$$({19}^5-1)÷11=9(\mathrm{mod}19)$$

$$({19}^6-1)÷11=2(\mathrm{mod}19)$$

$$({19}^7-1)÷11=1(\mathrm{mod}19)$$

$$({19}^8-1)÷11=4(\mathrm{mod}19)$$

$$({19}^9-1)÷11=6(\mathrm{mod}19)$$

$$({19}^{10}-1)÷11=0(\mathrm{mod}19)$$

因此，椭圆曲线 $E({\mathbb{F}}_{19})$ 对于 $m=11$ 的嵌入度 $k(11)=10$。也就是说， $E({\mathbb{F}}_{{19}^{10}})[11]$ 同构于 $\mathbb{Z}/11\mathbb{Z}\times \mathbb{Z}/11\mathbb{Z}$，可以用于配对。

2. MOV 算法

MOV 算法是一种将椭圆曲线上的离散对数问题（ECDLP）转换为有限域上的离散对数问题（DLP）的算法，目的是利用在有限域上离散对数问题相对较容易解决的特性，来攻击更难解决的椭圆曲线上的离散对数问题。

MOV 算法的核心思想是利用椭圆曲线的配对，将椭圆曲线上的离散对数问题 $Q=xP$ 转换为有限域 $F_{p^k}^{\ast }$ 上的离散对数问题 $e(Q,T^{\prime })=e(P,T^{\prime }{)}^x$，从而解决它。

2.1 算法步骤

给定椭圆曲线 $E(F_p)$ 上的基点 $P$ 和点 $Q=xP$，目的是求出 $x$。

1. 计算点群的秩： 计算椭圆曲线 $E(F_p)$ 上点群元素的数量 $N$。
2. 计算点的阶：计算点 $P$ 的阶 $m$，其中 $m|N$。由于 $Q=xP$，那么 $Q$ 的阶也是 $m$。
3. 计算嵌入度：找到满足 $m|(p^k-1)$ 的最小正整数 $k$，即嵌入度。
4. 选择点T和T'：选择一个随机点 $T\in F_{p^k}$ 但 $T\notin F_p$。在计算点 $T^{\prime }=(N/m)T$，其中 $T^{\prime }$ 的阶诶 $m$。
5. 构造配对：使用 Weil 配对（或 Tate 配对），在椭圆曲线 $E({\mathbb{F}}_{p^k})$ 上构造一个双线性映射 $e:E[m]\times E[m]\to {\mathbb{F}}_{p^k}^{\ast }$。
6. 转换问题：计算配对

$$\alpha =e_m(P,T^{\prime })\in {\mathbb{F}}_{p^k}^{\ast }$$

$$\beta =e_m(Q,T^{\prime })\in {\mathbb{F}}_{p^k}^{\ast }$$

7. 解决DLP：解决 ${\mathbb{F}}_{p^k}^{\ast }$ 上的 DLP 问题 $\beta ={\alpha }^x$
8. 解决ECDLP：根据双线性，上一步得到的 $x$ 就是 $Q=xP$ 的解。因为 $\beta =e_m(Q,T^{\prime })=e_m(xP,T^{\prime })=e_m(P,T^{\prime }{)}^x={\alpha }^x$。

2.2 安全性影响

MOV 算法表明，如果椭圆曲线的嵌入度 $k$ 较小，则椭圆曲线上的离散对数问题的安全性会受到威胁。因为在有限域 ${\mathbb{F}}_{p^k}$ 上的离散对数问题可能通过索引计算法更高效的解决。因此，为了保证椭圆曲线密码体系的安全性，通常会选择具有较大嵌入度的椭圆曲线。

但是，如果椭圆曲线的嵌入度 $k$ 较大，那么计算配对时使用的 $E({\mathbb{F}}_{p^k})$ 会很大，计算效率非常低。因此在实际使用时，我们要在抵抗 MOV 攻击的情况下选择尽量小的嵌入度。以太坊用来配对的两条椭圆曲线 alt_bn128 和 bls12_381 的嵌入度都是 $12$，可以兼顾安全和配对效率。

3. 总结

这一讲，我们探讨了扩域上的 Weil 配对及相关概念。嵌入度是一个重要的参数，它指定了可以实现Weil配对的扩域，从而影响椭圆曲线应用的安全性和效率。MOV 算法是一种利用较低嵌入度的椭圆曲线的弱点，将椭圆曲线上的离散对数问题（ECDLP）转化为相对容易解决的有限域上的离散对数问题（DLP）。在选择椭圆曲线时，我们要兼顾安全性和配对效率，选择嵌入度适中的椭圆曲线。