国际密码学领域的一场顶级智力较量

——西安电子科技大学胡予濮教授攻破GGH密码方案

■记者秦明

一个原本有望成为国际密码学研究新技术的GGH密码映射方案，最近被西安电子科技大学综合业务网理论及关键技术国家重点实验室的胡予濮教授攻破。胡予濮教授与他的博士研究生贾惠文，对GGH映射本身以及基于GGH映射的各类高级密码应用进行了颠覆性的否定。该研究成果——《GGH映射的密码分析》（Cryptanalysis of GGH Map），日前经过同行专家的严格评审，已经被2016年欧洲密码年会（Eurocrypt 2016，简称欧密）正式接收。这一会议和美洲密码年会（简称美密），被公认为密码学界最著名的两大国际会议。2016年5月8日，胡予濮将赴奥地利维也纳，在欧密会上，正式向全世界的密码同行报告这一突破性成果。

胡予濮教授和他的博士研究生贾慧文

问题来自哪里？现代密码学遗留的公开问题

故事得从1976年讲起。这一年，斯坦福大学的密码学家惠特菲尔德·迪菲（Whitfield Diffie）和马丁·赫尔曼（Martin Hellman），共同发表了一篇题为《密码学的新方向》（New Directions in Cryptography）的学术论文，首次提出公钥密码体制的思想，引发了密码学史上的革命。同时，他们给出非交互密钥协商的概念，并基于离散对数问题给出了具体的实现。

Whitfield Diffie 和 Martin Hellman

迪菲-赫尔曼密钥交换的提出，颠覆了人们“不事先进行秘密共享是无法进行保密通信”的传统观念，使得用户可以在一个完全开放的信道上，进行秘密共享，实现保密通信。这一思想上的突破，成为了现今密钥交换系统的基础，被广泛应用于网络通信。与经典密码学相对应，业界将1976年定为现代密码学元年。迪菲与赫尔曼也因此获得美国计算机协会ACM授予的2015年度“图灵奖”。

然而，迪菲与赫尔曼的工作只是第一步，他们实现了无需交互就可以在公开信道上共享密钥，但仅限于两方。如何将这一机制扩展至三方乃至多方，一直是现代密码学遗留下来没有解决的公开问题。接下来的几十年中，全世界最聪明的密码学者们都在试图解决这个公开问题，然而研究始终未能取得突破性进展。

直到2000年，密码学家安托尼·尤克斯（Antoine Joux）利用双线性对，设计了第一个非交互的三方密钥交换协议，在该问题上取得了阶段性突破，但仍无法将这种思想推广到四方以上参与者的密钥交换中。2003年，密码学家丹·波恩（Dan Boneh）和艾力斯·西尔弗伯格（Alice Silverberg）提出多线性映射这一概念，并指出多线性映射不但可以解决多方秘密交换这一公开问题，而且还可以用于构造其他更高级的密码应用方案，但他们却无法给出具体的代数实现。

Antoine Joux

在波恩和西尔弗伯格给出“在代数几何领域内不大可能构造出多线性映射”这一悲观结论后的十年间，密码学界关于多线性映射的研究成果寥寥无几。直到2013年的欧密会，三位密码天才提出的GGH方案，才让解决这个问题出现了一道曙光。

2013年的欧密会上，时为加州大学洛杉矶分校的博士生萨吉·杰瑞格（Sanjam Garg），以及IBM研究员克雷格·金特里（Craig Gentry）和塞·哈勒维（Shai Halevi），共同提交了一篇论文《基于理想格的候选多线性映射方案》（Candidate Multilinear Maps from Ideal Lattices）。该论文提出一个分级编码系统（GES）概念，并以此在理想格上实现了第一个多线性映射方案（GGH映射，取名于三位作者姓名Garg、Gentry和Halevi的首字母），进而解决了现代密码学遗留的那个公开问题，这篇论文也因此获得当年欧密会的最佳论文奖。

Sanjam Garg、Craig Gentry 和 Shai 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 from the GGH paper.）

找到了GGH的漏洞，原作者也承认了胡予濮提出的攻击是有效的，但密码学领域的这场智力较量却刚刚开始。原来，塞·哈勒维随即在信中指出，胡予濮提供的第一版手稿中，攻击的第一步所采用的弱离散对数攻击方法，是原文已有的。“回来找资料，发现人家在一个报告中确实提过。”胡予濮介绍说，“但是在攻击的第二步中，我们提出了一种变形的编码/零测试工具，该工具是我们的原创性工作，也是攻击的核心技术。”

2015年4月份，胡予濮及其博士生贾惠文提出组合精确覆盖问题的概念，对精确覆盖这一NP完备问题进行弱化，同时利用改进的编码/零测试工具，又将基于GGH的证据加密方案攻破了。“这一方案的作者之一，密码学家阿米特·萨海（Amit Sahai）来信提醒说，我们只是在编码工具公开的情况下才攻破的，这一方案还可以在编码工具隐藏时进行，让我们在正式发表时进行修改。一段时间以后，我们进一步深入研究，把编码工具隐藏的那种方案，最后也给出了有效的密码分析，真正做到了无论在什么情况下，基于GGH的证据加密都不安全。”胡予濮回忆到。

Amit Sahai

胡予濮将修改后的论文再次给原作者发过去，换来的是一片沉默。

实际上，胡予濮及其博士生的主要成果，可以总结为四个方面：一是攻破了GGH映射的安全性假设；二是攻破了基于GGH映射的非交互多方密钥交换协议；三是攻破了基于GGH映射的第一个证据加密方案（无论编码工具公开还是隐藏）；四是给出GGH映射的两个修改方案，并对它们进行有效攻击。

“我们的成果是对GGH的一个否定，我们打出的这套组合拳，是对GGH密码映射方案的一次釜底抽薪似的攻击。几乎可以断言，在编码工具公开的情况下，任何基于GGH映射的密码应用都是不安全的；在编码工具隐藏的情况下，至少有一个基于GGH映射的密码应用是不安全的；GGH映射很难进行简单修改来避开我们的攻击。”胡予濮说。

研究意义何在？推动现代密码学不断向前发展

密码学和信息安全有什么关系？密码技术是信息安全的核心技术。

胡予濮打了一个比方说，如果把信息安全当作一个有大门、有围墙的院子。要想进院子，办法有多种，可以翻墙进去，也可以推倒墙进去，还可以挖个洞爬进去，但正常合理的办法是把门上的锁打开，然后推开门走进去。密码技术就是大门上的那把锁，锁的质量好不好，虽然决定不了院子是否安全，但却是合法通行的关键。密码技术的不断研究，推动着信息安全技术的发展。

而密码学自身又如何发展呢？胡予濮介绍说，现代密码学的发展，就是密码编码学和密码分析学“相互打架”的过程，也就是设计密码和破解密码两拨人的较量。设计密码的人希望自己的密码体制难以被对手攻破，破解密码的人希望自己可以破解敌方的所有密码体制。“学术研究上，破解的目的是帮助原有密码变得更加完善，推动现代密码学向前发展。”

当被询问破解GGH密码方案实际意义何在时，胡予濮介绍说：“GGH可以被看作是一种密码原语，一旦被证明安全可行，就可以在它的基础上构造出许多新的密码体制，极大地丰富未来密码应用的场景。”但胡予濮表示，他很难用一个大家都懂的生活中的场景来解释回答这个问题，他回忆了一段历史：

40年前，迪菲与赫尔曼解决的两方密钥交换问题，成为今天整个互联网信息安全传输的基础；而GGH密码映射要想解决的问题，是实现非交互多方密钥交换。换句话说，如果把经典密码学比作“1”，那么迪菲与赫尔曼解决的就是“2”的问题，但却带出了“≥3”该如何解决的难题。如果“≥3”的问题真的彻底解决了，能用到什么场景中，也许我们绞尽脑汁也想不到、想不全。

胡予濮说，现在的国际密码学界其实就是一个公开的智力角斗场。密码学家都把自己最好的研究成果，发表在每年定期召开的欧密会和美密会上，但在发表之前，他们往往都会把手稿公布在国际密码研究协会的在线论坛，供同行批评指正。

胡予濮教授的手稿自公布以后，吸引了全世界研究多线性映射密码学家的目光。除了上述已经提到的三名原作者和密码学家阿米特·萨海外，还有包括日本东京技术研究所草川恵太（Keita Xagawa）研究员、韩国首尔大学池東杓（Dong-Pyo Chi）教授，以及一些国内学者的关注。攻破多线性映射其他两个构造方案的研究团队，也对胡予濮的工作给予了肯定，说胡予濮做了他们想做而没做成的事情。

在谈到接下来的工作时，胡予濮指出，虽然他们在破解GGH密码方案的过程中已经做了不少工作，但一切才刚刚开始，下一步他们还将对基于GGH映射的不可区分混淆进行分析。“我还想给年轻人做个榜样，更想为提高西电密码学的学术地位贡献一份力量。西安电子科技大学的密码学在国内享有盛誉，是中国密码学的发源地，有‘一肖二王’这样的老专家、老前辈，我希望大家把这块金字招牌擦得更亮！”

延伸阅读

学生心中的又一个父亲——记西安电子科技大学2015年“师德标兵”胡予濮教授

胡予濮教授是一个特别简单纯粹的人，科研俨然已经不是胡予濮老师的工作，而是深深地浸入到了他的生活和生命之中，他的每一个成果其实都是在他散步的时候想出来的。在普通人看来，胡予濮老师有点书呆子气。“找胡老师聊天最好的开场白就是由密码学学术问题开始，因为这会引起他异乎寻常的兴趣，”他的学生王保仓曾这样提醒记者。胡予濮老师对学术的痴迷到了钻牛角尖的地步。王保仓老师回忆说，2009年密码学上的突破——Gentry的全同态加密被提出来的时候，胡予濮老师就让他的三个博士生去关注这个领域，但是学生普遍反映全同态加密是密码学上的硬骨头，论文异常难懂。胡老师没有责怪学生，而是自己潜心钻研，一篇短短9页的论文，胡予濮老师花了整整三个月的时间终于啃透了，在彻底悟透了这篇论文之后，他赶紧给他的几个博士生打电话，召集大家进行了三次讲座，彻底把这篇论文给学生们讲清楚了。（全文）

【澎湃新闻】我国专家攻破GGH密码方案，欧洲密码年会正式接收成果

【中青在线】我国专家攻破GGH密码方案

【西安日报】西安专家攻破GGH密码方案

【西安晚报】西电胡予濮教授攻破国际密码学难题