双线性映射 (Bilinear Mapping)

双线性映射又称为 双线性对 (Bilinear Pairing) ，属于椭圆曲线密码学中的工具。 早期的双线性映射多用于密码分析中，比如构造针对椭圆曲线密码学攻击方案。 随着对基于身份的密码学深入研究，双线性映射的构造顺势派上了用场。

2001年，Dan Boneh 和 Matt Franklin 使用双线性映射构造了基于身份的加密方案，此方案构造十分简洁，已成为后来构造基于身份密码方案的模板。 而基于双线性映射构造出的方案也百花齐放，各种稀奇古怪的协议蜂拥而现，时至今日余温不减。

其实如果读过两三篇有关双线性映射的文章，就知道它的性质没那么复杂，无非就是三条：

设 $\mathbb{G}_1$，$\mathbb{G}_2$ 是基于椭圆曲线上的阶为素数 $q$ 的加法循环群，$\mathbb{G}_T$ 是阶为素数 $q$ 的乘法循环群，如果函数 $\hat{e}:\mathbb{G}_1\times \mathbb{G}_2 \rightarrow \mathbb{G}_T$ 满足以下三个性质，那么就称它为双线性对。

1. 双线性：$\forall P\in\mathbb{G}_1, Q\in\mathbb{G}_2,\forall a,b\in\mathbb{Z}_q^*$，总是有 $\hat{e}(aP,bQ)=\hat{e}(P,Q)^{ab}$ 成立；
2. 非退化性：$\exists P\in\mathbb{G}_1, Q\in\mathbb{G}_2$，满足 $\hat{e}(P,Q)\neq 1$；
3. 可计算性：$\forall P\in\mathbb{G}_1, Q\in\mathbb{G}_2$，总存在概率多项式时间算法计算出 $\hat{e}(P,Q)$。

根据 $\mathbb{G}_1$ 与 $\mathbb{G}_2$ 是否为同一个群，可以划分为 对称式与非对称式。 最重要的还是 双线性 这条性质，几乎所有的构造都是依赖于此。比如 三方一轮的密钥协商¹：

其实在知道这些性质后，就可以开始着手将双线性映射看做一个“黑盒子”式的工具进行使用了。 但是，如果在不清楚它背后的构造时，即使能理论上构造出来一个自洽的方案，放到实际中也可能只是一个 "naive protocol"。

---

1. 双线性映射的三种形式

对于双线性映射而言，根据 $\mathbb{G}_1$ 与 $\mathbb{G}_2$ 的关系，可以分成三类：

1. $\mathbb{G}_1=\mathbb{G}_2$
2. $\mathbb{G}_1\neq\mathbb{G}_2$，同时存在一个同态映射 $\phi:\mathbb{G}_2\rightarrow\mathbb{G}_2$
3. $\mathbb{G}_1\neq\mathbb{G}_2$，但是 $\mathbb{G}_1$ 与 $\mathbb{G}_2$ 之间不存在同态的关系

---

1. Menezes, A. (2009). An introduction to pairing-based cryptography. Recent trends in cryptography, 477, 47-65. ↩