建议和反馈

请填写你的反馈内容

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

2020-12-02 ·1425次阅读 ·读完需要9分钟

作者简介

乔沛杨,来自趣链科技基础平台部,区块链密码学研究小组


导 读


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

本次将分为上、下两个篇章讲解双线性对在密码学中的应用。

本文为上篇入门篇,会从概念介绍发展历程实际应用三个方面展开说明,下篇为进阶篇,将从原理层面深入剖析。


双线性对的研究历程


▲ 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计算a

声明:作为区块链技术信息平台,本站所提供的资讯信息不代表任何投资暗示,本站所发布文章仅代表个人观点,与链客社区官方立场无关。
评论(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问答

小拇指

2503.0

LK币

2

粉丝

46

笔记

感谢"小拇指"

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

  • 0
  • 1
  • 4
  • 2
  • 5
喜欢0
链客社群 加入

微博进入

商务合作>

广告投放>

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

联系方式:010-67707199

ICP备案号:京ICP备18032136号

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

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

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

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

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