西安電子科技大學(xué)

厚德 / 求真 / 礪學(xué) / 篤行

   重磅消息！

胡予濮教授和他的博士研究生賈惠文

 問(wèn)題來(lái)自哪里？現(xiàn)代密碼學(xué)遺留的公開(kāi)問(wèn)題

故事得從1976年講起。這一年，斯坦福大學(xué)的密碼學(xué)家惠特菲爾德·迪菲（Whitfield Diffie）和馬丁·赫爾曼（Martin Hellman），共同發(fā)表了一篇題為《密碼學(xué)的新方向》（NewDirections in Cryptography）的學(xué)術(shù)論文，首次提出公鑰密碼體制的思想，引發(fā)了密碼學(xué)史上的革命。同時(shí)，他們給出非交互密鑰協(xié)商的概念，并基于離散對(duì)數(shù)問(wèn)題給出了具體的實(shí)現(xiàn)。

Whitfield Diffie 和 Martin Hellman

迪菲-赫爾曼密鑰交換的提出，顛覆了人們“不事先進(jìn)行秘密共享是無(wú)法進(jìn)行保密通信”的傳統(tǒng)觀念，使得用戶可以在一個(gè)完全開(kāi)放的信道上，進(jìn)行秘密共享，實(shí)現(xiàn)保密通信。這一思想上的突破，成為了現(xiàn)今密鑰交換系統(tǒng)的基礎(chǔ)，被廣泛應(yīng)用于網(wǎng)絡(luò)通信。與經(jīng)典密碼學(xué)相對(duì)應(yīng)，業(yè)界將1976年定為現(xiàn)代密碼學(xué)元年。迪菲與赫爾曼也因此獲得美國(guó)計(jì)算機(jī)協(xié)會(huì)ACM授予的2015年度“圖靈獎(jiǎng)”。

然而，迪菲與赫爾曼的工作只是第一步，他們實(shí)現(xiàn)了無(wú)需交互就可以在公開(kāi)信道上共享密鑰，但僅限于兩方。如何將這一機(jī)制擴(kuò)展至三方乃至多方，一直是現(xiàn)代密碼學(xué)遺留下來(lái)沒(méi)有解決的公開(kāi)問(wèn)題。接下來(lái)的幾十年中，全世界最聰明的密碼學(xué)者們都在試圖解決這個(gè)公開(kāi)問(wèn)題，然而研究始終未能取得突破性進(jìn)展。

直到2000年，密碼學(xué)家安托尼·尤克斯（Antoine Joux）利用雙線性對(duì)，設(shè)計(jì)了第一個(gè)非交互的三方密鑰交換協(xié)議，在該問(wèn)題上取得了階段性突破，但仍無(wú)法將這種思想推廣到四方以上參與者的密鑰交換中。2003年，密碼學(xué)家丹·波恩（Dan Boneh）和艾力斯·西爾弗伯格（Alice Silverberg）提出多線性映射這一概念，并指出多線性映射不但可以解決多方秘密交換這一公開(kāi)問(wèn)題，而且還可以用于構(gòu)造其他更高級(jí)的密碼應(yīng)用方案，但他們卻無(wú)法給出具體的代數(shù)實(shí)現(xiàn)。

Antoine Joux

在波恩和西爾弗伯格給出“在代數(shù)幾何領(lǐng)域內(nèi)不大可能構(gòu)造出多線性映射”這一悲觀結(jié)論后的十年間，密碼學(xué)界關(guān)于多線性映射的研究成果寥寥無(wú)幾。直到2013年的歐密會(huì)，三位密碼天才提出的GGH方案，才讓解決這個(gè)問(wèn)題出現(xiàn)了一道曙光。

2013年的歐密會(huì)上，時(shí)為加州大學(xué)洛杉磯分校的博士生薩吉·杰瑞格（Sanjam Garg），以及IBM研究員克雷格·金特里（Craig Gentry）和塞·哈勒維（Shai Halevi），共同提交了一篇論文《基于理想格的候選多線性映射方案》（CandidateMultilinear Maps from Ideal Lattices）。該論文提出一個(gè)分級(jí)編碼系統(tǒng)（GES）概念，并以此在理想格上實(shí)現(xiàn)了第一個(gè)多線性映射方案（GGH映射，取名于三位作者姓名Garg、Gentry和Halevi的首字母），進(jìn)而解決了現(xiàn)代密碼學(xué)遺留的那個(gè)公開(kāi)問(wèn)題，這篇論文也因此獲得當(dāng)年歐密會(huì)的最佳論文獎(jiǎng)。

Sanjam Garg、Craig Gentry 和 Shai Halevi

“GGH多線性映射方案，對(duì)密碼學(xué)界產(chǎn)生了深遠(yuǎn)影響，迅速在國(guó)際密碼學(xué)界引發(fā)了多線性研究的熱潮?！焙桢Ы榻B說(shuō)。因?yàn)檫@個(gè)里程碑式的密碼映射方案，不僅為密碼學(xué)界遺留下來(lái)的公開(kāi)問(wèn)題找到了答案，也促使了其他近似多線性映射方案的構(gòu)造，并有望在未來(lái)廣泛應(yīng)用于證據(jù)加密、廣播加密、屬性加密、功能加密、聚合簽名等多種高級(jí)的應(yīng)用場(chǎng)合，從而將現(xiàn)代密碼學(xué)大大地向前推動(dòng)一步！

“但由于多線性映射的特殊性，杰瑞格等人無(wú)法直接證明GGH密碼方案是安全可行的，所以他們?cè)谡撐闹胁扇「F舉攻擊的辦法，嘗試了所有現(xiàn)存的以及他們自己提出的攻擊方法，來(lái)間接表明該方案是安全的。”胡予濮介紹說(shuō)，“2014年5月底，我在日本九州大學(xué)進(jìn)行學(xué)術(shù)訪問(wèn)時(shí)，無(wú)意間了解到了這個(gè)信息，覺(jué)得很有意義，就嘗試著要對(duì)它進(jìn)行密碼分析，也就是破解?！?/span>

 如何實(shí)現(xiàn)攻破？釜底抽薪打出一組漂亮的組合拳

        “粗看上去，杰瑞格等人提出的GGH密碼映射方案，到處都是漏洞，但你就是無(wú)論如何也攻破不了它?！焙桢Щ貞浰醮谓佑|GGH時(shí)說(shuō)，“GGH提出者均是當(dāng)今國(guó)際上頂尖的密碼研究工作者，他們的方案十分完整，已經(jīng)列舉了各種能夠想到的攻擊方法，并都進(jìn)行了嘗試?！?/p>

從2014年5月底到2015年2月中旬，胡予濮的腦海里全是GGH密碼方案，他完全沉醉在格公鑰密碼、近世代數(shù)、數(shù)論、概率統(tǒng)計(jì)以及離散數(shù)學(xué)的世界里?！?015年春節(jié)，我是在賓夕法尼亞州特拉華河畔費(fèi)城的女兒家中度過(guò)的。我妻子對(duì)我女兒說(shuō)，你看你爸都蒼老了許多?！焙桢дf(shuō)，“一個(gè)如此有意思的問(wèn)題擺在我面前沒(méi)解決，茶不思飯不想，那是正常的事兒。”

在攻破GGH密碼方案的過(guò)程中，最具有紀(jì)念意義的這一天，是2015年3月7日?！斑@天，我一晚上都沒(méi)睡覺(jué)，突然覺(jué)得GGH的結(jié)構(gòu)有些不對(duì)，半夜就起來(lái)開(kāi)始在紙上驗(yàn)算?！焙桢d奮地回憶起當(dāng)時(shí)的情景，“到了第二天早上，還是覺(jué)得不對(duì)，又躺在床上稍微休息了一會(huì)，希望等腦子清醒了繼續(xù)推算。到了中午的時(shí)候，我再一步一步進(jìn)行了認(rèn)真驗(yàn)證，第一次發(fā)現(xiàn)了GGH的漏洞確實(shí)是存在的！”

即便自己經(jīng)過(guò)多次推導(dǎo)，已經(jīng)驗(yàn)證了GGH存在漏洞，但胡予濮還是沒(méi)有輕易下結(jié)論說(shuō)攻破了這一方案。他將演算思路告訴自己的博士生賈惠文，要求他對(duì)該過(guò)程進(jìn)行反復(fù)推導(dǎo)和驗(yàn)證。最終，他們得出一致結(jié)論，攻擊過(guò)程正確無(wú)誤，一顆懸著的心終于落地了。

“有大半年的時(shí)間，胡老師和我到處碰壁、毫無(wú)成果，各種攻擊方法嘗試了有50種之多。有一次，我們甚至都將已經(jīng)寫好的文章投遞出去了，但大半夜胡老師發(fā)現(xiàn)推導(dǎo)過(guò)程有漏洞，讓我趕緊撤稿。”論文第二作者，博士生賈惠文感嘆地說(shuō)。

2015年3月15日，為了最后確認(rèn)已經(jīng)攻破了GGH密碼方案，胡予濮將描述了攻擊過(guò)程的手稿，發(fā)給了提出該方案的三位原作者。4天后，也就是3月19日凌晨5時(shí)16分，該方案的第三作者塞·哈勒維代表三人回函稱：“感謝您發(fā)送的手稿，您描述的攻擊方式，似乎的確打破了我們?cè)贕GH一文中提到的多方密鑰協(xié)商機(jī)制?！保═hankyou for sending us the manuscript. Indeed the attack that you describe thereseem to break the multi-partite key agreement form the GGH paper.）

找到了GGH的漏洞，原作者也承認(rèn)了胡予濮提出的攻擊是有效的，但密碼學(xué)領(lǐng)域的這場(chǎng)智力較量卻剛剛開(kāi)始。原來(lái)，塞·哈勒維隨即在信中指出，胡予濮提供的第一版手稿中，攻擊的第一步所采用的弱離散對(duì)數(shù)攻擊方法，是原文已有的?！盎貋?lái)找資料，發(fā)現(xiàn)人家在一個(gè)報(bào)告中確實(shí)提過(guò)。”胡予濮介紹說(shuō)，“但是在攻擊的第二步中，我們提出了一種變形的編碼/零測(cè)試工具，該工具是我們的原創(chuàng)性工作，也是攻擊的核心技術(shù)。”

2015年4月份，胡予濮及其博士生賈惠文提出組合精確覆蓋問(wèn)題的概念，對(duì)精確覆蓋這一NP完備問(wèn)題進(jìn)行弱化，同時(shí)利用改進(jìn)的編碼/零測(cè)試工具，又將基于GGH的證據(jù)加密方案攻破了。“這一方案的作者之一，密碼學(xué)家阿米特·薩海（Amit Sahai）來(lái)信提醒說(shuō)，我們只是在編碼工具公開(kāi)的情況下才攻破的，這一方案還可以在編碼工具隱藏時(shí)進(jìn)行，讓我們?cè)谡桨l(fā)表時(shí)進(jìn)行修改。一段時(shí)間以后，我們進(jìn)一步深入研究，把編碼工具隱藏的那種方案，最后也給出了有效的密碼分析，真正做到了無(wú)論在什么情況下，基于GGH的證據(jù)加密都不安全?！焙桢Щ貞浀?。

Amit Sahai

胡予濮將修改后的論文再次給原作者發(fā)過(guò)去，換來(lái)的是一片沉默。

實(shí)際上，胡予濮及其博士生的主要成果，可以總結(jié)為四個(gè)方面：一是攻破了GGH映射的安全性假設(shè)；二是攻破了基于GGH映射的非交互多方密鑰交換協(xié)議；三是攻破了基于GGH映射的第一個(gè)證據(jù)加密方案（無(wú)論編碼工具公開(kāi)還是隱藏）；四是給出GGH映射的兩個(gè)修改方案，并對(duì)它們進(jìn)行有效攻擊。

“我們的成果是對(duì)GGH的一個(gè)否定，我們打出的這套組合拳，是對(duì)GGH密碼映射方案的一次釜底抽薪似的攻擊。幾乎可以斷言，在編碼工具公開(kāi)的情況下，任何基于GGH映射的密碼應(yīng)用都是不安全的；在編碼工具隱藏的情況下，至少有一個(gè)基于GGH映射的密碼應(yīng)用是不安全的；GGH映射很難進(jìn)行簡(jiǎn)單修改來(lái)避開(kāi)我們的攻擊?！焙桢дf(shuō)。

 研究意義何在？推動(dòng)現(xiàn)代密碼學(xué)不斷向前發(fā)展

密碼學(xué)和信息安全有什么關(guān)系？密碼技術(shù)是信息安全的核心技術(shù)。

胡予濮打了一個(gè)比方說(shuō)，如果把信息安全當(dāng)作一個(gè)有大門、有圍墻的院子。要想進(jìn)院子，辦法有多種，可以翻墻進(jìn)去，也可以推倒墻進(jìn)去，還可以挖個(gè)洞爬進(jìn)去，但正常合理的辦法是把門上的鎖打開(kāi)，然后推開(kāi)門走進(jìn)去。密碼技術(shù)就是大門上的那把鎖，鎖的質(zhì)量好不好，雖然決定不了院子是否安全，但卻是合法通行的關(guān)鍵。密碼技術(shù)的不斷研究，推動(dòng)著信息安全技術(shù)的發(fā)展。

而密碼學(xué)自身又如何發(fā)展呢？胡予濮介紹說(shuō)，現(xiàn)代密碼學(xué)的發(fā)展，就是密碼編碼學(xué)和密碼分析學(xué)“相互打架”的過(guò)程，也就是設(shè)計(jì)密碼和破解密碼兩撥人的較量。設(shè)計(jì)密碼的人希望自己的密碼體制難以被對(duì)手攻破，破解密碼的人希望自己可以破解敵方的所有密碼體制。“學(xué)術(shù)研究上，破解的目的是幫助原有密碼變得更加完善，推動(dòng)現(xiàn)代密碼學(xué)向前發(fā)展?！?/span>

當(dāng)被詢問(wèn)破解GGH密碼方案實(shí)際意義何在時(shí)，胡予濮介紹說(shuō)：“GGH可以被看作是一種密碼原語(yǔ)，一旦被證明安全可行，就可以在它的基礎(chǔ)上構(gòu)造出許多新的密碼體制，極大地豐富未來(lái)密碼應(yīng)用的場(chǎng)景?！钡桢П硎荆茈y用一個(gè)大家都懂的生活中的場(chǎng)景來(lái)解釋回答這個(gè)問(wèn)題，他回憶了一段歷史：

40年前，迪菲與赫爾曼解決的兩方密鑰交換問(wèn)題，成為今天整個(gè)互聯(lián)網(wǎng)信息安全傳輸?shù)幕A(chǔ)；而GGH密碼映射要想解決的問(wèn)題，是實(shí)現(xiàn)非交互多方密鑰交換。換句話說(shuō)，如果把經(jīng)典密碼學(xué)比作“1”，那么迪菲與赫爾曼解決的就是“2”的問(wèn)題，但卻帶出了“≥3”該如何解決的難題。如果“≥3”的問(wèn)題真的徹底解決了，能用到什么場(chǎng)景中，也許我們絞盡腦汁也想不到、想不全。

胡予濮說(shuō)，現(xiàn)在的國(guó)際密碼學(xué)界其實(shí)就是一個(gè)公開(kāi)的智力角斗場(chǎng)。密碼學(xué)家都把自己最好的研究成果，發(fā)表在每年定期召開(kāi)的歐密會(huì)和美密會(huì)上，但在發(fā)表之前，他們往往都會(huì)把手稿公布在國(guó)際密碼研究協(xié)會(huì)的在線論壇，供同行批評(píng)指正。

        胡予濮教授的手稿自公布以后，吸引了全世界研究多線性映射密碼學(xué)家的目光。除了上述已經(jīng)提到的三名原作者和密碼學(xué)家阿米特·薩海外，還有包括日本東京技術(shù)研究所草川恵太（Keita Xagawa）研究員、韓國(guó)首爾大學(xué)池東杓（Dong-Pyo Chi）教授，以及一些國(guó)內(nèi)學(xué)者的關(guān)注。攻破多線性映射其他兩個(gè)構(gòu)造方案的研究團(tuán)隊(duì)，也對(duì)胡予濮的工作給予了肯定，說(shuō)胡予濮做了他們想做而沒(méi)做成的事情。

        在談到接下來(lái)的工作時(shí)，胡予濮指出，雖然他們?cè)谄平釭GH密碼方案的過(guò)程中已經(jīng)做了不少工作，但一切才剛剛開(kāi)始，下一步他們還將對(duì)基于GGH映射的不可區(qū)分混淆進(jìn)行分析?！拔疫€想給年輕人做個(gè)榜樣，更想為提高西電密碼學(xué)的學(xué)術(shù)地位貢獻(xiàn)一份力量。西安電子科技大學(xué)的密碼學(xué)在國(guó)內(nèi)享有盛譽(yù)，是中國(guó)密碼學(xué)的發(fā)源地，有‘一肖二王’這樣的老專家、老前輩，我希望大家把這塊金字招牌擦得更亮！”

為胡予濮教授點(diǎn)贊！為西電點(diǎn)贊！↓↓