演算法領域取得突破性進展,加密技術或遲早要完

類別: 新奇

# 感謝 Grey Yang 投遞譯稿:

演算法領域取得突破性進展,加密技術或遲早要完

芝加哥大學數學系著名教授László Babai宣佈發明了一種全新的演算法,該演算法可顯著地簡化電腦科學領域某些眾所周知的困難問題。 這一突破性的進展使得很多演算法領域的專家們開始懷疑一直以來他們信以為真的理論也許並不靠譜。同時,該發現也提醒我們,或許可以取得類似突破,使得攻破資料加密演算法變得更加容易

László Babai教授將於該校舉辦三場系列講座,詳細解釋他所發明的新演算法如何解決著名的圖的同構問題(Graph Isomorphism problem)。本週二和週四(11月10日/12日)的兩場講座均人滿為患。圖的同構問題是指由計算機判斷給定的兩個圖——每個圖由一些“點”(vertex)和“邊”(edge) 構成——是否具有完全相同的結構。

Babai 教授的講座非常令人鼓舞。過去三十餘年來,圖的同構問題都被認為很可能是最難以使用計算機解決的問題之一。若Babi教授的演算法正確無誤,則這一看似頗具挑戰性的問題事實上更可能屬於一類易於解決的演算法問題,也即存在複雜度至多為多項式時間(complexity class P)演算法的問題。

“這一突破使得大家浮想聯翩,”佐治亞理工學院(Georgia Institute of Technology)從事計算理論研究的Richard Lipton教授表示,“他把這個問題的難度降低了數個級別”. 麻省理工(MIT)的副教授Scott Aaronson在瞭解Babai教授的發現後,在他的部落格上表示這可能是“計算理論領域近十年來最重要的突破”

在計算機領域,要衡量一個問題的困難程度,科學家們通常考慮隨著問題規模的上升,所需要多少的計算能力的增加速度。根據這一標準,圖的同構問題被歸類為極其困難的問題,因為隨著輸入圖的尺度增加,解決該問題所需要的計算能力幾乎呈指數型增長。

該演算法由Babai教授和俄勒岡大學(University of Oregon)的Eugene Luks於1983年初次發表。Babai教授稱,當輸入的圖的尺度增加時,他的新演算法需要的額外計算能力並不會急速增加。該演算法的存在使得圖同構的問題的困難程度被顯著降低。

Babai教授表示在其研究成果經過同行評審並正式發表之前,不願接受採訪。但他對一名參加他講座的激動聽眾說,其論文的預覽版將會“很快”發表。

Lipton教授則表示,在完整的論文面世之前,我們應當謹慎對待任何聲稱的突破性成果。但是憑藉Babai教授在業內的崇高聲望,大家紛紛表示他所取得的成果很有可能是真實可靠的。“他老人家可是業內的泰山北斗”,Lipton教授說。

若Babai教授的成果最終被確認有效,這一發現目前也只會在計算理論的專家圈子內掀起一些波瀾。圖的同構問題在某些領域內具有一定的應用價值。例如在資料庫內檢索特定的分子結構,因為分子結構可以簡單地通過圖來表示。 不過該問題已經存在類似的替代解決方案。

Babai教授還宣稱,在因式分解問題上也取得了類似的突破。因式分解被認為和圖的同構問題具有相同的困難程度,但該問題的潛在影響力比圖的同構問題更加深遠。 因式分解也即將一個數分解為其所有質因子。這一問題是最為常用的加密技術的基石,而該加密技術則被廣泛的用於資料和因特網上的通訊加密。

即便使用當前已知的最佳演算法,因式分解問題仍然和圖的同構問題一樣具有很高難度。同時由於因式分解具有某些圖的同構問題所不具備的數學性質,Babai教授的演算法目前無法用來解決因式分解問題。不過,Lipton教授認為,這一發現的意義在於提醒人們某些長期以來被奉為真理的理論或許會被某些新的演算法推下神壇。

“如果能夠找到解決因式分解的快速演算法,即使只是理論上有效,這也足夠讓密碼學專家們如坐鍼氈了”, Lipton教授說。當前的加密技術能夠被暴力破解,但是如果加密演算法使用的祕鑰足夠長,暴力破解需要使用海量的計算資源。若這方面的演算法有所突破,政府機構等或能夠切實地利用現有的超級計算機來對當前使用的加密演算法進行暴力解密。

即便理論上有效的快速因式分解演算法尚不能投入實踐,這也足夠督促科學家們進行進一步的探索和嘗試去破解這一問題,Lipton教授補充道,“密碼學專家們恐怕不能再信誓旦旦的公開表示‘我的加密演算法是安全的,因為該演算法用到了因式分解’。”

[投稿 via MIT Technology Review]

演算法領域取得突破性進展,加密技術或遲早要完原文請看這裡