我的账户
触电网

自媒体资讯干货

亲爱的游客,欢迎!

已有账号,请

如尚未注册?

QQ图标网 触电网 QQ头像

如何评价“西安电子科技大学胡予濮教授攻破GGH密码方案”? ...

2018-9-1 13:34

补充,感谢@edwardz的分享。@edwardz在私下讨论中,推荐了下述总结,希望对相关领域感兴趣的朋友们有所帮助:http://malb.io/are-graded-encoding-schemes-broken-yet.html。=============================谢@LLQ654 ...

补充,感谢 @edwardz 的分享。@edwardz在私下讨论中,推荐了下述总结,希望对相关领域感兴趣的朋友们有所帮助:http://malb.io/are-graded-encoding-schemes-broken-yet.html

=============================
谢 @LLQ654 、 @玄星 邀。

个人观点,仅供参考。答案主线将沿新闻稿论述进行剖析,简单讲一讲成果本身,并补充一些黑历史。

在新闻稿中可以体现出,胡予濮教授所说的话是非常严谨的。仅从新闻稿的内容就可以得出断言,胡教授是一位非常严谨的学者,必须为其点赞。

新闻稿链接:http://toutiao.com/a6263327533842350338/
胡予濮教授和贾惠文博士研究生的论文完整版链接:Cryptology ePrint Archive: Report 2015/301
密码学三大顶级会议之一,EUROCRYPT 2016 Accepted Papers页面:EUROCRYPT 2016

=============================
先说结论:胡予濮教授和贾惠文博士研究生的工作,对国际密码学有关Multilinear Map的研究来说是地震性质的成果。他们的工作结果表明,2013年由Sanjam Garg(当时是UCLA的博士研究生),Graig Gentry和Shai Halevi(IBM研究院研究员)利用Ideal Lattice所构造的GGH Multilinear Map,由于不满足Weak Discrete Log Problem假设,因此基于GGH Map所构造的One-round Multiparty Key Exchange Protocol,以及一个基于Exact-3-Cover Problem的Witness Encryption,存在安全漏洞。并断言,此安全漏洞的根源在于GGH Map,因此可能导致基于GGH Map的密码学方案构造都是不安全的。这就意味着GGH Map的应用场景会被进一步压缩。同时,由于GGH Map几乎是所有现有Multilinar Map的基础,因此基于Multilinear Map的One-round Multiparty Key Exchange Protocol构造又回到了上古时代:仍然没有安全的构造实例。

对国内的影响:成果本身表明,国内学者对于密码学前沿理论的研究,已经追上甚至超过国际研究的步伐。可以认为,国内顶级密码学者的研究水平已经和国际顶级学者持平。

=============================
我本来一直都不太敢回答这个问题,原因是GGH Map对于我来说一直是一种无法理解的存在。对于胡予濮教授和贾惠文博士研究生的贡献,更是一直以来连浅显的理解都做不到。但因为下面的原因,我还是决定尽我所能,回答一下这个问题。

首先,随着3天前刚刚听译完毕Vadim Lyubashevsky在Winter School on Cryptography 2012中有关Ideal Lattice and Its Applications,以及Craig Gentry在Winter School on Cryptography 2012中有关Somewhat Homomorphic Encryption的报告后,我终于有可能尝试去理解密码学界这3年来一直重点讨论的GGH Map,以及其应用的论文了。听译压制后的视频将会在大约3周后在世界上最顶级的密码学课程课程详情上发布。如果真的想简单了解胡予濮教授和贾惠文博士研究生的贡献,可以把视频作为入门材料,结合PPT多线性映射方案分析Cryptanalysis of the GGH’13 multilinear map_百度文库进行学习。

其次,我认为已有的答案都有点偏了。并非讨论胡予濮教授和贾惠文博士研究生的贡献本身,转而变成了另一种风气。我觉得这样的趋势并不太好。科学研究本身需要安静,需要心如止水地理解和创新。与之相对的,就是急功近利,有了成果就被媒体大写特写。这不是反而落回了教育界一直以来对国内科研的批评点了吗?

再次,近年来信息安全越来越热,相关的介绍和报道也是越来越多。先是支付宝漏洞,然后又是百度云盘,最近又出来一些听起来似乎特别高大上,但是经不起推敲的新闻。在批评企业良心什么的之前,还是要理智的思考问题,不要人云亦云。企业的有些做法的确不良心,有些做法是没办法的办法。举个简单的正面例子:

利用现有安全技术,在考虑用户可能忘记密钥的条件下,有可能实现云存储全盘加密+通过网页把文件安全分享给任意指定的第三方用户吗?

=============================
高能预警,下面的回答比较难以理解,有很多名词出现。

下面,我将沿新闻稿的描述进行剖析。因为原文中一些词语并没有对应上,所以我对原稿的翻译部分进行了些许修改,主要是用英文词汇置换中文翻译,这样可以看出知识点之间的关系。

Diffie-Hellman密钥交换的提出,颠覆了人们“不事先进行秘密共享是无法进行保密通信”的传统观念,使得用户可以在一个完全开放的信道上,进行秘密共享,实现保密通信。这一思想上的突破,成为了现今密钥交换系统的基础,被广泛应用于网络通信。与经典密码学相对应,业界将1976年定为现代密码学元年。迪菲与赫尔曼也因此获得美国计算机协会ACM授予的2015年度“图灵奖”。
有关这方面的介绍,请参见我的答案:如何评价 Diffie 和 Hellman 获 2016 年图灵奖? - 刘巍然-学酥的回答,在此不多做叙述。

直到2000年,密码学家Antoine Joux利用Bilinear Map,设计了第一个非交互的三方密钥交换协议,在该问题上取得了阶段性突破,但仍无法将这种思想推广到四方以上参与者的密钥交换中。2003年,密码学家Dan Boneh和Alice Silverberg提出Multilinear Map这一概念,并指出多线性映射不但可以解决多方秘密交换这一公开问题,而且还可以用于构造其他更高级的密码应用方案,但他们却无法给出具体的代数实现。
多方密钥协商协议一直已经有了构造,但是无法达到非交互。所谓非交互,就是协议只需要双方发送一次信息就可以完成协商过程。现有构造中,当参与方超过3个时,双方至少需要交互发送2次信息才可以完成密钥协商。
Multilinear Map的概念实际上是Bilinear Map的自然推广。之所以2003年提出了这一概念,是因为:
  • 2001年,Dan Boneh等人利用Bilinear Map构造了更高级的密码学应用方案:Identity-Based Encryption(基于身份的加密),
  • 2002年,Dan Boneh等人利用Bilinear Map构造了可证明严格满足签名安全需求的数字签名方案。
这两个成果的提出,让学者们了解到Bilinear Map这一代数结构,不仅可以构造简单的密钥协商协议,更可以构造更高级的密码学应用。自2001年开始,Bilinear Map也作为密码学热门研究方向,持续了10年左右的时间。

然而,Bilinear Map无法自然推广为Multilinear Map。这是因为Bilinear Map中,被Map的群是椭圆曲线群,但Map后的群代数结构发生了变化,不再是椭圆曲线群。如果构造Multilinear Map,实际要求Map之前和Map之后的群代数结构都必须要相同才可以。

EUROCRYPT 2013上,时为UCLA的博士生Sanjam Garg,以及IBM研究员Craig Gentry和Shai Halevi,共同提交了一篇论文“Candidate Multilinear Maps from Ideal Lattices”。该论文提出一个Graded Encoding Systems概念,并以此在Ideal Lattice上实现了第一个Multilinear Map(GGH Map,取名于三位作者姓名Garg、Gentry和Halevi的首字母),进而解决了现代密码学遗留的那个公开问题,这篇论文也因此获得当年欧密会的最佳论文奖。
这个构造与其说是一个方案,不如说是一个密码学工具更为准确一点。由这3个人提出构造也一点都不奇怪。首先,Multilinear Map的构造和Gentry提出的Fully Homomorphic Encryption(FHE)非常类似:本质上,群加法运算就是FHE中的密文加法操作,Map运算就是FHE中的密文乘法操作。同时,这个工具的基础是Ideal Lattice,而Halevi正是Lattice的著名学者。他是格密码学加密方案:GGH方案(这里的GGH指的是Goldreish, Goldwasser和Halevi,不是相同的3个人,这一工作所对应的论文"Public-Key Cryptosystems from Lattice Reduction Problems"发表在CRYPTO 1997上)的构造者。至于Garg,他是UCLA的博士生… 也是因为这个工作,他从UCLA顺利毕业,而博士论文就是"Candidate Multilinear Maps"(http://www.cs.berkeley.edu/~sanjamg/Sanjam%20Garg_files/sanjam-thesis.pdf),并因此拿到了2013 ACM Doctoral Dissertation Award。所以… 嗯… 这么轰动密码学界的成果,使得一个博士生毕业了,实在是有点醉。实际上,Gentry也是因为他的FHE构造,经过8年的博士研究后,从Standord毕业,博士论文是"A Fully Homomorphic Encryption Scheme"(http://crypto.stanford.edu/craig/craig-thesis.pdf)。而Gentry的导师就是Dan Boneh。

“GGH Map对密码学界产生了深远影响,迅速在国际密码学界引发了Multilinear Map研究的热潮。”胡予濮介绍说。因为这个里程碑式的构造,不仅为密码学界遗留下来的公开问题找到了答案,也促使了其他近似的构造,并有望在未来广泛应用于Witness Encryption、Broadcast Encryption、Attribute-Based Encryption、Functional Encryption、Aggregate Signatures等多种高级的应用场合,从而将现代密码学大大地向前推动一步!
上述几个应用场景,除了Broadcast Encryption,以及我不熟悉的Aggregate Signatures以外,都是近10年才提出的密码学新概念。而密码学新概念从提出到实际使用,怎么也得需要15年以上的时间。要知道,RSA是1976年提的,理论上漏洞一堆,而且效率实在是不太高,现在照样用;椭圆曲线密码学近5年才逐渐被使用;至于2001年提出的Identity-Based Encryption,到今年正好15年,应该会开始使用了吧… 所以,Multilinear Map更多的是一种理论讨论,离实际使用还早得很,从应用角度说还有点远。

“粗看上去,杰瑞格等人提出的GGH Map到处都是漏洞,但你就是无论如何也攻破不了它。”胡予濮回忆他初次接触GGH时说,“GGH提出者均是当今国际上顶尖的密码研究工作者,他们的方案十分完整,已经列举了各种能够想到的攻击方法,并都进行了尝试。”
所谓到处是漏洞,根源在于GGH Map的公开参数中给出了很多能够帮助破解的信息。尤其是新闻稿中提到的zero-test,更是让人感觉全是漏洞。

所谓zero-test,是指GGH Map中存在一个函数,可以帮助验证群中两个元素是否相等。这不是逗我么… 两个元素是否相等还需要一个特殊的函数吗?这是因为GGH Map的构造方式是在Lattice中的一个原始向量上增加一个噪声,只不过这个噪声特别小。因此,对于群中的同一个元素,实际上有指数多种表述方法。zero-test的目的是,检测两个元素的差是否足够小。如果足够小的话,意味着这两个元素都是在同一个原始向量上增加小噪声得来的,这是就认为这两个元素相等。

这有什么帮助呢?既然我能检测两个元素是否相等,在给定一个元素后,我能否找另一个和给定元素相等的元素,然后求这个元素的原始向量呢?而这篇文章的工作指出,我们可以利用zero-test,找到一个和给定元素相等的元素,并求得这个元素的原始向量。只不过所找到这个元素的原始向量不是给定元素对应的原始向量。换句话说,找到的这个元素中所添加的噪声比较大。不过没关系,反正两个元素相等,并且找到了个原始向量。

严格来说,描述应该是这样的:


找到了GGH的漏洞,原作者也承认了胡予濮提出的攻击是有效的,但密码学领域的这场智力较量却刚刚开始。原来,Shai Halevi随即在信中指出,胡予濮提供的第一版手稿中,攻击的第一步所采用的弱离散对数攻击方法,是原文已有的。“回来找资料,发现人家在一个报告中确实提过。”胡予濮介绍说,“但是在攻击的第二步中,我们提出了一种变形的编码/零测试工具,该工具是我们的原创性工作,也是攻击的核心技术。”
弱离散攻击方法,就是上图的Weak DLP。这段话实际的意思是,Shai Halevi认为,胡教授第一步的工作并不是原创的,原文中已经有了。这句话潜在的意思是:这个工作的原创性是否不够?所以会有后面一段原创性工作的描述。

2015年4月份,胡予濮及其博士生贾惠文提出组合精确覆盖问题的概念,对精确覆盖这一NP完备问题进行弱化,同时利用改进的编码/零测试工具,又将基于GGH的Witness Encryption方案攻破了。“这一方案的作者之一,密码学家Amit Sahai来信提醒说,我们只是在编码工具公开的情况下才攻破的,这一方案还可以在编码工具隐藏时进行,让我们在正式发表时进行修改。一段时间以后,我们进一步深入研究,把编码工具隐藏的那种方案,最后也给出了有效的密码分析,真正做到了无论在什么情况下,基于GGH的证据加密都不安全。”胡予濮回忆到。
Witness Encryption是在计算机顶级会议STOC 2013上的成果,原始论文是"Witness Encryption and its Applications",作者嘛,看看熟悉的人吧:Sanjam Garg, Craig Gentry, Amit Sahai, Brent Waters。Witness Encryption是新提出的一种密码学原语,这个原语的特点是:这是个加密算法,但这个加密算法没有Key Generation过程。

我靠,又逗我,没有密钥生成,公钥私钥哪里来呢?实际上,Witness Encryption的公钥私钥是一个NP-hard问题。举例来说,我生成了一个曼哈顿回路问题实例,把这个问题实例作为公钥,问题解作为私钥。也就是说:
Can we encrypt a message so that it can only be opened by a recipient who knows a witness to an NP relation?
这样的好处是,Key Generation可以特别快。Witness Encryption的构造是基于GGH Map的。构造方法就是利用前面提到的Exact-3-Cover Problem这个NP-Complete问题构造实例。由于任意NP-Complete问题都可以互相归约,所以我们就可以在多项式时间复杂度下得到任意一个NP-Complete问题的Witness Encryption。

至于编码工具公开/编码工具隐藏的问题,涉及到了Multilinear Map的具体构造,过于复杂了,有兴趣的知友们可以看一看前面我给出的一个PPT:多线性映射方案分析Cryptanalysis of the GGH’13 multilinear map_百度文库

40年前,Diffie-Hellman解决的两方密钥交换问题,成为今天整个互联网信息安全传输的基础;而GGH Map要想解决的问题,是实现非交互多方密钥交换。换句话说,如果把经典密码学比作“1”,那么Diffie-Hellman解决的就是“2”的问题,但却带出了“≥3”该如何解决的难题。如果“≥3”的问题真的彻底解决了,能用到什么场景中,也许我们绞尽脑汁也想不到、想不全。
题主看到这句话产生的疑问。简单的说,如果“≥3”的问题真的彻底解决了,密码学将引发彻底的革命:所有看似不可能实现的功能都将实现。举例来说:最开始提到的云安全存储、云安全计算将得到彻底解决;多方安全群组通信将得到彻底解决;软件盗版问题将得到彻底解决;等等等等。

=============================
取得这样的研究成果,对于国内密码学界来说可以是一种必然。与其他领域的发展相比,密码学领域的特性就导致国内一定可以追上国际最顶级研究成果:所有理论算法可以公开也必须公开,所有讨论可以在全世界范围内进行。密码学的研究具有很强的传承性,比的更多的是快。所以很多新思想早已经存在,但在看到之前,别人已经往前走了很长的一步。所以,只要国内研究者可以在顶级研究团队研究一段时间,一定可以将一些前沿思想带回国内,从而打造顶级的研究团队。

近几年的成果也表明,国内水平有了突飞猛进的发展。从开始时好几年没有一篇三大会议论文,到现在几乎每年都会出现5-6篇国内的研究成果。

密码学,确实很有意思。

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

这个人很懒,什么也没留下...
粉丝0 阅读640 回复0
关注我们
一起来触电吧

客服电话:400-234-9000

客服邮箱:ceo@chudianw.cn

周一至周五 9:00-18:00

公司地址:威高广场迪尚大厦海景写字楼A座1988

Powered by 触电新闻 @ 2018-2019 触电网