双线性映射

【原创】
姓名：王顺其；学号：20181214438；学院：广州研究院

【嵌牛导读】密码学在我们的生活中越来越重要，面对各种“攻击”，密码技术也不断发展，本文将带你了解一下加密技术中的双线性映射。

【嵌牛鼻子】密码学双线性映射

【嵌牛提问】你觉得算个线性映射能用到那些场景中？双线性映射有何优缺点？

【嵌牛正文】

1 离散对数系统

1.1 指标

定义：设 $p$ 是一素数， $a$ 是 $p$ 的原本根，则 $a,a^2,\ldots,a^{p-1}$ 产生出的 $1\thicksim p-1$ 之间所有的值，且每一值只出现一次，即对于 $\forall b \in\{1,\ldots,p-1\}$ 都唯一存在 $i(1\leq i\leq p-1)$ ，使得 $b\equiv a^i\:mod\:p$ 。称 $i$ 为模 $p$ 下以 $a$ 为底 $b$ 的指标，记作 $i=ind_{a,p}(b)$ 。

性质：（1） ${ind}_{a,p}(1) = 0$ ；
       （2） ${ind}_{a,p}(a) = 1$  。
定理：若 $a^z\equiv a^p\:mod\:p$ ，其中 $p$ 为素数， $a$ 为 $p$ 的原本根，则有 $z\equiv q\:mod\:\varphi(p)$ 。

性质：（3） ${ind}_{a,p}(xy)=[{ind}_{a,p}(x)+{ind}_{a,p}(y)]\:mod\:\varphi(p)$ ；
        （4）${ind}_{a,p}(y^r)=[r\times{ind}_{a,p}(y)]\:mod\:\varphi(p)$ 。

1.2 离散对数（DLP）

设 $p$ 是一素数， $a$ 是 $p$ 的原本根，则 $a,a^2,\ldots,a^{p-1}$ 产生出的 $1\thicksim p-1$ 之间所有的值，且每一值只出现一次，即对于 $\forall b \in\{1,\ldots,p-1\}$ 都唯一存在 $i(1\leq i\leq p-1)$ ，使得 $b\equiv a^i\:mod\:p$ 。称 $i$ 为模 $p$ 下以 $a$ 为底 $b$ 的离散对数，记作 $i\equiv {log}_a(b)(mod\:p)$ 。

当 $a、p、i$ 已知时，用快指数算法可以比较容易的地求出 $b$ ，但是如果已知 $a、b$ 和 $p$ ，求 $i$ 则非常困难。目前已知的最快的求离散对数算法的事件复杂度为： $O(exp(ln\:p)^{\frac{1}{3}}ln(ln\:p)^{\frac{2}{3}})$ 所以当 $p$ 很大时，该算法也不可行。

2 双线性映射

设 $q$ 是一大素数， $\mathbb{G}_1$ 和 $\mathbb{G}_2$ 是两个阶为 $q$ 的群，其上的运算分别为加法和乘法。 $\mathbb{G}_1$ 到 $\mathbb{G}_2$ 的双线性映射 $e:\mathbb{G}_1\times\mathbb{G}_1\rightarrow\mathbb{G}_2$ ，满足下面的性质：

（1）双线性：如果对任意 $P,Q,R\in \mathbb{G}_1$ 和 $a,b\in Z$ ，有 $e(aP,bQ)=e{(P,Q)}^{ab}$ ，或 $e(P+Q,R)=e(P,R)\cdot(Q,R)$ 和 $e(P,Q+R)=e(P,Q)\cdot(P,R)$ ，那么就称该映射为双线性映射。

（2）非退化性：映射不把 $e:\mathbb{G}_1\times\mathbb{G}_1$ 中所有元素对（即序偶）映射到 $\mathbb{G}_2$ 中的单位元。由于 $\mathbb{G}_1、\mathbb{G}_2$ 都是阶为素数的群，这意味着：如果 $P$ 是 $\mathbb{G}_1$ 的生成元，那么 $e(P,P)$ 就是 $\mathbb{G}_2$ 的生成元。

（3）可计算性：对任意 $P,Q\in \mathbb{G}_1$ ，存在一个有效算法计算 $e(P,Q)$ 。

3 Diffie-Hellman 问题（DHP）

3.1 Diffie-Hellman 密钥交换

Diffie-Hellman 密钥交换过程，其中 $p$ 是大素数， $a$ 是 $p$ 的本原根， $p$ 和 $a$ 作为公开的全程元素。用户A选择一个保密的随机整数 $X_A$ ，并将 $Y_A =a^{X_A}\:mod\:p$ 发送给用户B。类似的，用户B选择一个保密随机数 $X_B$ ，并将 $Y_B =a^{X_B}\:mod\:p$ 发送给用户A。然后A和B分别由 $K=Y_B^{X_A}\:mod\:p$ 和 $K=Y_A^{X_B}\:mod\:p$ 计算出的就是共享密钥。

因为 $X_A,X_B$ 是保密的敌手只能得到 $p,a,Y_A,Y_B$ ，想要得到 $K$ ，则必须得到 $X_A,X_B$ 中的一个，这意味着要解离散对数。因此求 $K$ 是不可行的。

3.2 q-Strong Diffie-Hellman（q-SDH）

假设 $g$ 是 $\mathbb{G}$ 的生成元， $a\in\mathbb{Z}_p$ ，我们说如果给定 $q+1$ 元组 $(g,g^a,g^{a^2},\ldots,g^{a^q})$ ，计算一个对 $(g^{1/{a+x}},x)\qquad x\in\mathbb{Z}_p^*$ 是困难的。