建议和反馈

请填写你的反馈内容

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

2020-12-02 ·1736次阅读 ·读完需要13分钟

双线性对的性质介绍

 

性质介绍

在本科阶段的线性代数课程中,读者可能已经学习过线性映射(linear mapping)的概念,但是对双线性映射(bilinear mapping)的概念可能会感到陌生。

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

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

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

比如中学就接触的正比例函数就是一个线性映射。

例如对f(x)=3x,有f(1)=3f(-2)=-6,则:

可加性:f(1)+f(-2)=f(-1)=-3

齐次性:f(-2)=-6=-2f(1)

理解了线性,那么双线性就好理解很多。

和线性函数不同的点在于满足双线性的函数有两个输入,而且对这两个输入分别满足线性。换言之,如果固定其中一个输入使之成为一元函数,则这个一元函数满足线性。

而双线性对就是指群上元素满足双线性映射的三个群,它们的关系满足双线性,下面是定义:

G₁G₂G₃是三个n阶循环群,一个双线性对(双线性映射)

1.双线性性:

2.非退化性: 存在g₁g₂,使得

3.可计算性: 存在有效的多项式时间算法计算双线性对的值

上述定义简单来说就是,一个映射e,能将G₁G₂中的两个元素映射为G₃中的一个元素,并且该映射满足双线性。这里的定义虽然严谨,但不便于读者接受,我们通过类比来加深理解,例如读者熟悉的向量内积就满足双线性。我们来回顾一下向量内积的特点,内积运算从两个向量αβ得到数r

α · β → r

所谓双线性映射,是从两个元素到一个元素的映射,并且这个映射对每一个输入的元素都保持线性。

比方说:我们固定β,则rα是有线性的关系的:如果用代替α,那么结果就是kr;固定α也有同样的结论,因此内积的运算是有双线性的。

我们研究的椭圆曲线上的双线性对也正是有类似的双线性,并且根据双线性,我们有下面的推论:

g₁, g₂分别是群G₁G₂的元素,

注意这里G₃的群运算用加法表示了,如果用乘法表示则看起来会不同,但是本质一样,写成加法还是乘法只是符号的问题。

本文约定都按照加法形式处理(这里的加法并不暗示群一定是交换群),但通常习惯将G₃写成乘法群的形式,如下:

1.png 

综上我们可以看到双线性使得变量前面的系数可以灵活转化,这是正是双线性对独特的性质。利用这些性质,双线性对在密码学中可用来构造很多其他数学工具所不能构造的协议或方案。

▲ SM9密钥协商算法解析

首先我们来理解双线性对在SM9算法中起到的作用。

下面的介绍中的签名算法是简化后的版本,能够体现算法原理,但是并非SM9标准算法本身,签名算法的完整流程可以参看参考文献中的GM/T0044标准。

因为使用到双线性配对,这里涉及到三个椭圆曲线群,我们记为G₁G₂G₃e是从G₁×G₂G₃的双线性映射,G₁G₂的生成元分别为P₁P₂。并且设e(P₁, P₂)=P₃ ∈ G₃

在签名和验签之前,还需要经历生成主密钥、生成用户密钥两个步骤,主密钥只需要生成一次并由密钥生成中心保管,而用户密钥生成则需要为每个用户生成一次。

可以看到相对于ECDSA算法,SM9的密钥生成相对要复杂一些。这里的巧妙之处在于将H(ID)+ks的逆元隐藏在用户私钥中,稍后这一逆元也会影响到签名和验签。

222.png 

签名和验签算法的巧妙之处在于计算hash时拼接了re(P₁,Ps),从而将rPs隐藏在hash结果中,验签算法正是通过S和公钥计算rPs的过程——如果签名中的hS是正确的,那么按照验签流程应该能够计算出同样的rPs,然后同样计算H(M||rPs),如果该值和h一致,那么签名被认为是合法的。

而验签算法中计算rPs的过程正是利用了双线性映射。验签的第三步骤中通过e(P₁,Ps)约减掉了之前提到的H(ID)+ks,从而得到结果。

这个具体过程可以看下面的式子,这个式子也恰好是SM9签名算法正确性的简单证明:

333.png 

三方一轮密钥协商算法解析

该算法的关键在于三方独立计算出的a

但是根据双线性对能够将每个参数的系数提出来的这个性质,我们有:

a

b

c

因此三方计算出的密钥k是相同的,上面三个式子也恰好是该算法正确性的简单证明。

 444.png

双线性对的实现

 

本文的最后,我们来了解一些双线性对已有的代码应用实现。

Weil提出双线性对概念时构造出Weil对以来,后续的密码学家提出很多新的双线性对的构造,例如Tata对、Ate对、Rate对、最优对等。

虽然双线性对有诸多优点,但是其计算开销往往较大

例如基于配对的BLS签名,虽然可以方便的实现签名聚合,但是其验签时间相对于传统的ECDSA签名上升了两个数量级。因而不断研究各种配对函数主要也是为了降低配对函数计算的复杂度,从而使双线性对这个工具更有实用性。

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

BN曲线曾是配对友好曲线的代表,在go语言代码包golang.org/x/crypto/bn256中提供了基于BN256曲线的双线性对实现,并且该代码包中提供了使用BN256完成一轮三方密钥协商的测试示例。

下图是该代码包的介绍性注释:

22.png 

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

此发现的影响范围非常广,至少波及zcash等项目使用的zkSNARK实现、Apache Milagro项目、以太坊、任何使用相关曲线的BBS签名和BLS签名等,可能影响到intelSGXEPID安全性。

鉴于此,该代码仓库不再做维护。

但是也不必沮丧,回顾双线性对在密码学中的应用(上)》那句话,进攻和防守只是同一件事的不同方面,这一发现只会促进安全性的又一次进步。

首先对于BN曲线,仍然可以通过提高参数长度来弥补漏洞。建议将曲线大小提高1/3从而到达相同的安全等级。另外,除去BN曲线,仍然有其他可用于配对的曲线可以选择。IEFT审议的草案pairing-friendly-curve的第七个版本(https://tools.ietf.org/pdf/draft-irtf-cfrg-pairing-friendly-curves-07.pdf)已经完全考虑到相关攻击的影响,因此该草案中推荐的曲线目前是安全的。

对于128位安全级别,草案推荐嵌入度为12381位特征的BLS曲线和462位特征的BN曲线,对于256位的安全级别,推荐嵌入度为48且具有581位特征的BLS曲线。

从代码实现的角度来看,PBChttps://crypto.stanford.edu/pbc/)库和Miraclhttps://miracl.com/)库是两个较优的选择。

 


声明:作为区块链技术信息平台,本站所提供的资讯信息不代表任何投资暗示,本站所发布文章仅代表个人观点,与链客社区官方立场无关。
评论(0)问答(0)
请先登录或注册

请先登陆或注册

相关推荐

区块链中的数学 - 不经意传输

不经意传输(Oblivious transfer)或者译为茫然传输是密码学中的一类协议,缩写为OT,实现了发送方将潜在的许多信息中的一个传递给接收方,但对接收方所接收信息保持未知状态。写在前面上一篇讲......
云志 · 2021-02-04
1579阅读 · 0赞赏 · 0问答

区块链中的数学 - 哈希承诺

作者:blocksight本文介绍密码学承诺的含义及性质,并对哈希承诺做了说明,关于hash函数的内在机制实际是比较复杂的,我们以黑盒的角度来学习了解它的性质,在区块链&密码学中,哈希函数占据了基础且......
云志 · 2021-02-04
1773阅读 · 0赞赏 · 0问答

区块链中的数学 - Pedersen承诺

作者:blocksightPedersen承诺产生方式,有些类似加密,签名之类的算法。但是,作为密码学承诺重在“承诺”,并不提供解密算法,即如果只有r,无法有效地计算出隐私数据v。写在前面上一篇介绍了......
云志 · 2021-02-04
1423阅读 · 0赞赏 · 0问答

Schnorr 多签

Schnorr 最大的特性是可以进行公钥和签名聚合(aggregate)。可以把多个签名聚合成一个签名,因此大大节省了多重签名的字节空间。这种聚合不但是同一个input,不同singer之间的签名聚合......
分析师 · 2021-01-21
1540阅读 · 0赞赏 · 0问答

证明MiMC哈希的GKR + Groth16与Groth16的正确时间比较

来源:ethresear.ch在这里遵循我们的建议 32我们介绍了针对MiMC7实施GKR + Groth16的结果。这篇文章使用两种方法比较了2 ^ 23(〜8M)个MiMC哈希的验证时间......
胖shy · 2021-01-11
1420阅读 · 0赞赏 · 0问答

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

作者:blocksight改进的密钥聚合的算法是如何防止伪签名的呢?本质上增加了公钥的可验证性写在前面上一节简要概述了 BLS 签名机制,具体实现起来有很多细节,如哈希消息到曲线上的点。本文......
YYF · 2020-12-21
1825阅读 · 0赞赏 · 0问答

abcdef

19.0

LK币

0

粉丝

11

笔记

感谢"abcdef"

这篇精彩的笔记,目前已经帮助

  • 0
  • 1
  • 7
  • 3
  • 6
喜欢0
链客社群 加入

微博进入

商务合作>

广告投放>

公司名称:北京链客行科技有限公司

联系方式:010-67707199

ICP备案号:京ICP备18032136号

Copyright:链客区块链技术问答社区 版权所有

感谢您的提问,问题被社区永久收入以便新人查看。一定要记得采纳最佳答案哦!加油!

感谢您的善举,每一次解答会成为新人的灯塔,回答被采纳后获得20算力和相应的LK币奖励

您将赞赏给对方2LK币的奖励哦!感谢您的赞赏!

您将赞赏给对方2LK币的奖励哦!感谢您的赞赏!