面向大众的配对，第二部分：Tate配对

为我们其余人准备的配对，第二部分

Tate 配对

理解椭圆曲线（EC）配对引导我阅读了许多书籍和研究论文。每个来源都教给我一些新的东西，但它们通常假设了很高的数学知识水平，并引入了复杂的概念。第一部分，我们专注于找到子群 G1 和 G2，这具有挑战性，但仍然可以控制。然而，当涉及到实际的配对计算时，我发现自己很难理解像“函数除子”和“等价类”这样的术语。

但别担心。在不深入研究高等数学的情况下，理解底层发生了什么是可能的，当然，要牺牲普遍性和精确性。本文将帮助你建立关于 Tate 配对的基本直觉。我们将跳过一些更复杂的细节，比如除子，而是使用简单的解释和类比。这种方法可能不是完全准确的，但这是我学习这个主题的方式。我的目标是给你一个良好的基础，并鼓励你在以后有兴趣时探索更详细的资源。

在第一部分中，我们探索了由

$y^2 = x^3 + 8x + 8 \mod 13$ 定义的 “Tiny JubJub” 曲线，并将我们的基域

$F_{13}$ 扩展到

$F_{13^4}$。我们学习了 Frobenius 自同态和迹映射，这帮助我们找到了子群

$G_1$ 和

$G_2$。这为第二部分奠定了基础，我们将在其中实现 Tate 配对。

然而，在我们深入细节之前，让我们快速回顾一些基础知识，以确保我们都在同一页面上。

点和线：距离关系

平面上的每两个点

$(x_1, y_1)$ 和

$(x_2, y_2)$ 都可以用一条线连接起来，这条线的斜率可以用以下公式计算：

$m = \frac{y_2 - y_1}{x_2 - x_1}$

现在，如果我们有第三个点

$(x_t, y_t)$，并且我们想检查它是否位于同一条线上，我们将它代入

$v = m \cdot (x_t - x_1) - (y_t - y_1)$ 并检查是否

$v == 0$。

让我们考虑以下点：

$A = (x_1, y_1) = (-1, 1)$

$B = (x_2, y_2) = (3, 2)$

$C = (x_3, y_3) = (7, 3)$

$D = (x_4, y_4) = (5, 1)$

$E = (x_5, y_5) = (2, 1)$

由点

$A$ 和

$B$ 形成的直线的斜率为：

$m = \frac{2 - 1}{3 + 1} = 0.25$

要检查点

$C$ 是否位于该线上，我们计算：

$v = 0.25 \cdot (7 + 1) - (3 - 1) = 0$

由于

$v = 0$，点

$C$ 位于该线上。但是，当我们插入点

$D$ 和

$E$ 的坐标时，我们得到

$v_D = 1.5$ 和

$v_E = 0.75$。点

$D$ 和

$E$ 不在该线上，因为它们的

$v \neq 0$。我们可以看到这些点与该线的距离不同，其中点

$E$ 更接近。这使我们得出结论，

$v$ 表示点和线之间的一些距离关系：值越大，点离线越远。

重要的是要注意

$v$ 的值不代表实际距离。点到线的实际距离可以使用不同的公式计算（参见维基百科），该公式计算

$D$ 与线之间的距离为

$\frac{6}{\sqrt{17}}$。但是，我们对那个距离不感兴趣。重要的是要强调，我们认为

$v$ 只是点和线之间距离关系的指标，而不是欧几里得距离。

EC 点：加法和倍乘

添加两个椭圆曲线（EC）点，

$P$ 和

$Q$，包括在它们之间画一条线。这条线将在另一个点

$R'$

$(x_t, y_t)$ 与曲线相交。在使用上一节中描述的方法找到该点后，我们翻转其 y 坐标以获得新点

$R$

$(x_t, -y_t)$，它是

$P$ 和

$Q$ 的总和。(左图)

当我们想将点

$P$ 加到它自身时，我们画一条与

$P$ 相切的切线。这条切线在另一个点与曲线相交，然后，我们再次翻转其 y 坐标以获得

$P + P$ 的结果。(右图)

我们已经描述了如何计算两个不同点，

$P$ 和

$Q$ 之间连线的斜率，以及如何检查第三个点是否位于由

$P$ 和

$Q$ 定义的线上。然而，我们还没有讨论线及其斜率在与曲线相切时的特殊情况。

让我们定义一条曲线

$E: y^2 = x^3 + ax + b$ 和该曲线上的一点

$P$。与曲线相切并穿过

$P$ 的线的斜率由

$E$ 的导函数

$\frac{dy}{dx}$ 给出，在

$P$ 处进行评估。我们不会在这里费心区分方程，而是直接给出斜率的公式：

$m = \frac{3x^2 + a}{2y}$

请参考“Pairings for Beginners”（第 2.1.2 节）以获取有关这些公式的推导和深入讨论。

标量乘法：Double-and-Add 算法

“Double-and-Add”算法是一种有效的计算椭圆曲线（EC）点

$P$ 乘以标量

$m$ 的方法。将

$P$ 乘以

$m$ 本质上意味着将

$P$ 加到它自身

$m$ 次：

$P + P + \dots + P$ （$m$ 次）

但是，以

$m$ 步执行此操作效率低下，尤其是在处理来自大型有限域的标量时。“Double-and-Add”算法优化了此过程。

我们将使用这个有启发性的例子来快速理解该算法。让我们考虑一个 EC 点

$P$ 和一个标量

$m = 26$：

1. 写下

$m$ 的二进制表示形式：

$26 = (11010)_2$

2. 从第二个最高有效位开始，循环访问所有位
3. 初始化一个累加器

$A = P$。对于每个位，如果它是 1，则将累加器加倍并将

$P$ 添加到其中（即，

$A = 2A + P$）；如果它是 0，则仅将累加器加倍（即，

$A = 2A$）

这是详细的逐步过程：

位	操作	结果
1	忽略	A=P
1	加倍	A=2A=2P
	添加	A=A+P=3P
0	加倍	A=2A=6P
1	加倍	A=2A=12P
	添加	A=A+P=13P
0	加倍	A=2A=26P

使用 “Double-and-Add” 算法，我们仅用 5 步而不是 26 步计算

$26P$。

---

回顾了所有主题后，我们准备好跳入我们主题的实质内容。Tate 配对由两个组成部分组成：Miller 循环和最终求幂。

Miller 循环

为了对 Miller 循环进行高级概述，我将从 Michael Scott 的《计算 Tate 配对》中的精彩入门开始，并结合一个具体的例子进行开发。

“Tate 配对的符号是

$e(P, Q)$，其中

$P$ 和

$Q$ 是椭圆曲线

$E(F_{p^k})$ 上的点，并且阶数为

$r$。Tate 配对评估为

$F_{p^k}$ 中的一个元素。

………

基本上（并且非常宽松地），Miller 算法首先使用用于椭圆曲线点乘法的标准 double-and-add 算法执行

$P$ 乘以

$r$ 的隐式乘法。当然，此乘法的结果将是无穷远处的点，因为

$P$ 的阶数为

$r$。(…) 在过程的每一步中，都根据当前线和点

$Q$ 之间的距离关系计算

$F_{p^k}$ 值。该值被乘法累积，其最终值是 Miller 循环的输出。”

与第 1 部分类似，我们使用在素数有限域

$F_{13}$ 上定义的“TinyJubJub”曲线来说明整个过程。请记住，由于

$r = 5$ 是曲线阶数的最大素因子，因此我们计算了嵌入度

$k = 4$ 并将

$F_{13}$ 扩展到

$F_{13^4}$。因此，我们找到了两个不同的子群，

$G_1$ 和

$G_2$。那些子群的点的重​​要特征在于，当乘以

$r$ 时，它们都会变为无穷远点。

$P$ 和

$Q$，分别属于一个或另一个子群，将被插入到 Miller 循环中。

如入门中所述，我们将采用

$P$ 并应用 “Double-and-Add” 算法将其乘以

$r$。每个循环步骤都在累加器点和点

$P$ 之间绘制新线，因此工作是计算那些线和

$Q$ 之间的距离关系。结果值将来自

$F_{13^4}$，并且所有

$F_{13^4}$ 值的乘积将是 Miller 循环的输出。

这是配对两个点

$P$ 和

$Q$ （来自

$F_{13^4}$ 上的“Tiny JubJub”）的逐步过程。

参数和输入

$a = 8$（由 $y^2 = x^3 + 8x + 8$ 给出，用于斜率公式中）

$r = 5 = (101)_2$

$P = (x_P, y_P) = (8, 8)$

$Q = (x_Q, y_Q) = (4x^2 + 7, 5x^3 + 10x)$

初始化

$A$（累加器点）$= (x_A, y_A) = (8, 8)$

$f$（累积距离）$= 1$

$v$（距离关系）$= 1$

斜率公式

$m$ 对应于操作

$m_{add} = \frac{y_A - y_P}{x_A - x_P}$

$m_{double} = \frac{3x_A^2 + a}{2y_A}$

步骤

循环访问最大素因子

$r$ 的所有位：

$5 = (101)_2$，忽略第一个位。记住我们在

$\mod 13$ 中运算。

1. 下一个位的

$0$，操作为 “Double”，导致斜率通过以下方式计算：

$m = \frac{3x_A^2 + a}{2y_A} = \frac{3 \ast 8^2 + 8}{2 \ast 8} = 6$ 2.

$A$ 和

$Q$ 之间的距离关系

$v$ 为

$v = m \ast (x_Q - x_A) - (y_Q - y_A) = 6 \ast (4x^2 + 7 - 8) - (5x^3 + 10x - 8)$

3. 距离

$f$ 接下来被乘法累积

$f = f \ast f \ast v = 1 \ast 1 \ast 8x^3 + 11x^2 + 3x + 2 = 8x^3 + 11x^2 + 3x + 2$

4. 累加器点

$A$ 也被加倍

$A = 2A = (7, 11)$

5. 下一个位的

$1$，因此我们首先类似于之前的步骤进行加倍，但也进行 “Add” 操作

6. 我们最终得到

$f = 12x^3 + 11x^2 + 2x + 9$，它是

$F_{13^4}$ 中的一个值

位	操作	斜率 <br>madd/double	距离关系 <br>v=m∗(xQ−xA)−(yQ−yA)	累积距离 <br>f	累积点 <br>A
1	忽略	-	1	1	A=P=(8,8)
0	加倍	6	8x3+11x2+3x+2	f∗f∗v=8x3+11x2+3x+2	A=2A=(7,11)
1	加倍	4	8x3+x2+3x+11	f∗f∗v=12x3+10x2+6x+2	A=2A=(8,5)
	添加	1	xQ−xA=4x2+12	f∗v=12x3+11x2+2x+9	A=A+P=O

最终求幂

当我们谈论 EC 点的阶数（不要与曲线的阶数混淆）时，我们指的是基础域中的标量，当乘以该点时，该标量会将给定的点发送到无穷大：

$P \ast 5 = O$，在我们的例子中。

类似地，来自基础域的值也有一个（乘法）阶数

$m$，当它们被提升到

$m$ 的幂时，会将它们发送到单位元素（即 1）。例如，

$4$ 在

$F_{13}$ 中的乘法阶数为 6，因为

$4^6 = 1 \mod 13$。

回想一下，两个 EC 点要“可配对”的要求之一是具有相同的阶数。这也适用于配对的输出：结果值必须与 EC 点的阶数相同。

上面的示例表明，Miller 循环输出

$f = 12x^3 + 11x^2 + 2x + 9$ 是扩展域

$F_{13^4}$ 中的一个值。

$f$ 的阶数为

$4080$，而

$P$ 和

$Q$ 的阶数为

$5$。这就是为什么我们必须将

$f$ 提升到某个幂，以将其阶数降至

$5$。此操作称为 “最终求幂”。事实证明，如果我们将

$f$ 提升到

$(q^k - 1) / r$ 的幂，它将消除阶数

$r$ 的所有倍数，我们将从阶数

$5$ 的域中获得一个值。这是 Tate 配对的最终结果：

$e(P, Q) = (12x^3 + 11x^2 + 2x + 9)^{5712} = 6x^3 + 7x^2 + 7x + 3$

结束语

本系列记录了我的学习历程和我对椭圆曲线配对的理解。它并不声称 100% 准确或详尽无遗，但旨在为那些刚接触该主题的人提供一个基本的直觉。我欢迎任何反馈、更正或建议，以改进内容并帮助所有读者更好地理解该主题。感谢你加入我的旅程，并随时在 X 上与我联系：@BoyanBarakov。

• 原文链接： hackmd.io/@brozorec/pair...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～