Pairing (Weil/Tate/Eta/Ate Pairing)

设有理函数 \[f(X) = \frac{a_0 + a_1 X + \cdots + a_n X^n}{b_0 + b_1 X + \cdots + b_m X^m}\] 在复数范围内进行因子分解，那么它也可以写为 \[f(X) = \frac{a(X - \alpha_1)^{e_1} (X- \alpha_2)^{e_2} \cdots (X- \alpha_r)^{e_r}}{b(X - \beta_1)^{d_1} (X- \beta_2)^{d_2} \cdots (X - \beta_s)^{d^s}}\] 其中 \(\alpha_1,\cdots,\alpha_r\) 和 \(\beta_1, \cdots, \beta_s\) 各不相同。 \(\alpha_1, \alpha_2, \cdots, \alpha_r\) 是零值点，而 \(\beta_1, \beta_2, \cdots, \beta_s\) 是极值点。这了跟踪这些零值点和极值点，我们定义 \(f(X)\) 的 Divisor 为： \[\text{div}(f(X)) \triangleq e_1 [\alpha_1] + e_2 [\alpha_2] + \cdots e_r [\alpha_r] - d_1 [\beta_1] - d_2 [\beta_2] - \cdots d_r[\beta_r]\] 式子仅仅 表明 \(f(X)\) 有 \(e_1\) 个零值点 \(\alpha_1\) ，有 \(e_2\) 个零值点 \(\alpha_2\) ，...，有 \(d_r\) 个极值点 \(\beta_r\) ， \(\text{div}(f(X))\) 仅仅是这个表述的一个记号而已。 式子中没有标量乘法运算（记号 \(e_1 [\alpha_1]\) 并不是标量乘法运算，而是表示 \(e_1\) 个零值点 \(\alpha_1\) ）。

上面 \(f\) 是单变量函数，类似地，可以推广到多变量函数。对于椭圆曲线 \(E: Y^2 = X^3 + AX + B\) 来说，其上的点 \(P = (x,y)\) ，可以定义两个变量的函数 \(f(P) = f(x,y)\) 。这时， \(f\) 在 \(E\) 上也有零值点和极值点。

我们定义 Divisor on Curve E \[D \triangleq \sum_{p \in E} n_p [P]\] 其实 \(D\) 就是一些点的集合（并不涉及点的加法和标量乘法运算）。比如有 \(E(\mathbb{F}_{61}): y^2 = x^3 + 8x + 1\) ，点 \(P=(57,24), Q=(25,37)\) 在这个曲线上，我们可以定义 \(D_1 = 1 [P] + 2 [Q], D_2 = 2 [P] + 3 [Q]\) ，或者其它的形式都可以。

定义 Degree of a divisor 是前面定义式子中系数的和，即 \[\text{deg} (D) = \text{deg}\left( \sum_{p \in E} n_p [P]\right) \triangleq \sum_{p \in E} n_p\] 定义 Sum of a divisor 是去掉中括号后的式子（也就是说 \(\text{Sum}(D)\) 会涉及到点的加法和标量乘法运算了， \(\text{Sum}(D)\) 本身不再是点的集合了，它自己就是一个点），即 \[\text{Sum}(D) = \text{Sum} \left( \sum_{p \in E} n_p [P] \right) \triangleq \sum_{p \in E} n_p P\] 式子中 \(n_P P\) 表示 \(P\) 加上自己一共加 \(n_P\) 次。

当且仅当 \(\text{deg}(D) = 0\) 和 \(\text{Sum}(D) = \mathcal{O}\) 同时成立时， \(D\) 被称为 Divisor of a rational function on E。

设 \(Y^2 = X^3 + Ax + B = (X - \alpha_1)(X - \alpha_2)(X - \alpha_3)\) ，由于没有 \(X^2\) 项，从而有 \(\alpha_1 + \alpha_2 + \alpha_3 = 0\) ，记 \[P_1 = (\alpha_1, 0), P_2 = (\alpha_2, 0), P_3 = (\alpha_3, 0)\] 容易验证这 3 个点的阶都是 2。求 Weil Pairing \(e_2(P_1, P_2), e_2(P_1, P_3), e_2(P_2, P_3)\)

按定义计算 Weil Pairing 时，需要寻找满足条件的 \(f_{P_1}(X,Y), f_{P_2}(X,Y), f_{P_3}(X,Y)\) 。这里设 \(f_{P_i}(X,Y) = X - \alpha_i\) 容易验证 \[\text{div}(f_{P_i}) = 2 [P_i] - 2 [\mathcal{O}]\] 所以 \(f_{P_i}\) 满足计算 Weil Pairing 的要求。

取 \(S=(x,y) \in E\) ，那么点 \(P_1 - S\) 的 \(x\) 坐标（根据椭圆曲线定义）为 \[\begin{aligned} X_{P_1 - S} &= \left( \frac{-y}{x-\alpha_1} \right)^2 - x - \alpha_1 \\ &= \frac{y^2 - (x - \alpha_1)^2(x + \alpha_1)}{(x - \alpha_1)^2} \\ &= \frac{(x-\alpha_1)(x-\alpha_2)(x - \alpha_3) - (x - \alpha_1)^2(x + \alpha_1)}{(x - \alpha_1)^2} \\ &= \frac{(- \alpha_2 - \alpha_3)x + \alpha_2 \alpha_3 + \alpha_1^2}{x - \alpha_1} \\ &= \frac{\alpha_1 x + \alpha_2 \alpha_3 + \alpha_1^2}{x - \alpha_1} \end{aligned}\]

类似地，我们可以得到 \(P_2 + S\) 的 \(x\) 坐标为 \[X_{P_2 + S} = \frac{\alpha_2 x + \alpha_1 \alpha_3 + \alpha_2^2}{x - \alpha_2}\]

下面，我们按照 Weil Pairing 的定义进行计算 \[\begin{aligned} e_2(P_1, P_2) &= \frac{f_{P_1}(P_2+S)}{f_{P_1}(S)} \bigg/ \frac{f_{P_2}(P_1-S)}{f_{P_2}(-S)} \\ &= \frac{X_{P_2+S} - \alpha_1}{X_S - \alpha_1} \bigg/ \frac{X_{P_1-S} - \alpha_2}{X_{-S} - \alpha_2} \\ &= \frac{\frac{\alpha_2 x + \alpha_1 \alpha_3 + \alpha_2^2}{x - \alpha_2} - \alpha_1}{x - \alpha_1} \bigg/ \frac{\frac{\alpha_1 x + \alpha_2 \alpha_3 + \alpha_1^2}{x - \alpha_1} - \alpha_2}{x - \alpha_2} \\ &= \frac{(\alpha_2 - \alpha_1)x + \alpha_1 \alpha_3 + \alpha_2^2 + \alpha_1 \alpha_2}{(\alpha_1 - \alpha_2)x + \alpha_2 \alpha_3 + \alpha_1^2 + \alpha_1 \alpha_2} \\ &= \frac{(\alpha_2 - \alpha_1)x + \alpha_2^2 - \alpha_1^2}{(\alpha_1 - \alpha_2)x + \alpha_1^2 - \alpha_2^2} \quad \text{since}\; \alpha_1 + \alpha_2 + \alpha_3 = 0 \\ &= - 1 \end{aligned}\]

类似地，可以计算出 \(e_2(P_1, P_3), e_2(P_2, P_3)\) ，具体过程略。

Victor S. Miller 在 Short Programs for functions on Curves 中提出了快速寻找“满足 Weil Pairing 要求的 \(f_P,f_Q\) ”的方法。

Miller 算法（摘自 An Introduction to Mathematical Cryptography, Second Edition）如图 1 所示。

有限域 \(\mathbb{F}_{631}\) 上的曲线 \[E: y^2 = x^3 + 30x + 34\] 这个曲线一共有 \(\#E(\mathbb{F}_{631}) = 650 = 2 \cdot 5^2 \cdot 13\) ，其中阶为 5 的点有 25 个，容易验证 \(P=(36, 60), Q=(121,387)\) 的阶都是 5，求 Weil Pairing \(e(P,Q)\) ，验证满足双线性 \(e(3P, 4Q) = e(P,Q)^{3 \cdot 4}\)

取 \(S=(0,36)\) ，使用 Miller 算法可得： \[\frac{f_P(Q+S)}{f_P(S)} = \frac{103}{219} = 473 \in \mathbb{F}_{631}\] 及 \[\frac{f_Q(P-S)}{f_Q(-S)} = \frac{284}{204} = 88 \in \mathbb{F}_{631}\] 从而 \(P,Q\) 的 Weil Pairing 为 \[e(P,Q) = \frac{473}{88} = 242 \in \mathbb{F}_{631}\]

记 \(P' = 3P = (617,5), Q' = 4Q = (121, 244)\) ，可求得 \[e(P',Q') = \frac{219}{83} = 512 \in \mathbb{F}_{631}\] 可以验证下式成立 \[e(P,Q)^{3 \cdot 4} = 242^{12} = 512 = e(3P, 4Q)\]

Weil Pairing 和 Tate Pairing 有关系 \[e_l(P,Q) = \frac{\tau(P,Q)}{\tau(Q,P)}\] 从式中可知 Weil Pairing 的计算量近似是 Tate Pairing 的两倍。

Paulo S. L. M. Barreto 等在论文 Efficient Pairing Computation on Supersingular Abelian Varieties 中提出了 Eta Pairing。

F. Hess 等在论文 The Eta Pairing Revisited 中提出了 Ate Pairing。论文中交待了 Ate Pairing 名字的由来：

We call our new pairing the Ate pairing, pronounced eight. This is for two reasons, firstly it is like the Tate pairing, but faster (hence the missing ‘T’), it is also like the Eta pairing but it reverses the order of the arguments (and Ate is Eta spelled backwards).