Bilinear Maps

双线性对是一个七元组$(p,G_1,G_2,G_T,e,g,h)$，其中

  • $p$：素数，其长度与安全等级有关，通常取$|p|=256$
  • 三个循环群$G_1,G_2,G_T$：三个群的阶均为$p$，其中$G_1$的生成元为$g$，$G_2$的生成元为$h$，$G_1,G_2$为源群，$G_T$为目标群（记群的单位元为$1$）
  • 映射$e:G_1 \times G_2 \rightarrow G_T$：满足下列两个性质
  1. 非退化性：$e(g,h)\neq 1$
  2. 双线性性：对于任给$a,b\in Z_p$，有$e(g^a,h^b)=e(g,h)^{ab}$
  3. 可计算性：存在一种有效计算$e$的算法

在2005年以前，两个源群都是加法循环群，现在的基本上默认为乘法循环群（不过椭圆曲线的双线性群构造中两个源群是加法群）

注意到，目标群的阶为素数$p$，因此将源群的两个生成元的映射到目标群，得到的是目标群的生成元

Generic Bilinear Group Operations

  • 比较：就是普通比较，将两个元素按比特比较
  • 高效算法：比如决定成员$u\in G_1$，群上计算$u \cdot v \in G_2$，计算双线性映射$e(u,v)$

Types of bilinear maps

PBC中（Pairing-Based Cryptography），通常取两个源群为有限域$F_q(F_{q^e})$上椭圆曲线的子群，目标群是$F^*_{q^k}$上的乘法子群

此外还有一些特殊的类别，如下

  1. 当$G_1=G_2$时，称这个双线性群是对称双线性群（Symmetric Bilinear Group），否则为非对称
  2. 当为非对称双线性群时，其有一个可以高效计算的同构$\Psi:G_2\rightarrow G_1$
  3. 当为非对称双线性群时，不存在这样的高效计算的同构

后续的内容中主要关注第三类，即主要关注不存在高效计算的同构的非对称双线性群

Efficiency

对于群元素的表示，通常记$a\in Z_p,u\in G_1,v\in G_2,w\in G_T$，且有$|a|<|u|<|v|<|w|$

对于计算开销，三个循环群$G_1,G_2,G_T$乘法和指数运算的开销依此递增，双线性映射的开销最大（大于前面的所有）

Getting used to bilinear maps

一些小练习帮助你进一步熟悉双线性对

  • 表达式$e(u,v)e(u,w)=y^az$，则$u,v,w,y,z,a$分别属于哪个群？

  • 化简下列表达式：

    1. $e(g^a,h)e(g^b,h)$
    2. $e(g,h^a)e(g^b,h)$
    3. $e(g^a,h^{-b})e(u,v)e(g,h)^c$
    4. $\prod^n_{i=1}e(g,h^{a_i})^{b_i}$
    5. $e(u,v)e(u,w)$
    6. $e(u,v^a)e(u^b,v)$
    7. $e(g^a,v^{-b})e(f,w)e(u,v)^c$
    8. $\prod_{i=1}^n e(u^a,v_i^b)^{\frac{c_i}{ab}}$
  • 比较$e(g^{a+b},h),e(g,h^{a+b}),e(g,h)^{a+b}$三者哪个更简化？==根据前面提到的，$G_1$上的指数运算最快，$G_T$上的指数运算慢，最慢的是双线性映射，因此第一个计算最快，不过如果$e(g,h)$在计算中会频繁用到，则可以考虑提前计算，则其计算转化为$G_T$上的指数运算z==

证明：若$e(u,v)=1$，则$u=1$或$v=1$

Usage in cryptography

如果说双线性对是对称的，则配对可以用来将一个群上的难题归约到另一个群上的，不同的但通常而言更简单的问题

例如在使用了Weil对或Tate对的群中，广义的CDH问题被认为是困难的，但更简单的DDH问题可以使用配对函数来解决，因为假设群中这两个问题的难度不同，因此第一个群被称为间隙群

KZG密码承诺方案中使用了基于配对的加密技术

BLS数字签名方案也使用双线性对

基于配对的密码学依赖于与椭圆曲线密码学不同的核心假设，椭圆曲线密码学更古老，研究时间更长