区块链中的数学 - BLS 基石(双线性函数)和配对

双线性配对特性不仅可以用于签名构造,密钥协商等,还可以实现乘法的同态隐藏和校验。这一点在零知识证明项目中应用很多。另外需要说明的是,并非基于任何椭圆曲线都可以构造配对函数,对于能有效实现双线性对的椭圆曲线,称为pairing-friendly curves,例如BLS12_381曲线。

写在前面

上一篇讲述了BLS门限签名,BLS签名机制和其他签名方案相比,最大的不同或者说创新在于使用了双线性配对函数,这一点在前面几篇都提到过,本文简要说一下双线性配对函数的性质。

双线性映射定义

双线性配对(Bilinear Pairing), 有时也称作双线性映射,具体翻译略有不同。双线性配对在密码学中得到广泛的应用始于2001年Boneh和Franklin使用它构造了第一个实用并且安全的基于身份加密方案IBE(IBE 可参照https://en.wikipedia.org/wiki/Identity-based_encryption)。 可以看出与BLS首次提出在同一年,不是巧合,是因为二者有共同作者--Boneh教授。

定义:一个双线性映射是由两个向量空间上的元素,生成第三个向量空间上一个元素之函数,并且该函数对每个参数都是线性的

若有A,B,C三个向量空间,映射e: A × B → C是一个双线性映射,则A固定,B可变时,B到C的映射是线性的,B固定,A可变时,A到C的映射也是线性的,也就是说保持双线性映射中的任意一个参数固定,另一个参数对C的映射都是线性的。

即双线性的函数有两个输入,而且对这两个输入分别满足线性。

例如矩阵乘法,数据库两张表的笛卡尔积都是双线性配对的例子。

配对函数满足:

密码学中双线性映射

密码学中的配对用法: 有三个素数p阶群乘法循环群$G_1 \cdot G_2 ,G_T$,三个群存在一个映射关系(函数)$e:G_1 * G_2 \to G_T$,且满足以下性质:

双线性(Bilinearity):对于任意的$g_1 \in G_1 ,g_2 \in G_2$,均有$e(g^a_1,g^b_2)=e(g_1,g_2)^{ab}$成立;

非退化性(Non-degeneracy):$\exists g_1 \in G_1,g_2 \in G_2 $使得 $e(g_1,g2) \not= 1{G_T}$($G_T$单位元)。非退化性保证了只要我们选择椭圆曲线上的非单位成员G,就能得到目标群中的非单位元

可计算性(Computability):存在有效的算法,对于$\forall g_1 \in G_1,g_2 \in G_2$,可计算$e(g_1,g_2)$,显而易见只有这样才具有可实用性。

特殊情况下$G_1=G_2$则称该双线性配对是对称的,否则是非对称的。另外还存在一种合数阶的双线性配对,不再详述!

关于双线性映射可以通过有限域上的超椭圆曲线上的Tate对或Weil对来构造。基于pairing密码学实现库可参考PBC (Pairing-Based Cryptography) library:https://crypto.stanford.edu/pbc/ 当然也有其他库可用,不再列举。

小结

双线性配对特性不仅可以用于签名构造,密钥协商等,还可以实现乘法的同态隐藏和校验。这一点在零知识证明项目中应用很多。

另外需要说明的是,并非基于任何椭圆曲线都可以构造配对函数,对于能有效实现双线性对的椭圆曲线,称为pairing-friendly curves,例如BLS12_381曲线。

关于配对的具体实现如Kate配对实现,涉及背景知识众多,且是高等数学内容,单独说起来晦涩不易理解,好在现在都有成熟的实现库,以后有机会再讲讲配对实例的具体实现吧。

配对也不是完美的, 配对实现需要对曲线做慎重选择,加之操作复杂,运算效率有所降低,例如BLS签名验证效率就比传统的ECDSA要低,配对算法的研究就是在致力改善这一点。

关于配对,还感兴趣的可以参考:

Pairings For Beginners: http://www.craigcostello.com.au/pairings/PairingsForBeginners.pdf

Short signatures from the Weil pairing: https://www.iacr.org/archive/asiacrypt2001/22480516.pdf

既然说到了配对在零知识证明中的应用,从下一节开始,我们开启零知识证明系列! 纵观区块链技术近几年的发展,密码学在区块链领域的创新应用成为区块链创新的基石与引擎,例如以太坊扩容方案zk-rollup等等。

欢迎关注公众号:blocksight

相关阅读:

区块链中的数学 - BLS门限签名 BLS m of n门限签名

区块链中的数学 - BLS密钥聚合 BLS密钥聚合

区块链中的数学 - BLS数字签名 BLS签名及验证

区块链中的数学 - 参与者 < 门限值t的密钥更新Amir Herzberg方案 Amir Herzberg改进方案

区块链中的数学 - Feldman的可验证的密钥分享 Feldman可验证密钥分享方案

区块链中的数学 - Ed25519签名 Ed25519签名

区块链中的数学-ElGamal算法 ElGamal算法签名及验证&实例演练

区块链中的数学-VRF基于ECC公钥体制的证明验证过程 基于椭圆曲线的VRF证明验证过程

Schorr签名与椭圆曲线 Schorr签名与椭圆曲线

区块链中的数学-Uniwap自动化做市商核心算法解析 Uniwap核心算法解析(中)

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2021-01-02 15:55
  • 阅读 ( 549 )
  • 学分 ( 6 )
  • 分类:入门/理论

0 条评论

请先 登录 后评论
blocksight
blocksight

67 篇文章, 1650 学分