title
tags
39. 扩域上的 Weil 配对
zk
abstract algebra
elliptic curve
group theory
finite field
pairing
WTF zk 教程第 39 讲：扩域上的 Weil 配对 这一讲，我们将介绍扩域上的 Weil 配对，主要涉及两个概念：嵌入度和MOV算法，它们会让你更深入的理解双线性配对和椭圆曲线。
在构造配对的时候，我们需要使用挠群，它有个很重要的性质：对于椭圆曲线 $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$ 值。
假设椭圆曲线 $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 \pmod{m}$ 成立。因此对于任意曲线和任意 $m$ 值，嵌入度都存在。同时，由于 $m$ 的取值决定了嵌入度，我们将它记为 $k(m)$ 。
让我们以椭圆曲线 $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) \div 11 = 7 \pmod{19}
$$
$$
(19^2 -1) \div 11 = 8 \pmod{19}
$$
$$
(19^3 -1) \div 11 = 5 \pmod{19} \\
$$
$$
(19^4 -1) \div 11 = 3 \pmod{19} \\
$$
$$
(19^5 -1) \div 11 = 9 \pmod{19} \\
$$
$$
(19^6 -1) \div 11 = 2 \pmod{19} \\
$$
$$
(19^7 -1) \div 11 = 1 \pmod{19} \\
$$
$$
(19^8 -1) \div 11 = 4 \pmod{19} \\
$$
$$
(19^9 -1) \div 11 = 6 \pmod{19} \\
$$
$$
(19^{10} -1) \div 11 = 0 \pmod{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}$ ，可以用于配对。
MOV 算法是一种将椭圆曲线上的离散对数问题（ECDLP）转换为有限域上的离散对数问题（DLP）的算法，目的是利用在有限域上离散对数问题相对较容易解决的特性，来攻击更难解决的椭圆曲线上的离散对数问题。
MOV 算法的核心思想是利用椭圆曲线的配对，将椭圆曲线上的离散对数问题 $Q = xP$ 转换为有限域 $F_{p^k}^*$ 上的离散对数问题 $e(Q, T') = e(P,T')^x$ ，从而解决它。
给定椭圆曲线 $E(F_p)$ 上的基点 $P$ 和点 $Q = xP$ ，目的是求出 $x$ 。
计算点群的秩 ： 计算椭圆曲线 $E(F_p)$ 上点群元素的数量 $N$ 。
计算点的阶 ：计算点 $P$ 的阶 $m$ ，其中 $m | N$ 。由于 $Q = xP$ ，那么 $Q$ 的阶也是 $m$ 。
计算嵌入度 ：找到满足 $m | (p^k - 1)$ 的最小正整数 $k$ ，即嵌入度。
选择点T和T' ：选择一个随机点 $T \in F_{p^k}$ 但 $T \notin F_{p}$ 。在计算点 $T' = (N/m)T$ ，其中 $T'$ 的阶诶 $m$ 。
构造配对 ：使用 Weil 配对（或 Tate 配对），在椭圆曲线 $E(\mathbb{F}_ {p^k})$ 上构造一个双线性映射 $e: E[m] \times E[m] \rightarrow \mathbb{F}_{p^k}^*$ 。
转换问题 ：计算配对
$$
\alpha = e_m(P, T') \in \mathbb{F}_{p^k}^*
$$
$$
\beta = e_m(Q, T') \in \mathbb{F}_{p^k}^*
$$
解决DLP ：解决 $\mathbb{F}_{p^k}^*$ 上的 DLP 问题 $\beta = \alpha^x$
解决ECDLP ：根据双线性，上一步得到的 $x$ 就是 $Q = xP$ 的解。因为 $\beta = e_m(Q, T') = e_m(xP, T') = e_m(P, T')^x = \alpha ^x$ 。
MOV 算法表明，如果椭圆曲线的嵌入度 $k$ 较小，则椭圆曲线上的离散对数问题的安全性会受到威胁。因为在有限域 $\mathbb{F}_{p^k}$ 上的离散对数问题可能通过索引计算法更高效的解决。因此，为了保证椭圆曲线密码体系的安全性，通常会选择具有较大嵌入度的椭圆曲线。
但是，如果椭圆曲线的嵌入度 $k$ 较大，那么计算配对时使用的 $E(\mathbb{F}_{p^k})$ 会很大，计算效率非常低。因此在实际使用时，我们要在抵抗 MOV 攻击的情况下选择尽量小的嵌入度。以太坊用来配对的两条椭圆曲线 alt_bn128 和 bls12_381 的嵌入度都是 $12$ ，可以兼顾安全和配对效率。
这一讲，我们探讨了扩域上的 Weil 配对及相关概念。嵌入度是一个重要的参数，它指定了可以实现Weil配对的扩域，从而影响椭圆曲线应用的安全性和效率。MOV 算法是一种利用较低嵌入度的椭圆曲线的弱点，将椭圆曲线上的离散对数问题（ECDLP）转化为相对容易解决的有限域上的离散对数问题（DLP）。在选择椭圆曲线时，我们要兼顾安全性和配对效率，选择嵌入度适中的椭圆曲线。