配对计算与优化策略

### 配对计算与优化策略 #### 1. 配对友好普通曲线的寻找策略 在寻找配对友好普通曲线时，需要满足以下条件： 1. $q$ 是素数或素数幂。 2. $p$ 是素数。 3. $p$ 整除 $q + 1 - t$。 4. $p | (q^k - 1)$ 但 $p \nmid (q^i - 1)$ 对于 $i < k$。 5. $4q = t^2 + Ds^2$，其中 $D$ 和 $s$ 是整数。 寻找配对友好普通曲线的一般策略步骤如下： 1. 固定嵌入度 $k$，找到整数 $t$、$p$ 和 $q$，使得椭圆曲线 $E/\mathbb{q}$ 的迹为 $t$，$E(\mathbb{q})$ 有一个大素数阶 $p$ 的子群且嵌入度为 $k$。 2. 使用复乘法（CM）算法找到 $E/\mathbb{q}$ 的显式形式。 以下是一些使用该策略创建的普通曲线类型，这些曲线在达到标准比特安全级别时非常有用，同时允许相对高效的实现： | 构造类型 | 嵌入度 | | --- | --- | | MNT（Miyaji, Nakabayashi and Tanako） | $k = 3, 4, 6$ | | Freeman | $k = 10$ | | BN（Baretto - Naehrig） | $k = 12$ | | BW（Brezing - Weng） | $18 \nmid k$ | #### 2. 配对友好曲线参数的相对效率 通常用于比较基于配对算法参数相对效率的一个参数是有限域 $\mathbb{q}$ 的大小相对于素数阶子群大小 $p$ 的比例，用 $\lambda$ 表示，定义为： $\lambda = \frac{\log q}{\log p}$ 一般来说，$\lambda$ 值较小的参数选择可以提供更快的椭圆曲线运算速度，因此可能比 $\lambda$ 值较大的参数选择更受青睐。但这不应作为一个严格的设计原则，因为其他权衡可能比更快的椭圆曲线运算所带来的额外速度更重要。例如，当 $\lambda$ 接近 1 时，可能难以找到一个索利纳斯素数 $p$，而 $p$ 为索利纳斯素数时在配对计算中带来的额外速度可能会弥补因 $\lambda$ 值较大而可能需要的稍慢的椭圆曲线运算。对于 $\lambda = 1$，可用于达到标准比特强度级别的 $p$、$q$ 和 $k$ 的理想值如下表所示： | 嵌入度 $k$ | 比特强度 | $p$ 的大小 | $q^k$ 的大小 | | --- | --- | --- | --- | | 6 | 80 | 171 | 1,026 | | 9 | 112 | 228 | 2,052 | | 12 | 128 | 256 | 3,072 | | 20 | 192 | 384 | 7,680 | | 30 | 256 | 512 | 15,360 | 目前的研究尚未找到满足上述所有要求的曲线，以下是使用已知曲线目前能达到的最接近理想值的参数： | 嵌入度 $k$ | 比特强度 | $p$ 的大小 | $\lambda$ | $q^k$ 的大小 | 构造类型 | | --- | --- | --- | --- | --- | --- | | 6 | 80 | 171 | 1 | 1,026 | MNT | | 10 | 112 | 224 | 1 | 2,240 | Freeman | | 12 | 128 | 256 | 1 | 3,072 | BN | | 19 | 192 | 384 | $\frac{10}{9}$ | 8,113 | BW | | 29 | 256 | 512 | $\frac{15}{14}$ | 15,921 | BW | #### 3. 消除无关因素 在 Tate 配对计算中，有些因素在最终指数运算后会简化为 1，消除这些无关因素可以使 Tate 配对的计算更加高效。 ##### 3.1 消除随机分量 Tate 配对 $e(P, Q)$（其中 $P$ 是阶为 $n$ 的点）的计算方式为 $e(P, Q) = f_P(A_Q)$，其中 $f_P$ 是一个有理函数，其除子 $\text{div}(f_P)$ 等价于 $n(P) - n(O)$，$A_Q$ 是一个等价于 $(Q) - (O)$ 的除子。为避免处理无穷远点 $O$，可以使用等价于 $n(P) - n(O)$ 的除子，如 $n(P + R) - n(R)$ 来计算 $f_P'$，其中 $R$ 是 $E(\mathbb{q})$ 中随机选择的点。 但实际上，由于最终指数运算会消除 $f_P'(A_Q)$ 的一些分量，使用随机点创建等价除子并非必要。若 $p | (q^k - 1)$，可以利用费马小定理找到可以忽略的项，因为这些项在最终指数运算后会变为 1。 简化后的 Tate 配对计算算法如下： ```plaintext Algorithm 12.1: SimplifiedTatePairing (simplified Miller’s algorithm for computing the Tate pairing) INPUT: Elliptic curve E/
q, P ∈E(
q )[n] with n = ∑ t i = 0 bi 2i, Q ∈E(
qk ) OUTPUT: e(P, Q ) 1. f ←1, t ←log2 n, S ←P 2. For i ←t −1 down to 0 3. f ←f 2 uS, S (Q ) v2, S (Q ) 4. S ←2S 5. If bi = 1 6. f ←f uS, P (Q ) vS + P (Q ) 7. S ←S + P 8. Return f ``` 例如，对于椭圆曲线 $E/\mathbb{11} : y^2 = x^3 + x$，$P = (5, 8) \in E(\mathbb{11})[3]$，$Q = (4, 3i) \in E(\mathbb{11^2})$，可以计算出 $f_P(x, y) = y + 9x + 2$，$f_P(Q) = 5 + 3i$，$f_P(Q)^{(q^k - 1)/p} = (5 + 3i)^{40} = 5 + 3i$。 ##### 3.2 消除扩展域除法 在某些情况下，当嵌入度 $k$ 为偶数时，可以用复共轭代替算法 12.1 中步骤 3 和 6 的扩展域除法，这样在最终指数运算后能得到正确结果。这是因为在大有限域中，求逆运算通常非常昂贵。 将 $\mathbb{q^k}$ 视为 $\mathbb{q^d}$（$d = k/2$）的 2 次扩展域，元素可以表示为 $a + ib$，其中 $a$ 和 $b$ 是 $\mathbb{q^d}$ 中的元素。通过复共轭进行简化后的算法如下： ```plaintext Algorithm 12.2: SimplifiedTatePairingConjugation (simplified Miller’s algorithm for computing the Tate pairing replacing extension field divisions with complex conjugation) INPUT: Elliptic curve E/
q, P ∈E(
q )[n] with n = ∑ t i = 0 bi 2i, Q ∈E(
qk ) OUTPUT: e(P, Q ```