椭圆曲线与泰特配对：密码学中的关键概念

### 椭圆曲线与泰特配对：密码学中的关键概念 #### 椭圆曲线的性质 在椭圆曲线的研究中，$j$-不变量是一个重要的概念。对于$j \in \mathbb{q}$，且$j \neq 0$，$j \neq 1728$，设$k = \frac{j}{1728 - j}$，那么椭圆曲线$E / \mathbb{q}: y^2 = x^3 + 3kc^2x + 2kc^3$（其中$c \in \mathbb{q}$）具有$j$-不变量$j$。 变量变换$a \to v^2a$和$b \to v^3b$时$j$-不变量不变，由此引出了二次扭转的定义。设$E / \mathbb{q}: y^2 = x^3 + ax + b$是椭圆曲线，$v \in \mathbb{q}^*$是$\mathbb{q}^*$中的二次非剩余，则$E' / \mathbb{F}: y^2 = x^3 + v^2ax + v^3b$称为$E$的二次扭转。在这种情况下，$E$和$E'$在$\mathbb{q}$的二次扩张上同构，但在$\mathbb{q}$本身不同构。例如，在$\mathbb{Z}_5$上，$v = 2$是二次非剩余，$E': y^2 = x^3 + 4x + 3$是$E: y^2 = x^3 + x + 1$的二次扭转。 除了二次扭转，对于某些椭圆曲线$E / \mathbb{q}$，还可以创建更高次数的扭转。当$E': y^2 = x^3 + a'x + b'$，其中$a' = v^{4/d}a$，$b' = v^{6/d}b$，且$v$是$d$次根但不是低于$d$次的根时，我们称其为$d$次扭转。这种扭转在$\mathbb{q}_d$（$\mathbb{q}$的$d$次扩张）上与$E$同构。以下是不同次数扭转的椭圆曲线形式总结： | 扭转次数 $d$ | $E$ 的形式 | $E'$ 的形式 | | --- | --- | --- | | 2 | $y^2 = x^3 + ax + b$ | $y^2 = x^3 + v^2ax + v^3b$ | | 3 | $y^2 = x^3 + b$ | $y^2 = x^3 + vb$ | | 4 | $y^2 = x^3 + ax$ | $y^2 = x^3 + vax$ | | 6 | $y^2 = x^3 + b$ | $y^2 = x^3 + vb$ | 不同次数扭转下椭圆曲线上点的对应关系如下： | 扭转次数 $d$ | $E$ 上的典型点 | $E'$ 上的对应点 | | --- | --- | --- | | 2 | $(x, y)$ | $(vx, v^{3/2}y)$ | | 3 | $(x, y)$ | $(v^{1/3}x, v^{1/2}y)$ | | 4 | $(x, y)$ | $(v^{1/2}x, v^{3/4}y)$ | | 6 | $(x, y)$ | $(v^{1/3}x, v^{1/2}y)$ | 从$E'$到$E$的映射$\psi_d$在实现基于配对的算法中很有用，这些映射会将输出的维度增加$d$倍。例如，在$\mathbb{Z}_{11}$上，$E': y^2 = x^3 + 10$是$E: y^2 = x^3 + 1$使用二次非剩余$v = 10$创建的二次扭转，点$(2, 3) \in E(\mathbb{Z}_{11})$，对应的点$(v \cdot 2, v^{3/2} \cdot 3) = (10 \cdot 2, 10i \cdot 3) = (9, 8i) \in E'(\mathbb{Z}_{11})$。 #### 扭曲映射 设$E / \mathbb{q}$是椭圆曲线，$n$是与$q$互质的整数，$P$是$E(\mathbb{q})$中阶为$n$的点。关于$P$的扭曲映射$\psi$是一个自同态，它将点$P$映射到与$P$线性无关的点$\psi(P)$。以下是一些有用的扭曲映射总结： | 域 | 曲线 | 扭曲映射 | $\#E$ | | --- | --- | --- | --- | | $\mathbb{Z}_p$ | $y^2 = x^3 + ax$ | $\psi(x, y) = (-x, iy)$ | $p + 1$ | | $\mathbb{Z}_p$ | $y^2 = x^3 + ax$ | $\psi(x, y) = (\alpha x, y)$，$\alpha \neq 1$，$\alpha^3 = 1$ | $p + 1$ | | $\mathbb{Z}_{p^2}$ | $y^2 = x^3 + ax$，$a \in \mathbb{Z}_p$，$r^2 = a$，$r \in \mathbb{Z}_{p^2}$，$\omega^3 = r$，$\omega \in \mathbb{Z}_{p^6}$ | $\psi(x, y) = (\frac{x^p}{r^{(2p - 1)/3}}, \frac{y^p}{r^{p - 1}})$ | $p^2 - p + 1$ | 扭曲映射在实现许多基于身份的加密（IBE）算法中很有用，但它的应用主要限于超奇异曲线。对于超奇异椭圆曲线$E / \mathbb{q}$，如果$P \in E(\mathbb{q})[n]$且$n$与$\mathbb{q}$的特征互质，则总是存在关于$P$的扭曲映射；而对于普通椭圆曲线$E / \mathbb{q}$，如果$P \in E(\mathbb{q})[n]$，$n$与$\mathbb{q}$的特征互质且$E[n] \nsubseteq E(\mathbb{q})$，则不存在关于$P$的扭曲映射。 ##