椭圆曲线配对

从基础开始

2024年12月10日

椭圆曲线双线性配对为椭圆曲线密码学提供了独特的用例，包括高效的签名聚合、单轮多方密钥交换和用于零知识简洁非交互式知识论证（zk-SNARK's）的多项承诺方案。尽管对密码学领域产生了深远影响，但它们在很大程度上仍笼罩在神秘之中。通常被称为“月球数学”，它们的实现细节被藏在一个黑盒中。非退化双线性的代数结构可以大致当作直接的实用工具，尽管在性能和哪类曲线能够使用什么配对之间仍存在一些微妙之处。

在此文档中，我们将介绍构造椭圆曲线双线性配对所需的基本属性，同时附上一些简单的、未经优化的Python代码片段，帮助理解。群论以及随后的环论是很好的前置知识，特别是多项式环。

引言

椭圆曲线和双线性映射都是相当抽象的，有许多椭圆曲线，以及许多函数单独产生双线性。特别是，我们对表现出难以处理的椭圆曲线离散对数问题（ECDL）的有限域上的椭圆曲线感兴趣。此外，我们感兴趣的是将两个椭圆曲线点转换为一个标量的双线性映射，从而保持双线性（在配对部分将会详细介绍），ECDL问题仍然难以解决，寻找两个非平凡的椭圆曲线点对以映射到相同的标量输出是不可行的。

有限域

这一切的基础是有限域，也称为伽罗华域或素数域。该域的元素是介于零与某个素数“p”之间的整数，算术运算是在“p”模上进行的，并且该域承认我们期望的代数结构，即加法和乘法承认结合性、交换性、可逆性（分别为减法和除法），并且乘法对加法分配。

Fp⊂Z∀a,b,c∈Fp(a+b)+c=a+(b+c)a+b=b+aa+0=0+a=aa+(−a)=(−a)+a=0(a∗b)∗c=a∗(b∗c)a∗b=b∗aa∗1=1∗a=aa∗a−1=a−1∗a=1a∗(b+c)=(a∗b)+(a∗c)

请注意，域元素的除法与常规理解中的整数除法是不同的。例如，将一除以二，结果是“0.5”，这是在素数域中并不存在的整数。然而，由于除法是乘法的反操作，我们只需要为每个数字找到一个“逆”，使得用该数字与其“逆”模素数相乘的结果为1。例如，如果我们的素数是“7”，我们可以如下面所示定义“二”的逆：

p = 7
two = 2
inverse_of_two = 4

assert 1 == (two * inverse_of_two % p)

为任何大素数域中的元素有效地找出一个逆可以通过扩展欧几里得算法实现，尽管实际应用中效率不高。

扩展域

扩展域是给定域的一个适当超集，它承认其基础域所承认的所有代数结构。用于解释扩展域的常见示例是复数作为实数的扩展，可以表示为一个一阶或两个系数的多项式，其中变量“i”是虚成分。

R⊂Ca,b∈Ra+bi∈C

实数存在于复数中，其中“b”为零。

class Complex:
    a: float
    b: float

    def __init__(self, a, b):
        self.a = a
        self.b = b

    def from_real(n):
        return Complex(n, 0.0)

real_n = 5.0
complex_n = Complex.from_real(real_n)

然而，复数在代数上是封闭的，也就是说，它们无法进一步扩展。

有限域扩展也可表示为多项式。例如，一个一阶有限域可以表示如下。

Fp⊂Fp2∀a,b,c∈Fp2a=a1x+a0b=b1x+b0c=c1x+c0(a+b)+c=a+(b+c)a+b=b+aa+0=0+a=aa+(−a)=(−a)+a=0(a∗b)∗c=a∗(b∗c)a∗b=b∗aa∗1=1∗a=aa∗a−1=a−1∗a=1a∗(b+c)=(a∗b)+(a∗c)

所有预期的域结构在多项式加法和乘法下都是保持的。Fp2的元素是以系数为基础域Fp的度-1多项式。

class Fp:
    p = 7     # 一些素数

    value: int

    def __init__(self, value):
        self.value = value % p

class Fp2:
    a0: Fp
    a1: Fp

    def __init__(self, a0, a1):
        self.a0 = a0
        self.a1 = a1

    def from_base_field(n):
        return Fp2(n, Fp(0))

fp_n = Fp(5)
fp2_n = Fp2.from_base_field(fp_n)

然而，我们可以任意扩展有限域。例如，度为11的域扩展，有12个系数，如下所示。

Fp⊂Fp12a∈Fp12:a12x12+a11x11+⋯+a0x0

“域扩展的塔”或“扩展塔”在双线性配对的文献和实现中被提及。这是一种优化域扩展操作的策略。

特别是，与其直接将基域从Fp扩展到Fp12，实施者通常会首先构建一个具有2个系数的Fp多项式，然后是具有3个系数的扩展Fp6，再用在Fp6中具有2个系数的多项式，构建出扩展的塔。

用词的表达要保持准确且可读，以下记法应该表示如何通过较低度的扩展域构建每个扩展域。

Fp2:(Fp,Fp)Fp6:(Fp2,Fp2,Fp2)Fp12:(Fp6,Fp6)

在Python中的简化形式如下。

class Fp:
    a: int

    # -- 省略

class Fp2:
    a0: Fp
    a1: Fp

    # -- 省略

class Fp6:
    a0: Fp2
    a1: Fp2
    a2: Fp2

    # -- 省略

class Fp12:
    a0: Fp6
    a1: Fp6

    # -- 省略

这种表示在实现中更为常用，因为它使得对Fp12的运算能够使用分治策略。然而，这只是一个实现细节，最终结果是相同的。

椭圆曲线

我们定义一个有限域元素坐标“x”和“y”上的椭圆曲线，使得满足以下方程。

a,b,x,y∈FpE(Fp):y2=x3+ax2+b

class ECPoint:
    a = 1
    b = 3

    x: int
    y: int
    is_infty: bool

    def __init__(self, x, y, is_infty=False):
        assert self.is_on_curve(x, y)
        self.x = x
        self.y = y
        self.is_infty = is_infty

    def is_on_curve(self, x, y):
        y**2 == x**3 + self.a*(x**2) + self.b

方程中的“a”和“b”系数经过精心选择，使得独特的椭圆曲线点的数量，或称“子群阶”，既大又是素数。我们将子群阶称为“r”，因此，域元素在模“r”的域中的形式如下。

Fr

点加法

我们将点加法定义为从两个点到同一曲线上另一个点的映射。请注意，这不仅仅是简单地将坐标相加，而是一个满足循环群法则的方程。

P,Q,R∈E(Fp):P⊕Q=R

直观地说，这可以通过一条直线在椭圆曲线上的三个交点“P”、“Q”和“R”来可视化，然后反转“R”的“y”坐标。

注意：网格使用了实数以便进行直观的可视化。然而，在有限域中，坐标仅为介于0和“p”之间的整数，因此看起来十分稀疏。

我们为不等价的点定义如下方程（该情况在下节讨论）。

λ=xQ−xPyQ−yPxR=λ2−xP−xQyR=λxP−λxR−yPR=(xR,yR)

这里的lambda是交线的斜率，坐标是它第三次交点的反值。

点倍加

我们还定义点与自身相加的情况。

P∈E(Fp):P⊕P=[2]P

我们简单地将将点与自身相加，或者点倍加称为‘[2]P’。这也称为‘标量点乘’，是椭圆曲线密码学的基础。

请注意，一些符号将这种标量点乘称为指数运算。为保持本文章的清晰性，我们将避免使用指数符号，但值得知道以下符号是等效的。

G∈E(Fp),n∈Fp:[n]G=Gn=∑nG

注意：网格使用了实数以便进行直观的可视化。然而，在有限域中，坐标仅为介于0和“p”之间的整数，因此看起来十分稀疏。

我们将以下方程定义给出。

λ=3xP2+a2yPxR=λ2−2xPyR=λxP−λxR−yP[2]P=R=(xR,yR)

循环群

最后，我们包括一个抽象的“无穷大点”，其在视觉上表现为将两个点在垂直方向上相加，即将一个点与其纵坐标的反值相加。

P⊕−P=(xP,yP)⊕(xP,−yP)=O

然而，值得注意的是，无穷大点并不是一个具体的具有x和y坐标的点，而是点加法的抽象单位元素。

G1=E(Fp)∪{O}

通过此方式，我们可以选择生成点‘G’，从而通过不断将一个点自身相加来衍生出循环群中的每一个点。

G∈G1∀P∈G1,∃n∈Fr:[n]G=P

注意，我们将‘G1’定义为曲线，将‘G’定义为生成点。使用‘G1’的原因将在下一节解释。目前，视为与‘E(Fp)’可互换。

该循环群保持所有预期的群法则，特别是我们将这些法则与标量联系起来，以展示结构并构建直至配对的直观理解。

∀a,b,c∈Fr,G∈G1[a]G=A,[b]G=B,[c]G=CA⊕B⊕C=A⊕(B⊕C)A⊕B=B⊕AA⊕O=O⊕A=AA⊕−A=−A⊕A=O

此外，循环群元素之间的点加法可以以两种等效方式表示。

∀a,b∈Fr,G∈G1[a]G⊕[b]G=[a+b]G

如此一来，无论形式如何，群法则都保持成立。

另请注意，一些经过优化的椭圆曲线软件库使用“投影点”，其中点在三维空间中表示。这种形式允许对点算术进行优化。请记住，在仿射（二维）点上进行点加法和倍加时需要除法来计算‘lambda’，即线的斜率。同时请记住，有限域上的除法开销很大。然而，在投影（三维）点上进行点加法和倍加不需要除法。因此，这是一种椭圆曲线算术中的常见优化。

基域扩展上的椭圆曲线

回想一下，域扩展是基域的超集。正如我们可以在整数的素数域的标量上定义椭圆曲线一样，我们也可以在具有任意度数的素数域扩展上做同样的事情。

Fp⊂Fp2a,b,x,y∈Fp2y2=x3+ax2+b

所有用于计算椭圆曲线点的方程都可以在多项式上执行，其中所有椭圆曲线点由多项式组成作为坐标。因此，我们在Fp2上定义椭圆曲线G2。

G2=E(Fp2)

下文定义的双线性配对依赖于两个具有相同子群阶'r'的椭圆曲线。然而，问题在于，度为1的扩展域多项式含有大约‘p’平方个元素，从而在其上定义的椭圆曲线大约有‘r’平方个元素。

然而，有一个群论现象，我自身资历不足以说明，而数学家则用“魔法”和“华丽”这些词来描述，它使得反复扩展基域最终会产生一个扩展域，使其椭圆曲线再次具有与原始曲线相同的子群阶。很可能是因为点在更大的扩展域中变得不再独特。

发生此现象所需的扩展次数称为“嵌入度”，通常用‘k’参数表示。例如，BLS12-381和BN254曲线的嵌入度为12。这一特定的嵌入度是使曲线“配对友好”的一个特征，在双线性配对部分的进一步解释中将详细说明。

双线性配对

一般双线性映射

在定义椭圆曲线的双线性配对之前，理解双线性映射到底是什么是很重要的。

抽象地说，双线性映射是将两个对象映射到另一个对象的函数，但具有一种重要的结构。

e:M×M→R∀x,y,z∈M:e(x⋆y,z)=e(x,z)⋄e(y,z)e(x,y⋆z)=e(x,y)⋄e(x,z)

请注意，我们使用“星号”和“菱形”操作符仅作抽象用途。“星号”操作符作用于‘M’的元素，而“菱形”操作符则作用于‘R’的元素。

我们关心的结构是，能够在给定的双线性映射下重新排列数学方程中的变量。

椭圆曲线双线性映射

在椭圆曲线的背景下，我们使用双线性配对将两个椭圆曲线点映射到一个标量。然而，我们还需要无退化性这一属性，即，对于两个不同的点，其配对不应映射到‘1’。为了实现这一点，我们需要使用具有相同子群阶的两条椭圆曲线。回想一下，具有12的嵌入度的椭圆曲线以及度为11（12个系数）的扩展域，其子群阶相同。

G1×G12→Fp12

通过这一点，我们可以将G1和G12中的一个点映射到Fp12中的一个标量。然而，在G12中计算任何东西都是计算上昂贵的。标量点乘与一个大标量的关系导致许多点倍加和加法，进而导致许多斜率和坐标的计算，每个方程都是度为11的多项式。

六次扭曲

在大小和复杂性方面的优化来自于构建在扩展域上的椭圆曲线之间的同构，这种同构称为扭曲。这个扭曲使我们可以将一个在某些度-n的点上的椭圆曲线转化为某些度-m的椭圆曲线，其中‘m’小于‘n’。我们可以将最大降低的度数称为6，这被称为六次扭曲，并且它只发生在参数‘a’为零的曲线上。

E(Fpn):y2=x3+bG2=E(F2),G12=E(F12)ψ:G12→G2ψ′:G2→G12∀P∈G12:P=ψ′(ψ(P))

回想R，BLS12-381和BN254曲线的嵌入度为12，即其扩展域的椭圆曲线，子群阶为‘r’，具有12个系数，通过六次扭曲可以降为2个系数。也就是说，以下两种配对是同构的。

G1×G12→Fp12≅G1×G2→Fp12

因此，一般在基于配对的椭圆曲线密码学中使用的双线性配对为：

e:G1×G2→Fp12g1∈G1g2∈G2e([a]g1,[b]g2)=e([ab]g1,g2)=e(g1,[ab]g2)

请注意，我们在这个示例中将曲线‘G1’中的点‘g1’和曲线‘G2’中的点‘g2’称为生成点，以消除对于使用的曲线的模糊性。

Tate配对

有4种类型的配对，每种适用于不同参数的不同曲线。覆盖所有这些内容超出了本文件的范围，也是多余的。大多数配对方程都是理论性的，不易计算，有些则仅仅是对其他方程的迭代和优化。因此，我们将专注于Tate配对以及其优化的迭代，最佳Ate配对。

Tate配对依赖于一个称为米勒循环的算法和一个通常称为“最终指数”的指数步骤。关于该算法的理论涉及功能因子，这超出了本文件的范围，因此我们将Tate配对定义如下。

e(P,Q)=fr,P(DQ)(pk−1)/r

其中米勒循环计算如下：

fr,P(DQ)

最终的指数则相当于通过嵌入度的基域规模的次方减去1，除以子群阶。

(pk−1)/r

米勒循环

尽管对米勒循环的深入探讨理想上应该包含其背后的原因，但从米勒循环的实现看，解释其数学上实现的目的深入到函数因子、投影空间和代数几何中，需要很多前置概念和数学分支，规模将显著增加，而我实际上尚未完全理解。因此，我提议妥协：米勒循环将在其实现中加以说明，而其背后的理论将委托给本文结尾的链接。

米勒循环的实现累积了一个在Fp12中的标量，称为变量‘f’。

线函数用于将值累积到‘f’中，并且可以通过类似于点算术的方式进行可视化，其中一条线可以交叉两个点（加法）或与一个点相切（倍加），我们用它来在第三个点进行评估。

def line_function(p, q, t):
    # 'p + q'
    if p.x != q.x:
        lam = (q.y - p.y) / (q.x - p.x)
        return lam * (t.x - p.x) - (t.y - p.y)

    # 'p + p'
    elif p.y == q.y:
        lam = 3 * (p.x**2) / (2 * p.y)
        return lam * (t.x - p.x) - (t.y - p.y)

    # 'p + -p'
    else:
        pass

    return t.x - p.x

‘y’标量从1开始，并累积线函数的评估。我们循环遍历子群阶‘r’的位。如果位为零，我们只需将‘t’点倍加并评估线函数。如果位为一，我们倍加‘t’点并评估线函数，然后将‘t’点与‘p’相加，再评估一次线函数。

r = ..               # 嵌入度
r_bits = bin(r)[2:]

def miller_loop(p, q):
    f = Fp12.one()
    t = p

    for bit in r_bits:
        f = (f**2) * line_function(t, t, q)
        t = 2 * t

        if bit == '1':
            f = f * line_function(t, p, q)
            t = t + p

    return f

最终指数

最终指数并没有特别出奇，尽管计算上相当密集，涉及对标量在Fp中的大素数次方进行指数运算。因此，扩展域塔变得非常重要的优化，因为在没有它们的情况下进行如此大规模的指数运算会更加昂贵。

此外，2024年初发表的研究显示，最终指数可以被功能上等价的检查所替代，这样的计算显著便宜。

优化

除了将椭圆曲线点从仿射空间转移到投影空间，再利用域扩展塔来减小扩展域计算成本以及利用扭曲同构来降低椭圆曲线中的扩展域度，以便于完成点算术外，椭圆曲线双线性配对中还有许多其他优化。

Tate配对是Weil配对的更高效版本，用额外的米勒循环替代最终指数。Ate配对显著减少了米勒循环中执行的迭代，与Tate配对相比，优化的Ate配对则更进一步。在某些情况下，当配对中的两个点之一固定时，也可以预计算值。

结论

椭圆曲线配对是一个相当深奥而复杂的细分领域，它位于椭圆曲线和基于配对的密码学之间以一种相当意外的方式存在，其中曲线参数产生极不可能的特征组合。尽管它的实现细节常常是黑盒的，但实现中的细微差别使得能够实现新颖的优化，而椭圆曲线配对是一个活跃发展的领域。理解基本概念并逐步构建配对是一个良好的开端，尽管许多内容本文件无法在合理的时间内覆盖，从函数因子到弗罗贝尼乌斯自同构再到安全参数，如今概述的内容显然是不够的。

然而，我希望这篇文章能在探索椭圆曲线配对的基础上提供信息。

以下是一些我强烈推荐的无价资源，以深入了解更多内容。

• BLS12-381 其他研究者：关于BLS12-381的优秀解释，以及配对友好曲线的含义。

• 初学者的配对（PDF）：关于椭圆曲线配对为何有效的一次全面深入探讨。

• py_ecc：基于BLS12-381和BN254的以太坊配对库，具有可读和优化的实现。

• sylow：Warlock前沿的BN254配对库，文档丰富，并附有相关论文和领域进展的参考。

期待下一次。

• 原文链接： jtriley.substack.com/p/e...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～