f***y
发帖数: 4447 | 1 http://bbsnew.netbig.com/thread-2666841-1-1.html
国际密码学领域的一场顶级智力较量
——西安电子科技大学胡予濮教授攻破GGH密码方案
■ 记者 秦明
一个原本有望成为国际密码学研究新技术的GGH密码映射方案，最近被西安电子科技大
学综合业务网理论及关键技术国家重点实验室的胡予濮教授攻破。胡予濮教授与他的博
士研究生贾惠文，对GGH映射本身以及基于GGH映射的各类高级密码应用进行了颠覆性的
否定。该研究成果——《GGH映射的密码分析》（Cryptanalysis of GGH Map），日前
经过同行专家的严格评审，已经被2016年欧洲密码年会（Eurocrypt 2016，简称欧密）
正式接收。这一会议和美洲密码年会（简称美密），被公认为密码学界最著名的两大国
际会议。2016年5月8日，胡予濮将赴奥地利维也纳，在欧密会上，正式向全世界的密码
同行报告这一突破性成果。
问题来自哪里？现代密码学遗留的公开问题
故事得从1976年讲起。这一年，斯坦福大学的密码学家惠特菲尔德·迪菲（Whitfield
Diffie）和马丁·赫尔曼（Martin Hellman），共同发表了一篇题为《密码学的新方向
》（New Directions in Cryptography）的学术论文，首次提出公钥密码体制的思想，
引发了密码学史上的革命。同时，他们给出非交互密钥协商的概念，并基于离散对数问
题给出了具体的实现。
迪菲-赫尔曼密钥交换的提出，颠覆了人们“不事先进行秘密共享是无法进行保密通信
”的传统观念，使得用户可以在一个完全开放的信道上，进行秘密共享，实现保密通信
。这一思想上的突破，成为了现今密钥交换系统的基础，被广泛应用于网络通信。与经
典密码学相对应，业界将1976年定为现代密码学元年。迪菲与赫尔曼也因此获得美国计
算机协会ACM授予的2015年度“图灵奖”。
然而，迪菲与赫尔曼的工作只是第一步，他们实现了无需交互就可以在公开信道上共享
密钥，但仅限于两方。如何将这一机制扩展至三方乃至多方，一直是现代密码学遗留下
来没有解决的公开问题。接下来的几十年中，全世界最聪明的密码学者们都在试图解决
这个公开问题，然而研究始终未能取得突破性进展。
直到2000年，密码学家安托尼·尤克斯（Antoine Joux）利用双线性对，设计了第一个
非交互的三方密钥交换协议，在该问题上取得了阶段性突破，但仍无法将这种思想推广
到四方以上参与者的密钥交换中。2003年，密码学家丹·波恩（Dan Boneh）和艾力斯
·西尔弗伯格（Alice Silverberg）提出多线性映射这一概念，并指出多线性映射不但
可以解决多方秘密交换这一公开问题，而且还可以用于构造其他更高级的密码应用方案
，但他们却无法给出具体的代数实现。
在波恩和西尔弗伯格给出“在代数几何领域内不大可能构造出多线性映射”这一悲观结
论后的十年间，密码学界关于多线性映射的研究成果寥寥无几。直到2013年的欧密会，
三位密码天才提出的GGH方案，才让解决这个问题出现了一道曙光。
2013年的欧密会上，时为加州大学洛杉矶分校的博士生萨吉·杰瑞格（Sanjam Garg）
，以及IBM研究员克雷格·金特里（Craig Gentry）和塞·哈勒维（Shai Halevi），共
同提交了一篇论文《基于理想格的候选多线性映射方案》（Candidate Multilinear
Maps from Ideal Lattices）。该论文提出一个分级编码系统（GES）概念，并以此在
理想格上实现了第一个多线性映射方案（GGH映射，取名于三位作者姓名Garg、Gentry
和Halevi的首字母），进而解决了现代密码学遗留的那个公开问题，这篇论文也因此获
得当年欧密会的最佳论文奖。
“GGH多线性映射方案，对密码学界产生了深远影响，迅速在国际密码学界引发了多线
性研究的热潮。”胡予濮介绍说。因为这个里程碑式的密码映射方案，不仅为密码学界
遗留下来的公开问题找到了答案，也促使了其他近似多线性映射方案的构造，并有望在
未来广泛应用于证据加密、广播加密、属性加密、功能加密、聚合签名等多种高级的应
用场合，从而将现代密码学大大地向前推动一步！
“但由于多线性映射的特殊性，杰瑞格等人无法直接证明GGH密码方案是安全可行的，
所以他们在论文中采取穷举攻击的办法，尝试了所有现存的以及他们自己提出的攻击方
法，来间接表明该方案是安全的。”胡予濮介绍说，“2014年5月底，我在日本九州大
学进行学术访问时，无意间了解到了这个信息，觉得很有意义，就尝试着要对它进行密
码分析，也就是破解。”
如何实现攻破？釜底抽薪打出一组漂亮的组合拳
“粗看上去，杰瑞格等人提出的GGH密码映射方案，到处都是漏洞，但你就是无论如何
也攻破不了它。”胡予濮回忆他初次接触GGH时说，“GGH提出者均是当今国际上顶尖的
密码研究工作者，他们的方案十分完整，已经列举了各种能够想到的攻击方法，并都进
行了尝试。”
从2014年5月底到2015年2月中旬，胡予濮的脑海里全是GGH密码方案，他完全沉醉在格
公钥密码、近世代数、数论、概率统计以及离散数学的世界里。“2015年春节，我是在
宾夕法尼亚州特拉华河畔费城的女儿家中度过的。我妻子对我女儿说，你看你爸都苍老
了许多。”胡予濮说，“一个如此有意思的问题摆在我面前没解决，茶不思饭不想，那
是正常的事儿。”
在攻破GGH密码方案的过程中，最具有纪念意义的这一天，是2015年3月7日。“这天，
我一晚上都没睡觉，突然觉得GGH的结构有些不对，半夜就起来开始在纸上验算。”胡
予濮兴奋地回忆起当时的情景，“到了第二天早上，还是觉得不对，又躺在床上稍微休
息了一会，希望等脑子清醒了继续推算。到了中午的时候，我再一步一步进行了认真验
证，第一次发现了GGH的漏洞确实是存在的！”
即便自己经过多次推导，已经验证了GGH存在漏洞，但胡予濮还是没有轻易下结论说攻
破了这一方案。他将演算思路告诉自己的博士生贾惠文，要求他对该过程进行反复推导
和验证。最终，他们得出一致结论，攻击过程正确无误，一颗悬着的心终于落地了。
“有大半年的时间，胡老师和我到处碰壁、毫无成果，各种攻击方法尝试了有50种之多
。有一次，我们甚至都将已经写好的文章投递出去了，但大半夜胡老师发现推导过程有
漏洞，让我赶紧撤稿。”论文第二作者，博士生贾惠文感叹地说。
2015年3月15日，为了最后确认已经攻破了GGH密码方案，胡予濮将描述了攻击过程的手
稿，发给了提出该方案的三位原作者。4天后，也就是3月19日凌晨5时16分，该方案的
第三作者塞·哈勒维代表三人回函称：“感谢您发送的手稿，您描述的攻击方式，似乎
的确打破了我们在GGH一文中提到的多方密钥协商机制。”（Thank you for sending
us the manuscript. Indeed the attack that you describe there seem to break
the multi-partite key agreement form the GGH paper.）
找到了GGH的漏洞，原作者也承认了胡予濮提出的攻击是有效的，但密码学领域的这场
智力较量却刚刚开始。原来，塞·哈勒维随即在信中指出，胡予濮提供的第一版手稿中
，攻击的第一步所采用的弱离散对数攻击方法，是原文已有的。“回来找资料，发现人
家在一个报告中确实提过。”胡予濮介绍说，“但是在攻击的第二步中，我们提出了一
种变形的编码/零测试工具，该工具是我们的原创性工作，也是攻击的核心技术。”
2015年4月份，胡予濮及其博士生贾惠文提出组合精确覆盖问题的概念，对精确覆盖这
一NP完备问题进行弱化，同时利用改进的编码/零测试工具，又将基于GGH的证据加密方
案攻破了。“这一方案的作者之一，密码学家阿米特·萨海（Amit Sahai）来信提醒说
，我们只是在编码工具公开的情况下才攻破的，这一方案还可以在编码工具隐藏时进行
，让我们在正式发表时进行修改。一段时间以后，我们进一步深入研究，把编码工具隐
藏的那种方案，最后也给出了有效的密码分析，真正做到了无论在什么情况下，基于
GGH的证据加密都不安全。”胡予濮回忆到。
胡予濮将修改后的论文再次给原作者发过去，换来的是一片沉默。
实际上，胡予濮及其博士生的主要成果，可以总结为四个方面：一是攻破了GGH映射的
安全性假设；二是攻破了基于GGH映射的非交互多方密钥交换协议；三是攻破了基于GGH
映射的第一个证据加密方案（无论编码工具公开还是隐藏）；四是给出GGH映射的两个
修改方案，并对它们进行有效攻击。
“我们的成果是对GGH的一个否定，我们打出的这套组合拳，是对GGH密码映射方案的一
次釜底抽薪似的攻击。几乎可以断言，在编码工具公开的情况下，任何基于GGH映射的
密码应用都是不安全的；在编码工具隐藏的情况下，至少有一个基于GGH映射的密码应
用是不安全的；GGH映射很难进行简单修改来避开我们的攻击。”胡予濮说。
研究意义何在？推动现代密码学不断向前发展
密码学和信息安全有什么关系？密码技术是信息安全的核心技术。
胡予濮打了一个比方说，如果把信息安全当作一个有大门、有围墙的院子。要想进院子
，办法有多种，可以翻墙进去，也可以推倒墙进去，还可以挖个洞爬进去，但正常合理
的办法是把门上的锁打开，然后推开门走进去。密码技术就是大门上的那把锁，锁的质
量好不好，虽然决定不了院子是否安全，但却是合法通行的关键。密码技术的不断研究
，推动着信息安全技术的发展。
而密码学自身又如何发展呢？胡予濮介绍说，现代密码学的发展，就是密码编码学和密
码分析学“相互打架”的过程，也就是设计密码和破解密码两拨人的较量。设计密码的
人希望自己的密码体制难以被对手攻破，破解密码的人希望自己可以破解敌方的所有密
码体制。“学术研究上，破解的目的是帮助原有密码变得更加完善，推动现代密码学向
前发展。”
当被询问破解GGH密码方案实际意义何在时，胡予濮介绍说：“GGH可以被看作是一种密
码原语，一旦被证明安全可行，就可以在它的基础上构造出许多新的密码体制，极大地
丰富未来密码应用的场景。”但胡予濮表示，他很难用一个大家都懂的生活中的场景来
解释回答这个问题，他回忆了一段历史：
40年前，迪菲与赫尔曼解决的两方密钥交换问题，成为今天整个互联网信息安全传输的
基础；而GGH密码映射要想解决的问题，是实现非交互多方密钥交换。换句话说，如果
把经典密码学比作“1”，那么迪菲与赫尔曼解决的就是“2”的问题，但却带出了“≥
3”该如何解决的难题。如果“≥3”的问题真的彻底解决了，能用到什么场景中，也许
我们绞尽脑汁也想不到、想不全。
胡予濮说，现在的国际密码学界其实就是一个公开的智力角斗场。密码学家都把自己最
好的研究成果，发表在每年定期召开的欧密会和美密会上，但在发表之前，他们往往都
会把手稿公布在国际密码研究协会的在线论坛，供同行批评指正。
胡予濮教授的手稿自公布以后，吸引了全世界研究多线性映射密码学家的目光。除了上
述已经提到的三名原作者和密码学家阿米特·萨海外，还有包括日本东京技术研究所草
川恵太（Keita Xagawa）研究员、韩国首尔大学池東杓（Dong-Pyo Chi）教授，以及一
些国内学者的关注。攻破多线性映射其他两个构造方案的研究团队，也对胡予濮的工作
给予了肯定，说胡予濮做了他们想做而没做成的事情。
在谈到接下来的工作时，胡予濮指出，虽然他们在破解GGH密码方案的过程中已经做了
不少工作，但一切才刚刚开始，下一步他们还将对基于GGH映射的不可区分混淆进行分
析。“我还想给年轻人做个榜样，更想为提高西电密码学的学术地位贡献一份力量。西
安电子科技大学的密码学在国内享有盛誉，是中国密码学的发源地，有‘一肖二王’这
样的老专家、老前辈，我希望大家把这块金字招牌擦得更亮！” |
h*******i
发帖数: 4386 | |
x*****q
发帖数: 2336 | 3 这一肖二王是谁啊。
【在 f***y 的大作中提到】
: http://bbsnew.netbig.com/thread-2666841-1-1.html
: 国际密码学领域的一场顶级智力较量
: ——西安电子科技大学胡予濮教授攻破GGH密码方案
: ■ 记者 秦明
: 一个原本有望成为国际密码学研究新技术的GGH密码映射方案，最近被西安电子科技大
: 学综合业务网理论及关键技术国家重点实验室的胡予濮教授攻破。胡予濮教授与他的博
: 士研究生贾惠文，对GGH映射本身以及基于GGH映射的各类高级密码应用进行了颠覆性的
: 否定。该研究成果——《GGH映射的密码分析》（Cryptanalysis of GGH Map），日前
: 经过同行专家的严格评审，已经被2016年欧洲密码年会（Eurocrypt 2016，简称欧密）
: 正式接收。这一会议和美洲密码年会（简称美密），被公认为密码学界最著名的两大国
|
z**********e
发帖数: 22064 | 4 从美国偷的吧。
否则无法解释为什么在国内几十年都没灵感，到女儿家住了几个月就立马变成神人了。 |
g********0
发帖数: 6201 | 5 能搞到就行，管他什么手段，想当年美国破恩格码的时候都是直接去德国潜艇上抢。。。
【在 z**********e 的大作中提到】
: 从美国偷的吧。
: 否则无法解释为什么在国内几十年都没灵感，到女儿家住了几个月就立马变成神人了。
|
b********n
发帖数: 38600 | 6 '从美国偷的吧.'
老将屁股决定大脑，lol
【在 z**********e 的大作中提到】
: 从美国偷的吧。
: 否则无法解释为什么在国内几十年都没灵感，到女儿家住了几个月就立马变成神人了。
|
T*R
发帖数: 36302 | 7 一个问题，他如果真找到了别人密码的漏洞，为什么发表出来？
告诉国家安全部，不是可以随便破解别人的密码了？
那是为国家立大功。
就像grace 高，破解了北斗密码，就混了个香槟的教授。 |
z**********e
发帖数: 22064 | 8 那是电影。
搞对方的密码，有一个原则就是不能让对方知道你搞到了他的密码，否则就没有用了。
美国搞到日本的密码，是因为日本进攻威克岛的一艘军舰被击沉，日本以为沉没了（密
码本是水溶墨水印的，一沾水就啥都看不到了），就放心撤退了；其实此舰是搁浅了，
密码没有沾水，被美军缴获了。
虽然日军后来很快就再次进攻占领了威克岛，可是密码已经安全转移了。
。。
【在 g********0 的大作中提到】
: 能搞到就行，管他什么手段，想当年美国破恩格码的时候都是直接去德国潜艇上抢。。。
|
x*****q
发帖数: 2336 | 9 GGH密码方案是2013年在欧密会发表的，几十年没有灵感...
还有，从美国偷的...感觉很思维很跳跃。
【在 z**********e 的大作中提到】
: 从美国偷的吧。
: 否则无法解释为什么在国内几十年都没灵感，到女儿家住了几个月就立马变成神人了。
|
x****o
发帖数: 21566 | 10 估计是因为GGH还没有大范围的应用，这个研究貌似很有意义，至少GGH需要改进
【在 T*R 的大作中提到】
: 一个问题，他如果真找到了别人密码的漏洞，为什么发表出来？
: 告诉国家安全部，不是可以随便破解别人的密码了？
: 那是为国家立大功。
: 就像grace 高，破解了北斗密码，就混了个香槟的教授。
|
