Skip to content

Latest commit

 

History

History
174 lines (120 loc) · 5.59 KB

readme.md

File metadata and controls

174 lines (120 loc) · 5.59 KB
title tags
37. Miller 算法
zk
abstract algebra
elliptic curve
group theory
finite field
pairing

WTF zk 教程第 37 讲:Miller 算法

这一讲,我们介绍 Miller 算法,它可以高效计算椭圆曲线上的配对。

1. Miller 算法

首先我们回顾下 Weil 配对,它将椭圆曲线 $m$-挠群上的两个点 $P, Q$ 映射到 $m$ 次单位根上:

$$ e_m: E[m] \times E[m] \to \mu_m $$

它的具体形式:

$$ e_m(P, Q) = \frac{f_P(Q+X)}{f_P(X)} / \frac{f_Q(P-X)}{f_Q(-X)} $$

其中,函数 $f_P$$f_Q$ 为定义在椭圆曲线上的有理函数,满足:

$$ \text{div}(f_P) = m[P] - m[O] $$

$$ \text{div}(f_Q) = m[Q] - m[O] $$

1.1 算法步骤

Miller 算法就求解函数 $f_P$ 的高效算法,你可以把它理解为计算配对的 Double-And-Add 算法,对于乘数 $m$,它的计算复杂度是 $O(\log{m})$。具体步骤:

  1. 初始 $T = P$$f = 1$
  2. $i = t - 1$ 循环至 0
    • $f = f^2 \cdot h_{T,T}$
    • $T = 2T$
    • 如果 $\varepsilon_i = 1$
      • $f = f \cdot h_{T,P}$
      • $T = T + P$
  3. 结束循环
  4. 返回 $f$ 的值

最后返回的函数 $f$ 的除子满足以下形式:

$$ \text{div}(f_P) = m[P] - [mP] - (m-1)[O] $$

$P$$m$-挠点时,有 $mP = O$,因此除子变为 $\text{div}(f_P) = m[P] - (m)[O]$,符合 Weil 配对中的形式。

1.2 证明

首先,我们定义一个和椭圆曲线交与 $P, Q, -P-Q$ 三点的直线 $y = \lambda x + \mu$

定义在椭圆曲线上的有理函数 $y-\lambda x - \mu$$P, Q, -P-Q$ 有三个零点,重数均为1;在无穷远点 $O$ 有一个极点,重数为3。它的除子满足:

$$ \text{div}(y-\lambda x - \mu) = [P] + [Q] + [- P - Q] - 3[O] $$

另外,有理函数 $x-x_{P+Q}$$P+Q$$-P-Q$ 有两个零点(它们的横坐标相等),重数均为1;在无穷远点 $O$ 有一个极点,重数为2。它的除子满足:

$$ \text{div}(x-x_{P+Q}) = [P+Q] + [- P - Q] - 2[O] $$

我们可以构造上面两个有理函数的商 $h_{P, Q} = \frac{y-\lambda x - \mu}{x-x_{P+Q}}$,它同样是个有理函数,并且它的除子满足(上面两个除子相减):

$$ \text{div}(h_{P, Q}) = [P] + [Q] - [- P - Q] - [O] $$

特别的,当直线斜率 $\lambda = \infty$ 时,有 $P + Q = O$,我们设 $g_{P,Q} = x - x_P$,它的除子为:

$$ \text{div}(h_{P, Q}) = [P] + [-P] - 2[O] $$

接下来,我们将 $m$ 展开为二进制形式

$m = \varepsilon_0 + \varepsilon_1 \cdot 2 + \varepsilon_2 \cdot 2^2 + \ldots + \varepsilon_t \cdot 2^t$

其中 $\varepsilon_i \in {0, 1}$$\varepsilon_t \neq 0$

通过简单的(并不)归纳法,我们就能证明 Miller 算法输出的 $f$ 满足

$$ \text{div}(f_P) = m[P] - [mP] - (m-1)[O] $$

2. 例子

下面我们举个稍微复杂的 Weil 配对的例子,过程使用 Sage 计算,内置了 Miller 算法。Sage(也称为SageMath)是一个开源的数学软件系统,旨在提供一个强大、全面的环境,用于解决各种数学问题和进行数学研究。它的语法与python类似,你可以使用 SageMathCell 在浏览器中运行 Sage 程序。

设定义在 $F_{631}$ 上的椭圆曲 $E: y^2 = x^3 + 30x + 34 \pmod{631}$。椭圆曲线上共有 650 个点,可以被分解为 $2 \cdot 5^2 \cdot 13$。它的 $5$-挠群 $E[5]$ 上共有 25 个点,我们在其中取点 $P(36, 60)$$Q(121, 387)$,它们都是 $E[5]$ 的生成元。然后我们用 Sage 计算它们的 Weil 配对:

$$ e_m(P, Q) = 242 $$

它满足 $242 \in \mu_5$,因为 $242^5 = 1 \pmod{631}$

代码如下:

p = 631
a = 30
b = 34
E = EllipticCurve(GF(p), [a, b])
print(E)
print("椭圆曲线中的元素个数: ", E.cardinality())

# 获取5-挠群的点
INF = E[0]
L_E_5 = INF.division_points(5)  # [11]P == INF
E_5 = Set(L_E_5)  # $5$-torsion
print("5-torsion points: ", E_5)
print("5-挠群中的元素个数: ", E_5.cardinality())

P = E([36,60])
Q = E([121,387])

weil_P_Q = P.weil_pairing(Q, 5)
print("5-挠群中点", P, "和", Q, "的Weil配对为", weil_P_Q)

# 输出
# Elliptic Curve defined by y^2 = x^3 + 30*x + 34 over Finite Field of size 631
# 椭圆曲线中的元素个数:  650
# 5-torsion points:  {(121 : 244 : 1), (121 : 387 : 1), (420 : 48 : 1), (0 : 1 : 0), (531 : 613 : 1), (36 : 60 : 1), (586 : 584 : 1), (428 : 25 : 1), (586 : 47 : 1), (339 : 132 : 1), (289 : 362 : 1), (575 : 7 : 1), (511 : 23 : 1), (511 : 608 : 1), (617 : 626 : 1), (575 : 624 : 1), (595 : 221 : 1), (617 : 5 : 1), (595 : 410 : 1), (36 : 571 : 1), (531 : 18 : 1), (339 : 499 : 1), (289 : 269 : 1), (428 : 606 : 1), (420 : 583 : 1)}
# 5-挠群中的元素个数:  25
# 5-挠群中点 (36 : 60 : 1) 和 (121 : 387 : 1) 的Weil配对为 242

接下来,我们计算 $R = 3P = (617, 5)$$S = 4Q = (121, 144)$ 之间的配对:

$$ e_m(R, S) = 512 $$

因为 Weil 配对满足双线性,那么应该有 $e_m(R, S) = e_m(3P, 4Q) = e_m(P,Q)^{12}$。验证一下 $242^{12} = 512 \pmod{631}$,的确成立。

因此,使用 Weil 配对,我们可以用 $e_m(P, Q)^{12} = e_m(3P,4P)$ 来验证 $3 * 4 = 12$

代码如下:

R = 3 * P
S = 4 * Q

weil_R_S = R.weil_pairing(S, 5)
print("5-挠群中点", R, "和", S, "的Weil配对为", weil_R_S)

print("因为 R= 3P, S = 4Q,因此 weil_P_Q ^ 12  = ",  weil_P_Q^12 , "和 weil_R_S 相等")

# 5-挠群中点 (617 : 5 : 1) 和 (121 : 244 : 1) 的Weil配对为 512
# 因为 R= 3P, S = 4Q,因此 weil_P_Q ^ 12  =  512 和 weil_R_S 相等

3. 总结

这一讲,我们介绍了可以高效计算配对的 Miller 算法,并使用 Sage 写了一个 Weil 配对的例子。