双线性配对 — Pairing 的定义、性质与 Miller 算法

日期: 2026-11-02 方向: 密码学数学 阶段: Phase 4 - 密码学数学基础 (Day 181-194) 标签: #密码学 #pairing #Tate #Weil #Miller-loop #BLS

---

今日目标

---

一、动机

普通 EC 群 $G$ 给我们 DH/DSA。但很多新 primitive 需要"乘法关系"：

• 给定 $g, g^a, g^b$，看到 $g^{ab}$ 是否可验证？（CDH 假设说"不能算"，但希望"能验证"）

Pairing：双线性映射 $e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$，满足 $$e(g_1^a, g_2^b) = e(g_1, g_2)^{ab}$$

→ 一下解锁了：BLS 签名、IBE、KZG、Groth16、attribute-based encryption。

---

二、严格定义

2.1 双线性 Pairing

定义 2.1：设 $\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T$ 是阶 $r$ 的循环群（写加法 / 乘法）。映射 $e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ 是 (admissible) bilinear pairing 若：

1. 双线性 (Bilinear)： $$e(P_1 + P_2, Q) = e(P_1, Q) \cdot e(P_2, Q)$$ $$e(P, Q_1 + Q_2) = e(P, Q_1) \cdot e(P, Q_2)$$ 推论：$e(aP, bQ) = e(P, Q)^{ab}$
2. 非退化 (Non-degenerate)：$e(g_1, g_2) \ne 1$ for generators
3. 可计算 (Efficient)：多项式时间可算

2.2 类型分类

现代主流是 Type III（BLS12-381, BN254 配对），最高效且安全假设最弱。

2.3 群 $\mathbb{G}_T$ 在哪里？

设曲线 $E/\mathbb{F}_p$，子群阶 $r$，嵌入度 $k$（$r \mid p^k - 1$）。

$$\mathbb{G}T = \mu_r \subset \mathbb{F}{p^k}^*$$

即 $\mathbb{F}_{p^k}^*$ 的 $r$-阶单位根子群。

2.4 三种主流 Pairing

---

三、Miller 算法（pairing 的"加法器"）

3.1 关键工具：函数除子

设有理函数 $f$ 在曲线 $E$ 上。其除子 $\text{div}(f) = \sum n_i (P_i)$ 记零点和极点。

关键事实：

• $\text{div}$ 满足 $\text{div}(fg) = \text{div}(f) + \text{div}(g)$
• 主除子（即来自函数的）形成群

3.2 Miller 函数 $f_{r,P}$

定义：函数 $f_{r,P}$ 满足 $\text{div}(f_{r,P}) = r(P) - r(\mathcal{O})$。

递归构造（Miller 1986，发表于 2004）： $$f_{m+n, P} = f_{m,P} \cdot f_{n,P} \cdot \frac{\ell_{mP, nP}}{v_{(m+n)P}}$$

其中 $\ell$ 是过 $mP, nP$ 的直线，$v$ 是过 $(m+n)P$ 的竖直线。

3.3 Miller Loop（计算 $f_{r,P}$）

input: P, r as bits b_{n-1} ... b_0
f = 1, T = P
for i = n-2 down to 0:
  f = f² * (line_{T,T} / vert_{2T})       # doubling step
  T = 2T
  if b_i == 1:
    f = f * (line_{T,P} / vert_{T+P})     # addition step
    T = T + P
return f

复杂度：$O(\log r)$ 次乘法 / line 计算。

3.4 Tate Pairing 公式

$$e_T(P, Q) = f_{r,P}(Q)^{(p^k-1)/r}$$

最后的 $(p^k-1)/r$ 次幂叫 final exponentiation，确保唯一表示（消去 $(\mathbb{F}_{p^k}^*)^r$ 商）。

3.5 Optimal Ate（Vercauteren 2010）

利用 Frobenius 把 Miller loop 长度从 $\log r$ 缩到 $\log r / \varphi(k)$。

对 BLS12-381：

• $r$ ~ 255 bit, $k=12, \varphi(12)=4$
• Optimal Ate Miller loop 长度：约 64 bit
• 加上 final exp 主导成本

---

四、双线性的代数证明（Tate 的 well-defined 性）

断言：$e_T(P+P', Q) = e_T(P, Q) \cdot e_T(P', Q)$。

证明思路：

1. $f_{r, P+P'}$ 与 $f_{r,P} \cdot f_{r,P'}$ 在除子上差一个常数（用 div 计算可见）
2. 但常数被 final exp $(p^k-1)/r$ 抹去，因为常数的 $r$-次方是 $1$ 在 $\mu_r$ 中

非退化性来自 Weil 配对的 alternating 性质 + 选合适的 $P, Q$。可计算性来自 Miller。$\blacksquare$

严格证明见 Silverman Advanced Topics in Arithmetic of EC，Ch. III。

---

五、直觉与图像

5.1 类比：log 和 exp

把 pairing 看作"广义 log"：

• $e(g_1^a, g_2) = e(g_1, g_2)^a$ 把 $a$ "搬出"
• 给定 $A = g_1^a, B = g_2^b$，$e(A, B) = e(g_1, g_2)^{ab}$
• 类似 $\log(x^a y^b) = a \log x + b \log y$

5.2 为什么 DDH 在 pairing 群中容易？

DDH：区分 $(g, g^a, g^b, g^{ab})$ vs $(g, g^a, g^b, g^c)$。

• Type I (对称) 配对 $\mathbb{G}_1 = \mathbb{G}_2$：可算 $e(g^a, g^b) = e(g,g)^{ab}$ 和 $e(g, g^c) = e(g,g)^c$，比较即可 ⇒ DDH 容易
• Type III (非对称, $\mathbb{G}_1 \ne \mathbb{G}_2$)：不能直接算 $e(g_1^a, g_1^b)$ 因 $\mathbb{G}_1 \times \mathbb{G}_1$ 不是 pairing 域 ⇒ DDH 在 $\mathbb{G}_1$ 仍可能难（SXDH 假设）

→ 这就是 Type III 优于 Type I 的原因。

5.3 BLS 签名的 magic

• 签名 $\sigma = sk \cdot H(m) \in \mathbb{G}_1$, 公钥 $pk = sk \cdot G_2 \in \mathbb{G}_2$
• 验证 $e(\sigma, G_2) = e(H(m), pk)$
• 推导：$e(sk \cdot H(m), G_2) = e(H(m), G_2)^{sk} = e(H(m), sk \cdot G_2) = e(H(m), pk)$ ✓

聚合：$\sigma_{\text{agg}} = \sum \sigma_i$，验证 $e(\sigma_{\text{agg}}, G_2) = \prod e(H(m_i), pk_i)$。

---

六、代码示例（伪 Miller loop）

"""
Day 185: Pairing 概念演示 (伪代码 + 真实库调用)
完整 BLS12-381 pairing 用 py_ecc 库
"""

# 真实 pairing: pip install py_ecc
from py_ecc.bls12_381 import (
    G1, G2, multiply, pairing, FQ, FQ12,
    add, neg, eq, curve_order
)

def demo_bilinearity():
    """验证 e(aG1, bG2) = e(G1, G2)^(ab)"""
    a, b = 5, 7
    aG1 = multiply(G1, a)
    bG2 = multiply(G2, b)

    # 左侧: e(aG1, bG2)
    lhs = pairing(bG2, aG1)

    # 右侧: e(G1, G2)^(ab)
    base = pairing(G2, G1)
    rhs = base ** (a * b)

    print(f"e(aG1, bG2) == e(G1,G2)^ab : {lhs == rhs}")


def demo_bls_signature():
    """简化 BLS 签名验证"""
    # 私钥
    sk = 12345

    # 公钥 pk = sk * G2
    pk = multiply(G2, sk)

    # 消息 hash 到曲线 (简化: 实际 hash_to_curve)
    H_m = multiply(G1, 999)  # 假设 H(m) = 999 * G1

    # 签名 sigma = sk * H(m)
    sig = multiply(H_m, sk)

    # 验证: e(sig, G2) ?= e(H(m), pk)
    lhs = pairing(G2, sig)
    rhs = pairing(pk, H_m)
    print(f"BLS 验证: {lhs == rhs}")


def miller_loop_pseudocode():
    """Miller Loop 伪代码 (教学用)"""
    print("""
    Miller(P, Q, r):
      f = 1
      T = P
      for i = bit_length(r) - 2 down to 0:
        # Doubling step
        ell = line(T, T)         # 过 T 的切线
        v   = vertical(2T)        # 过 2T 的垂线
        f = f² * ell(Q) / v(Q)
        T = 2T
        # Addition step
        if bit_i(r) == 1:
          ell = line(T, P)
          v   = vertical(T+P)
          f = f * ell(Q) / v(Q)
          T = T + P
      return f
    """)


if __name__ == "__main__":
    demo_bilinearity()
    demo_bls_signature()
    miller_loop_pseudocode()

---

七、密码学应用关联

---

八、真实参数（BLS12-381 pairing）

p = 0x1a01...aaab (381 bit)
r = 0x73ed...0001 (255 bit, BLS12-381 子群阶)
k = 12

G1: E/F_p,  y² = x³ + 4
G2: E'/F_{p²}, y² = x³ + 4(u+1)
GT: μ_r ⊂ F_{p^12}*

Miller loop 长度 (Optimal Ate): |6u+2| 中的 64 bit, u = -0xd201000000010000

成本（laptop 级）：

• $\mathbb{G}_1$ 标量乘：~80 us
• $\mathbb{G}_2$ 标量乘：~250 us
• Pairing：~3-5 ms
• $\mathbb{F}_{p^{12}}$ 一次乘：~1 us

---

九、常见陷阱

1. Type 混淆：旧文献用 Type I（symmetric）证明，迁到 Type III 时假设变弱（SXDH 替代 DDH）。论文复现时必须重新检查安全证明。
2. 聚合签名的 Rogue Key Attack：朴素 BLS 聚合 $\sigma = \sum \sigma_i$ 会被恶意公钥伪造。修复：proof-of-possession 或加 weight $H(pk_i)$。
3. Subgroup 检查：解析 $\mathbb{G}_2$ 元素必须验证落在 $r$-阶子群（$\mathbb{G}2 \subset E'(\mathbb{F}{p^2})$ 但只取 $r$-子群）。EIP-2537 显式要求。
4. Final Exponentiation 必做：跳过会导致 pairing 不在 $\mu_r$ 中，破坏双线性。
5. 侧信道：Miller loop 中 doubling/addition 分支取决于 $r$ 比特，可被时序攻击。$r$ 是公开的，所以问题转向 $u$（loop 参数）—但 $u$ 也通常公开（非秘密）。秘密标量 $a$ 在 $aP$ 阶段已防护。
6. Hash-to-Curve 一致性：BLS 签名 $H(m) \in \mathbb{G}_1$ 必须可验证、抗碰撞、constant-time。错误实现导致同一消息有多个有效签名（恶意 mutation）。RFC 9380 标准化这步。

---

十、关键速查

公式

Pairing 类型决策

---

十一、面试题

Q1: 解释为什么 pairing 让 DDH 在某些情况下变容易。

答：DDH 是 "区分 $(g, g^a, g^b, g^{ab})$ vs $(g, g^a, g^b, g^c)$"。在对称配对（Type I, $\mathbb{G}_1 = \mathbb{G}_2$）中： $$e(g^a, g^b) = e(g, g)^{ab}, \quad e(g, g^c) = e(g,g)^c$$ 比较两个 $\mathbb{G}_T$ 元素即可 ⇒ DDH 容易。

但 CDH（"算 $g^{ab}$"）仍难 ⇒ 这种"DDH 易、CDH 难"的 group 叫 Gap Diffie-Hellman，是 BLS 签名安全证明的基础。

Q2: BLS12-381 中 $\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T$ 各自在哪里？

答：

• $\mathbb{G}_1 \subset E(\mathbb{F}_p)$，$E: y^2 = x^3 + 4$，元素 ~96 bytes (uncompressed) / 48 bytes (compressed)
• $\mathbb{G}2 \subset E'(\mathbb{F}{p^2})$，$E'$ 是 sextic twist；元素 192/96 bytes
• $\mathbb{G}T \subset \mathbb{F}{p^{12}}^*$，元素 4572 bit ≈ 572 bytes

子群阶都是 $r$（255-bit 素数）。

Q3: 解释 Miller loop 为什么是 $O(\log r)$ 复杂度。

答：Miller 用类似 double-and-add 标量乘的方式构造 $f_{r,P}$。每一步：

• doubling 一次：1 次切线 + 1 次乘法 + 1 次平方 in $\mathbb{F}_{p^k}$
• addition (若 bit=1)：1 次弦 + 1 次乘法

共 $\log_2 r$ 次循环 → $O(\log r)$ 次 $\mathbb{F}_{p^k}$ 操作。Optimal Ate 利用 Frobenius 把循环长度进一步缩到 $\log r / \varphi(k)$，对 BLS12-381 大约从 255 缩到 64 bit。

Q4: Final exponentiation 的作用是什么？

答：Tate pairing 输出在 $\mathbb{F}{p^k}^* / (\mathbb{F}{p^k}^*)^r$（商群）。两个 $f_{r,P}(Q)$ 表示同一 pairing 值若它们差一个 $r$-次方。Final exponentiation $(p^k-1)/r$ 把任何元素映到 $\mu_r$（$r$-阶单位根子群），给出唯一表示。

不做 final exp：失去双线性的精确等式，只能用 $\equiv$ in 商群。

Q5: 为什么 BLS12-381 比 BN254 更优？

答：

1. 安全性：BN254 的 $\mathbb{F}{p^{12}}$ ~ 3048 bit，但 Tower NFS 把 DLP 难度降到 ~100 bit；BLS12-381 的 $\mathbb{F}{p^{12}}$ ~ 4572 bit，仍达 128 bit。
2. 结构：BLS 曲线参数 $u$ 是稀疏 ("low Hamming weight")，让 Miller loop 更高效。
3. 生态：BLS12-381 被 Zcash/Eth2/Filecoin 采用，库（blst, py_ecc）成熟。
4. 缺点：BLS12-381 字段 381 bit（vs BN254 的 254）让基本运算稍慢，但安全收益更值得。

---

十二、明日预告

Day 186: 离散对数与困难问题 — 系统分类 DLP / CDH / DDH / BDH / SXDH 等假设，分析为何 secp256k1 安全（无 sub-exp 攻击）、为何 $\mathbb{F}_p^*$ 需要 3072 bit。

核心问题：Pollard rho、index calculus、NFS 各自适用什么群？

参考文献：

• Miller, "The Weil Pairing, and Its Efficient Calculation", J. Cryptology 2004.
• Vercauteren, "Optimal Pairings", IEEE Trans. Inf. Theory 2010.
• Galbraith, Mathematics of Public Key Cryptography, Ch. 26.
• Boneh, Lynn, Shacham, "Short Signatures from the Weil Pairing", 2001.