What is pairing?

 最近在搞中期报告，要用到一些双线性配对密码学的知识。我们都知道双线性配对满足一些计算性质，例如$e(u^a,v^b)=e(u,v)^{ab}$，利用双线性配对可以构造很多密码学算法，当然也是身份加密的基础。然而，双线性配对到底是啥呢？咋来的呢？具体应用是什么呢？

 首先要引入一些概念。

 群。一种代数结构，由一组元素和二元运算*组成。群必须满足以下四个条件：

• 封闭性：对于群中的任意两个元素 a 和 b，a*b 仍在群中。
• 结合性：对于群中的任意元素 a、b 和 c，有 (a∗b)∗c=a∗(b∗c)。
• 单位元：存在一个单位元 e，使得对于任何元素 a，都有 a∗e=a。
• 逆元：对于群中的每个元素 a，存在一个元素 b，使得 a∗b=e。

 离散对数问题（DLP）。给定一个加法群 G，P 是 G 的生成元，群的阶为 n，以及一个群中的元素 Q。DLP 是要求找到一个整数 $x \in [0,n−1]$，使得：Q=x*P。当 n 很大的时候，而且群如果是精心选择的话，DLP 很困难。

 Diffie-Hellman 问题（DHP）。给定 P、aP 和 bP 的情况下得到 abP。很容易看出来 DHP 比 DLP 简单，因为多了一些信息。

pairing 是怎么来的？

 给一个域 K 上的椭圆曲线 E：$y_2 + a_1xy + a_3y = x_3 + a_2x_2 + a_4x + a_6$，其中 $a_1,a_2,a_3,a_4,a_6 \in K$。E(K) 是一个点集，由无穷远处的点和满足上式的点 $(x, y) \in K * K$ 组成。假设 K 是阶数为 q、特征为 p 的有限域 $F_q$，那么 E(K) 中的元素数量$#E(K)$满足：${(\sqrt{q}-1)}^2 \leq #E(K) \leq {(\sqrt{q}+1)}^2$（Hasse 定理），可以推导出$#E(K) = q + 1 − t$，其中$|t| \leq 2 \sqrt{q}$。如果 $p | t$ ，则 E 被称为超奇异，否则 E 是普通的。如果 q 是素数，那么对于每个 t，$|t| < 2 \sqrt{q}$，都存在一条在 $F_q$ 上定义的椭圆曲线 E，其中 $#E(F_q) = q + 1 − t$。

 如果 p > 3，则 E 转换为：$y^2 = x^3 + ax + b$，其中 $a, b \in K$ 且 $4a^3 +27b^2 \ne 0$。如果 E 是超奇异且 p = 3，则 E 转换为：$y^2 = x^3 + ax + b$，其中 $a, b \in K$ 且 $b \ne 0$。如果 E 是超奇异且 p = 2，则转换为：$y^2 + cy = x^3 + ax + b$，其中 $a, b, c \in K$ 且 $c \ne 0$。下面是椭圆曲线的计算规则：

 令 $P \in E(K)$ 为素数阶 n 的点，并假设 gcd(n, q) = 1。P 中的椭圆曲线离散对数问题（ECDLP）如下：给定 $P,Q \in〈P〉$，找到整数 $l$ 使得 $Q = lP$。已知用于求解 ECDLP 的最佳通用算法是 Pollard 的 rho 方法，时间复杂度为 $O(\sqrt{n})$。Weil 和 Tate 配对可用于将 ECDLP 实例转换为扩展域 $F{q^k}$ 中的离散对数问题。令 E 为在 $F_q$ 上定义的椭圆曲线，$P \in E(F_q)$ 为素数阶 n 的点。假设 gcd(n, q) = 1。则 P 的嵌入度是满足 $n|q^k-1 $ 的最小正整数 k。如果嵌入度 k 较小，则用于求解 $F{q^k}$ 中的 DLP 可能比用于求解 ECDLP 更快。

 人们一致认为，低嵌入度的椭圆曲线不应在离散对数协议中使用，因为会受到 Weil 和 Tate 配对攻击。然而，低嵌入度椭圆曲线现在又重新流行起来，因为它们可以实现基于配对的协议。

 那什么是 Weil 和 Tate 配对攻击呢？令 E 是在 $K = Fq$ 上定义的椭圆曲线，并令 $K’$ 表示 K 的代数闭包，用 $E(K’)$ 表示 E。E 上的除数是 $D = \sum{P \in E}{n_P(P)}$，其中 $n_P$ 是整数集。如果对于 K 的所有自重构 $\alpha$，满足 $D^\alpha=\sum_P{n_P(P^\alpha)}=D$，$P^\alpha=(\alpha(x), \alpha(y))$，那么就叫 D 在 K 上定义了。在 K 上定义的所有除数的集合用 $Div_K (E)$ 表示。

To be continued…