导 读
如果关心近年的密码学成果，可以发现双线性对作为一个基础的密码学工具频频出现。
双线性对是一种二元映射，它作为密码学算法的构造工具，在各区块链平台中广泛应用，比如零知识证明、聚合签名等技术方案大多基于双线性对构造得来。
本次将分为上、下两个篇章讲解双线性对在密码学中的应用。
本文为上篇入门篇，会从概念介绍、发展历程、实际应用三个方面展开说明，下篇为进阶篇，将从原理层面深入剖析。
双线性对的研究历程
▲ 1946年作为一个数学工具被提出（Weil对）
1946年双线性对首先被法国数学家Weil提出并成为代数几何领域重要的概念和研究工具。
在最初的时候，双线性对的概念并非为了密码学的研究，甚至Weil在提出双线性对时现代密码学还未成为系统的科学（3年后C.E.香农发表著名论文《保密系统的通信理论》奠定现代密码学理论基础，而公钥密码学的发展更在30年之后）。
▲ 1996年Menezes、Okamoto和Vanstone提出利用双线性对将ECDLP问题规约到DLP问题的MOV攻击
在19年火热的电影《罗小黑战记》中，主人公拥有控制自己“领域”的能力。电影中的“领域”指自己专有的一个空间，在此空间中可以主宰一切。
不严谨的说，双线性映射的功能也有几分相似——虽然攻击椭圆曲线系统在离散数域解决起来很难，但是如果被映射到特定的扩域从而规约为一般的离散对数问题，解决起来就相对容易。
但与攻击椭圆曲线系统的目的恰恰相反，MOV（一种攻击手段，详细说明见文末）最终促进了椭圆曲线密码学的发展。
这当然也是密码学家去研究攻击方法的本意——毕竟攻和防从来都是对立统一的两个方面而已。
MOV攻击并非能作用于全部的椭圆曲线，而是只能对参数满足一定条件的曲线进行攻击。这促使人们在选择椭圆曲线参数时更加谨慎，更加注重抗MOV攻击。
今天我们再选用椭圆曲线参数时都会考虑避开MOV攻击的条件从而使所选的参数更安全。
例如国标《SM2椭圆曲线公钥密码算法》就充分重视了受到MOV攻击的可能性，不仅在第一部分《总则》中用附录A的部分篇幅介绍验证曲线参抗MOV攻击的方法，而且也在第五部分《参数定义》中给出了安全曲线的推荐参数。
▲2000年双线性对开始在密码学领域得到重视，成果有基于身份的密码体制（IBE）、三方一轮密钥协商、BLS签名算法等
基于身份的密码体制是公钥密码学的一个研究方向，其特点是直接用标识用户身份的字符串作为公钥。大家熟悉的国密SM9算法就属于该类算法，这是目前国产密码算法中唯一一个基于双线性对的密码算法。
三方一轮密钥协商是一种可以在一轮交互内完成三方的密钥协商的密钥协商协议，效率高于DH密钥协商。
传统的DH密钥协商可以完成两两之间的密钥协商。虽然能够通过两两之间多轮协商完成三方之间的密钥协商，但是增加了通信复杂度。
基于双线性对能够在三方之间通过一轮通信完成密钥协商，大大降低了通信复杂度。
BLS签名是Boneh、Lynn和Shacham三人基于双线性映射构造的短签名方案，其特性之一就是能用于构造聚合签名。
除了上述的代表成果，双线性对在隐私保护方面、可证明执行、可信计算等方面也有大量成果，例如可信计算组（The Trusted Computing Group ，TCG）在可信平台模块规范中推荐的椭圆曲线直接匿名证明协议（ECDAA），适用于通用问题的零知识证明（zk-SNARK），intel的可信计算环境SGX以及加强隐私ID（EPID）等。
双线性对的应用
虽然双线性对有大量的应用案例，但是限于篇幅，本文挑选了三方一轮密钥交换和SM9数字签名算法作为例子。
本部分先将算法过程剥离开来，还没有太多去分析算法的原理，这是因为在不了解双线性对的前提下理解这些算法是有困难的。
我们建议读者先简单阅读本部分了解算法能实现的功能，然后在阅读下篇的双线性对的性质介绍后再回来品味算法的优美。
▲三方一轮密钥交换
密钥交换（key exchange）又叫密钥协商（key agreement），是一种能够让参与者在公共信道上通过交换某些信息来公共建立一个共享密钥的密码协议。
最常见的是两方DH密钥交换，椭圆曲线群上的DH（ECDH）依据的椭圆曲线群是循环群这个性质。
如下图：
1.用户A生成随机数a，计算aG，并将aG发送给对方
2.用户B生成随机数b，计算bG，并将bG发送给对方
3.A和B利用手中信息分别计算出abG作为协商密钥，原因是abG = baG
通过上述的DH算法可以轻松地完成两方的密钥协商，但是较难满足需要三方密钥协商的场景。
利用双线性对可以仅做一轮通信完成密钥协商。
如下图所示：
1.A选择随机数a，计算aG，将结果发送给B和C
2.B选择随机数b，计算bG，将结果发送给A和C
3.C选择随机数c，计算cG，将结果发送给A和B
4.A计算ae(bG, cG)
5.B计算be(aG, cG)
6.C计算ce(aG, bG)
A、B、C分别计算出的结果就是协商出的密钥。这个协议是双线性配对在密码学研究中的第一次正面应用。
SM9数字签名算法
SM9标识密码算法包括数字签名算法、密钥协商算法、加解密算法三部分，我们主要来关注数字签名算法。
不同于传统签名算法的由用户随机选择私钥然后计算得到公钥的方式，SM9能够实现用户指定公钥，密钥生成中心通过公钥计算私钥。
这样可以将一些有意义的字符串，例如身份证号码、邮箱地址等作为用户公钥，从而能在公钥中直接反应出用户信息，这也是标识密码（IBC）的含义。
签名算法包括参数生成、密钥生成、签名和验签等几个步骤。和一般签名验签不同的地方在于，密钥生成分为主密钥生成和用户密钥生成两部分，主私钥由密钥生成中心（KGC）保管。
可以看到不论是在三方一轮密钥协商中，还是在SM9签名验签中，e都扮演了重要的角色。当不知道e是指什么的情况下要理解上面两个算法是不现实的，而这个映射e也正是本文的核心：双线性映射。
e的计算是一个计算复杂度较高的操作，我们不打算介绍关于e的原理和细节，读者只需要了解e的一些属性就足够理解上面两个例子的思想。
因为篇幅原因，双线性映射的性质将在下篇介绍。在下篇的开始我们就会先帮助读者理解什么是双线性，然后紧接着再回顾上面的两个算法，介绍并分析它们的思想和原理。
双线性对的性质介绍
▲ 性质介绍
在本科阶段的线性代数课程中，读者可能已经学习过线性映射（linear mapping）的概念，但是对双线性映射（bilinear mapping）的概念可能会感到陌生。
我们说一个函数f是线性的是指函数f满足可加性和齐次性，也就是：
可加性：f(a)+f(b)=f(a+b)
齐次性：f(ka)=kf(a)
比如中学就接触的正比例函数就是一个线性映射。
例如对f(x)=3x，有f(1)=3，f(-2)=-6，则：
可加性：f(1)+f(-2)=f(-1)=-3
齐次性：f(-2)=-6=-2f(1)
理解了线性，那么双线性就好理解很多。
和线性函数不同的点在于满足双线性的函数有两个输入，而且对这两个输入分别满足线性。换言之，如果固定其中一个输入使之成为一元函数，则这个一元函数满足线性。
而双线性对就是指群上元素满足双线性映射的三个群，它们的关系满足双线性，下面是定义：
综上我们可以看到双线性使得变量前面的系数可以灵活转化，这是正是双线性对独特的性质。利用这些性质，双线性对在密码学中可用来构造很多其他数学工具所不能构造的协议或方案。
▲ SM9密钥协商算法解析
首先我们来理解双线性对在SM9算法中起到的作用。
下面的介绍中的签名算法是简化后的版本，能够体现算法原理，但是并非SM9标准算法本身，签名算法的完整流程可以参看参考文献中的GM/T0044标准。
可以看到相对于ECDSA算法，SM9的密钥生成相对要复杂一些。这里的巧妙之处在于将H(ID)+ks的逆元隐藏在用户私钥中，稍后这一逆元也会影响到签名和验签。
签名和验签算法的巧妙之处在于计算hash时拼接了re(P₁,Ps)，从而将rPs隐藏在hash结果中，验签算法正是通过S和公钥计算rPs的过程——如果签名中的h和S是正确的，那么按照验签流程应该能够计算出同样的rPs，然后同样计算H(M||rPs)，如果该值和h一致，那么签名被认为是合法的。
而验签算法中计算rPs的过程正是利用了双线性映射。验签的第三步骤中通过e(P₁,Ps)约减掉了之前提到的H(ID)+ks，从而得到结果。
这个具体过程可以看下面的式子，这个式子也恰好是SM9签名算法正确性的简单证明：
▲ 三方一轮密钥协商算法解析
该算法的关键在于三方独立计算出的ae(bG, cG)、be(aG , cG) 和ce(aG, bG)要相同，否则就无法协商出一致的密钥。
但是根据双线性对能够将每个参数的系数提出来的这个性质，我们有：
ae(bG, cG) = abce(G , G)
be(aG , cG) = abce(G , G)
ce(aG, bG) = abce(G , G)
因此三方计算出的密钥k是相同的，上面三个式子也恰好是该算法正确性的简单证明。
双线性对的实现
本文的最后，我们来了解一些双线性对已有的代码应用实现。
自Weil提出双线性对概念时构造出Weil对以来，后续的密码学家提出很多新的双线性对的构造，例如Tata对、Ate对、Rate对、最优对等。
虽然双线性对有诸多优点，但是其计算开销往往较大。
例如基于配对的BLS签名，虽然可以方便的实现签名聚合，但是其验签时间相对于传统的ECDSA签名上升了两个数量级。因而不断研究各种配对函数主要也是为了降低配对函数计算的复杂度，从而使双线性对这个工具更有实用性。
另外需要强调的是，并非基于任何椭圆曲线都可以构造配对函数，对于能有效实现双线性对的椭圆曲线，称为pairing-friendly curves。
BN曲线曾是配对友好曲线的代表，在go语言代码包golang.org/x/crypto/bn256中提供了基于BN256曲线的双线性对实现，并且该代码包中提供了使用BN256完成一轮三方密钥协商的测试示例。
下图是该代码包的介绍性注释：
不幸的是，2016年的研究（https://moderncrypto.org/mail-archive/curves/2016/000740.html)指出BN曲线配对在NFS数域筛算法的攻击下达不到宣称的安全等级（在新攻击方法下估计强度大约减少1/4）。
此发现的影响范围非常广，至少波及zcash等项目使用的zkSNARK实现、Apache Milagro项目、以太坊、任何使用相关曲线的BBS签名和BLS签名等，可能影响到intel的SGX和EPID安全性。
鉴于此，该代码仓库不再做维护。
但是也不必沮丧，回顾《双线性对在密码学中的应用（上）》那句话，进攻和防守只是同一件事的不同方面，这一发现只会促进安全性的又一次进步。
首先对于BN曲线，仍然可以通过提高参数长度来弥补漏洞。建议将曲线大小提高1/3从而到达相同的安全等级。另外，除去BN曲线，仍然有其他可用于配对的曲线可以选择。IEFT审议的草案pairing-friendly-curve的第七个版本（https://tools.ietf.org/pdf/draft-irtf-cfrg-pairing-friendly-curves-07.pdf）已经完全考虑到相关攻击的影响，因此该草案中推荐的曲线目前是安全的。
对于128位安全级别，草案推荐嵌入度为12的381位特征的BLS曲线和462位特征的BN曲线，对于256位的安全级别，推荐嵌入度为48且具有581位特征的BLS曲线。
从代码实现的角度来看，PBC（https://crypto.stanford.edu/pbc/）库和Miracl（https://miracl.com/）库是两个较优的选择。
总 结
经过十余年的研究，双线性对的性质、实现方法等研究领域已经有了很大进展。
本文简要介绍了双线性对在密码学中的应用，包括双线性对的研究历程、双线性对的概念和性质以及双线性对的应用，主要包括三方一轮密钥协商、SM9标识密码。
在学界对双线性对多年的研究之后，多线性映射作为一个自然而然的推广也得到越来越多的关注，是相关领域下一个值得期待的研究热点，我们会在以后的介绍中分享，大家敬请期待！