双线性对是一种二元映射,它作为密码学算法的构造工具,在各区块链平台中广泛应用,比如零知识证明、聚合签名等技术方案大多基于双线性对构造得来。

线性映射

一个函数f是线性的是指函数f满足可加性和齐次性,也就是:

可加性:f(a)+f(b)=f(a+b)

齐次性:f(ka)=kf(a)

双线性映射

和线性函数不同的点在于满足双线性的函数有两个输入,而且对这两个输入分别满足线性。

一个映射e,能将G₁和G₂中的两个元素映射为G₃中的一个元素,并且该映射满足双线性。

设g₁, g₂分别是群G₁和G₂的元素,𝑒是G₁×G₂→G₃的双线性映射,那么有:

𝑒(ag₁, bg₂) = ab 𝑒(g₁ , g₂) = 𝑒(abg₁ , g₂) = 𝑒(g₁ , abg₂)

𝑒(ag₁, bg₂) + 𝑒(cg₁, dg₂) = (ab+cd) 𝑒(g₁, g₂)

双线性使得变量前面的系数可以灵活转化

基于双线性对的密码算法

三方一轮密钥协商

三方一轮密钥协商是一种可以在一轮交互内完成三方的密钥协商的密钥协商协议,效率高于DH密钥协商。传统的DH密钥协商可以完成两两之间的密钥协商。虽然能够通过两两之间多轮协商完成三方之间的密钥协商,但是增加了通信复杂度。

国密SM9算法

基于身份的密码体制(IBE)是公钥密码学的一个研究方向,其特点是直接用标识用户身份的字符串作为公钥。大家熟悉的国密SM9算法就属于该类算法,这是目前国产密码算法中唯一一个基于双线性对的密码算法。

SM9标识密码算法包括数字签名算法、密钥协商算法、加解密算法三部分。不同于传统签名算法的由用户随机选择私钥然后计算得到公钥的方式,SM9能够实现用户指定公钥,密钥生成中心通过公钥计算私钥。

这样可以将一些有意义的字符串,例如身份证号码、邮箱地址等作为用户公钥,从而能在公钥中直接反应出用户信息,这也是标识密码(IBC)的含义。这样可以将一些有意义的字符串,例如身份证号码、邮箱地址等作为用户公钥,从而能在公钥中直接反应出用户信息,这也是标识密码(IBC)的含义。

和一般签名验签不同的地方在于,密钥生成分为主密钥生成和用户密钥生成两部分,主私钥由密钥生成中心(KGC)保管。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

BLS签名算法

BLS签名是Boneh、Lynn和Shacham三人基于双线性映射构造的短签名方案,其特性之一就是能用于构造聚合签名。

可以有效缩减PBFT类共识在区块头中存放的签名体积, 聚合签名只占 32 字节, 可以在区块中放更多笔的交易。

MOV攻击

又称MOV规约攻击,是Menezes、Okamoto和Vanstone三人的论文中提出的针对特殊椭圆曲线离散对数问题(ECDLP)的一种有效解法。通过双线性配对,将椭圆曲线上的离散对数问题规约成为某个乘法群上的离散对数问题,能够在亚指数步骤中计算ECDLP。

MOV攻击并非能作用于全部的椭圆曲线,而是只能对参数满足一定条件的曲线进行攻击。这促使人们在选择椭圆曲线参数时更加谨慎,更加注重抗MOV攻击。

例如国标《SM2椭圆曲线公钥密码算法》就充分重视了受到MOV攻击的可能性,不仅在第一部分《总则》中用附录A的部分篇幅介绍验证曲线参抗MOV攻击的方法,而且也在第五部分《参数定义》中给出了安全曲线的推荐参数。

缺点: 计算开销较大

配对函数并不那么高效, 验签时间相对于传统的ECDSA签名上升了两个数量级。

BLS 签名验证的复杂度要比 ECDSA 高上一个数量级。在验证区块中 1000 笔交易的聚合签名时,仍需要进行 1000 次配对计算,这可能比使用 ECDSA 时(对 1000 个单独签名进行验证)还要慢。唯一的好处在于,可以在区块中放更多笔的交易,毕竟聚合签名只占 32 字节。

曲线

并非基于任何椭圆曲线都可以构造配对函数,对于能有效实现双线性对的椭圆曲线,称为配对友好曲线(pairing-friendly curves)。

BN曲线

不再安全, 2016年的研究(https://moderncrypto.org/mail-archive/curves/2016/000740.html)指出BN曲线配对在NFS数域筛算法的攻击下达不到宣称的安全等级(在新攻击方法下估计强度大约减少1/4)。

BLS曲线

BLS12_381(嵌入度为12的381位特征的BLS曲线, 128位安全级别), 零知识证明(zk-SNARK)的证明系统,主要是基于BLS12_381椭圆曲线上,实现了Groth16的零知识证明系统。

名词解释

DLP

离散对数问题。例如在整数模11乘法群中容易计算5×5×5×5=9 mod 11,那么求几个5相乘的结果是9这个问题就是一个离散对数问题。当模数为很大的质数时,这个问题是困难的。

ECDLP

椭圆曲线离散对数问题。例如已知P、Q是两个椭圆曲线点,并且4个P相加得到Q,那么已知P和Q求解几个P相加得到Q的问题就是椭圆曲线离散对数问题。当选择的曲线满足一定要求时,该问题是困难的。

参考文献:

双线性对在密码学中的应用(上)

双线性对在密码学中的应用(下)


往期精彩回顾:
区块链知识系列
密码学系列
共识系列
公链调研系列
以太坊系列
EOS系列
智能合约系列
Token系列
Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐