【密码学】密码学数学基础：双线性配对

又到了枯燥乏味的数学打基础时间，本文不会有太深的讲解，毕竟是我本人对此概念的理解（我的理解不太深，还请大家见谅），如果想系统性的学习此知识，推荐看相关数学教材。免责声明结束后，简单说下本文的行文结构。要想理解双线性配对是个啥？我觉得先得知道线双线性映射是什么，要想知道双线性映射是什么，就要先理解线性映射是什么。

文章无法避免严谨（枯燥）的数学表达方式，但求尽量用我的理解，说人话通俗表达。

一、线性映射与线性函数

（1）线性映射的定义

线性映射（Linear Map）是从一个向量空间到另一个向量空间的映射，它保持了向量加法和标量乘法的线性性质。如果这个映射是从一个向量空间到另一个向量空间的函数，我们通常称它为线性函数。

严谨表达来了，给定两个向量空间 $V$ 和 $W$ ，定义在同一个标量域 $F$ 上，一个函数 $f:V\rightarrow W$ 被称为线性函数，如果它满足以下两个条件：

加法性：对于所有 $v,{v}' \in V$ ，有 $f(v+{v}')=f(v)+f({v}')$
标量乘法：对于所有 $v \in V$ 和所有标量 $a \in F$ ，有 $f(av)=af(v)$

在坐标表示中，线性函数可以用矩阵表示，且它的图形通常是一条直线（在一维情况下）或者一个平面/超平面（在更高维度的情况下）。

（2）线性函数与线性映射什么关系

在大多数数学文献和教材中，线性函数和线性映射是同义词。因此，当我们在讨论从一个向量空间到另一个向量空间的映射时，线性函数和线性映射可以互换使用。

二、双线性映射与双线性函数

（1）双线性映射的定义

双线性映射（Bilinear Map）是从两个向量空间的笛卡尔积到第三个向量空间的映射，它同时关于两个输入变量都是线性的。如果这个映射特别关注的是从两个向量空间到第三个向量空间的函数，我们通常称它为双线性函数。

严谨表达来了，设 $V, W$ 和 $U$ 是三个向量空间，并且假设它们都定义在一个相同的标量域 $F$ 上。一个从 $V\times W$ 到 $U$ 的映射 $B:V\times W\rightarrow U$ 称为双线性映射，如果它同时关于 $V$ 和 $W$ 中的变量是线性的。具体来说，如果对于所有 $v,{v}'\in V$ ， $w,{w}'\in W$ 和所有标量 $a,b\in F$ ，映射 $B$ 满足以下条件：

对第一个变量的线性：
- 加法性： $B(v+{v}',w)=B(v,w)+B({v}',w)$
- 标量乘法： $B(av,w)=aB(v,w)$
对第二个变量的线性：
- 加法性： $B(v,w+{w}')=B(v,w)+B(v,{w}')$
- 标量乘法： $B(v,bw)=bB(v,w)$

换句话说，对于固定的 $w\in W$ ，映射 $v \mapsto B(v,w)$ 是从 $V$ 到 $U$ 的线性映射；

同样地，对于固定的 $v\in V$ ，映射 $w \mapsto B(v,w)$ 也是从 $W$ 到 $U$ 的线性映射。

内积和矩阵乘法就是双线性函数，在欧几里得空间中，两个向量的内积（点积）是一个双线性函数。当我们将两个向量分别视为行向量和列向量时，它们的乘积就是一个双线性函数的例子。

（2）双线性映射和线性映射的关系

从某种意义上说，双线性映射可以看作是两个独立线性映射的组合。

联系：线性映射和双线性映射都保持了线性性质。线性映射保持了一个向量空间到另一个向量空间的线性性质，而双线性映射保持了两个向量空间到第三个向量空间的线性性质。

区别：线性映射涉及单个向量空间到另一个向量空间的映射，而双线性映射涉及两个向量空间到第三个向量空间的映射，并且它在两个输入变量上都是线性的。

三、双线性配对的定义

双线性配对（Bilinear Pairing）是一种特殊的双线性函数，它通常涉及两个向量空间（或更一般的代数结构）和一个输出标量值的代数结构。双线性配对不仅保持了双线性函数的特性，还具有非退化性和计算可行性。

设 $G_1$ 和 $G_2$ 是定义在同一标量域 $F$ 上的两个向量空间（或更一般的代数结构，如群），而 $G_T$ 是另一个定义在相同标量域 $F$ 上的向量空间或代数结构。一个函数 $e:G_1 \times G_2\rightarrow G_T$ 被称为双线性配对，如果它满足以下条件：

双线性：对于固定的 $g_2\in G_2$ ，映射 $g_1 \mapsto e(g_1,g_2)$ 是从 $G_1$ 到 $G_T$ 的线性映射；同样地，对于固定的 $g_1\in G_1$ ，映射 $g_2 \mapsto (g_1,g_2)$ 也是从 $G_2$ 到 $G_T$ 的线性映射。
非退化性：存在 $g_1\in G_1$ 和 $g_2\in G_2$ 使得 $e(g_1,g_2)\neq 1$ ，其中 $1$ 是 $G_T$ 中的单位元。这意味着配对不是恒等的零映射。
计算可行性：对于所有 $g_1\in G_1$ 和 $g_2\in G_2$ ，配对 $e(g_1,g_2)$ 是有效计算的。

四、椭圆曲线上的双线性配对

（1）椭圆曲线上的双线性配对

椭圆曲线上的双线性配对是在椭圆曲线 $E$ 上定义的一种双线性配对，它将两个椭圆曲线上的子群 $G_1$ 和 $G_2$ 映射到一个特定的代数结构 $G_T$ ，通常是有限域的一个子群。

稍微回顾一下椭圆曲线，椭圆曲线 E 定义在一个有限域 Fq 上，其中 q 是一个素数或素数的幂。椭圆曲线上的点构成一个阿贝尔群，其中群操作是点的加法。

更多关于椭圆曲线的内容可以看我之前的文章：【密码学】椭圆曲线密码体制（ECC）

（2）举例和应用

Weil 配对和 Tate 配对是在椭圆曲线上常见的双线性配对。

椭圆曲线上的双线性配对在密码学中有许多应用，包括身份基加密（IBE）、属性基加密（ABE）、短签名、非交互式零知识证明等，这些应用依赖于双线性配对的独特性质来增强安全性或简化加密协议的设计。

五、总结

线性映射与线性函数是保持向量加法和标量乘法线性性质的最基础概念。双线性映射与双线性函数扩展了线性函数的概念，涉及两个向量空间，并保持了关于两个输入变量的线性性质。双线性配对是双线性函数的一个特例，它具有非退化性和计算可行性，适用于密码学等多种应用场景。椭圆曲线上的双线性配对是在椭圆曲线这一特定代数结构上定义的双线性配对，它在密码学中有着广泛的应用。