在量子計算機到來之前，請準備好抗量子破解的密碼學_風聞

撰文 | Jeremy Hsu

翻譯 | 無邪（量子計算領域研究人員）

如果量子計算在未來取得突破性進展，一直守護着互聯網的安全系統將變得岌岌可危。世界從此會變成怎樣？第一個研發出實用量子計算機的政府或機構將會得到整個世界的秘密嗎？事情並沒有想象中那麼糟糕。事實上，即便有了量子計算機，許多經典的保密算法仍將是有效的，更何況量子保密技術也在蓬勃發展。不過，由於密碼系統更迭需要很長的時間，所以儘管看上去為時尚早，美國國家標準與技術局（NIST）卻已經從學術界和工業界徵集研究人員，希望在2022年之前準備好抗量子破解的密碼學（quantum-resistant cryptography）。

當實用的量子計算機最終來臨的時候，它將能夠破解一直在為我們的在線隱私、政府安全、公司安全以及幾乎所有互聯網使用者的個人安全保駕護航的標準數字密碼。這就是為什麼美國政府機關開始鼓勵研究人員去開發新一代抗量子破解的密碼學算法。

雖然許多專家並不認為量子計算機能夠在未來十年內具備破解現代標準密碼術所需要的複雜計算能力，但是，美國國家標準與技術局（NIST）希望走在前面，讓新的密碼標準在2022年之前準備好。這一機構正在審查其“後量子密碼學標準化程序”的第二階段，以縮小抗量子破解並能夠替代現代密碼學的最佳候選加密算法的範圍。

“當前，那些保護廣泛採用的加密系統，如RAS和基於橢圓曲線的密碼方案等的難解計算問題有可能變得可解。這意味着量子計算機有可能最終會夠破壞這個星球上最安全的通信系統，”英特爾公司的密碼學專家 Rafael Misoczki説道，他同時也是參與上述NIST計劃的兩個小組（分別叫Bike和Classic McEliece）的成員之一。

Misoczki參加了8月22日至25日在加州大學聖巴巴拉分校舉行的第二次PQC（後量子密碼學）標準化會議，該會議有超過250人註冊參加，幾乎所有致力於26種候選算法研究的團隊都做了報告。這些算法則是從第一輪的69個算法中篩選出來的。

NIST希望這些第二輪候選算法能夠跨越單純的原理驗證的階段，並開始進入基準測試。如果量子計算方面的突破性進展能夠威脅到數千億美元的電子商務——這還不包括數萬億美元更為廣泛的數字經濟領域，那麼這麼做就是非常值得的。不過，很多研究者警告，NIST在確定最終的後量子密碼學算法清單之前，應該花一些時間去評估新的候選算法類型。

Misoczki解釋説，NIST的計劃主要考慮兩大類的算法，第一類包括密鑰建立算法，這類算法可以確保從未碰面的通信雙方能夠對共享的保密信息達成一致。這一類同時也包含公鑰加密算法——比如RSA和橢圓曲線加密術，它們可以做同樣的事情，但不是那麼有效。

第二類包含數字簽名算法，用於確保數據的真實可靠性。這種數字簽名在代碼簽署等應用中非常重要，如此一來就可以確信一個程序是由預期的開發者開發的，而不是一個黑客。

這兩大類都要求新的算法是基於即便量子計算機也無法解決的數學問題的。目前有幾種正在考慮中的後量子密碼學算法發展途徑，每種都各有優缺點。舉例來説，“基於編碼的密碼（code-based cryptography）偏愛長的公開審核歷史，而基於網格的密碼（lattice-based cryptography）可以提供非常快速的算法，”Misoczki説道。

這是一個計算問題的集合關係圖。量子計算機能夠解決一部分 NP 問題，但仍然無法解決 NP-完全（NP-complete）問題，這給了後量子密碼學足夠的機會。

每種方法的折中處理會對現實世界中的計算機應用和設備產生顯著影響。基於網格的密碼學甚至比現代加密技術如RSA更快，但它的數據量更大，因此如果帶寬有限的情況下它的應用就會變得不一樣。

位於瑞士IBM蘇黎世研究室的密碼學專家Vadim Lyubashevsky也參與了NIST的標準化計劃。他説，這就是為什麼NIST要從幾個不同的途徑來做算法標準化。“即便我們可以保證它們都是安全的，也不可能有哪種算法在所有場景都是最佳的。”

荷蘭Radboud大學的計算機安全專家Peter Schwabe説，對這些很可能部分取代全球通信安全基礎架構的候選算法，我們仍知之甚少。每種算法在面臨各種可能攻擊下的真實安全性仍有待更多的研究和測試，此外還需要權衡其安全-性能比，發展可靠的算法實施技術，並找出那些一旦算法實施之後會發生故障的事情。

Schwabe 還説：“我們現在看起來很清楚的是，與我們今天採用的方案相比，這些新的方案在性能特徵上有極大的不同，並且很多在安全性上有細微差別。”

合作精神 vs.競爭機制

NIST的挑戰已經將學術界專注於理論研究的學者和工業界熟悉現實世界性能需求和安全要求的技術專家聚集在一起。這個機構最開始將計劃描述成“競賽型過程”，不過看起來他們更希望鼓勵參與者們互相合作。

一些研究者加入了多個研究不同算法的小組，比如，Lyubashevsky 是致力於CRYSTAL-KYBER、CRYSTALS-DILITHIUM和Falcon等多種算法研究的小組成員。Schwabe 則同屬於七個研究各不相同的算法的小組：CRYSTALS-KYBER、CRYSTALS-DILITHIUM、Classic McEliece、NewHope、SPHINCS+、NTRU以及MQDSS。

各團隊在一個統一的郵件列表中開放共享框架和反饋——這是一個既有優點又有弊端的辦法。一位匿名的參與者在NIST的調查問卷中回應道：“某些聲音和時不時的直接人身攻擊充斥着郵件列表，導致其他人不願意對這些人的工作或問題提供幫助。”

Misoczki 則説，大部分社區成員看起來還是很樂於一起工作的。他看到了“更多的合作氛圍而不是競爭環境”，儘管有些不同的觀點。

Schwabe 也描述了社區的合作精神，但提到某些個人似乎有更強的競爭傾向。他在一封郵件中寫道：“很不幸，有些參與者並不是那麼願意合作，他們致力於推動他們自己的（通常是申請了專利的）方案，而不是像社區那樣為找到可標準化並應用於未來的最佳方案而奮鬥。”

某些競爭算法其實是從同一個加密方法派生出來的，差別並不大。Lyubashevsky 建議NIST保持參與者專注於共性標準化目標，對候選算法提出想要的加密特性指標。他説：“最好跟大家説‘看，忘掉與這些事有關的人名，這是我們想要的指標’。”

圖片來源：Natasha Hanacek/NIST

新的後量子密碼學標準

NIST計劃於2022年左右起草後量子密碼學標準。但學者們已經敦促其避免急迫處理對所有候選算法的審查。他們的匿名反饋來自於一份NIST調查問卷，這份問卷在八月份第二次PQC標準化會議結束時被公開出來。

一位調查對象寫道：“NIST不應該將結束計劃並於2022年前完成標準作為目標。這有點太急於得到正確的答案了… …我們還需要更多的研究。”

另一位調查對象提出，NIST應該在2025年之前延遲推出任何標準，並在此之前資助所有候選算法的研究工作，以“給研究者創新的機會。”

一位調查對象描述了一幅急於推進的可能後果的悲觀景象：“試圖在短短几年內就終止計劃是危險的，這將導致災難性的後果，甚或喪失這一計劃及其成果的合法性。”

很多人指出，對每種算法可能的弱點進行徹底研究需要更多的密碼分析。有人敦促NIST更多地資助美國大學進行學術研究，以進一步發展“量子密碼分析學”。

Lyubashevsky 説：“密碼學的一個共性問題是，密碼分析是一個毫無回報的過程。不管你失敗了，沒人知道你嘗試過並失敗了，或是你成功了，並且贏得了五分鐘的名聲，總歸你寫的算法再沒人去用。”

NIST可能部分考慮過不同小組會試圖相互破解對方算法的想法。但是Lyubashevsky 建議NIST也應該要求研究者們檢查其他團隊的工作，或者將密碼分析作為算法開發理論研究獲得資助的條件之一。

計算機什麼時候可以破解密碼？

沒人知道什麼時候量子計算會使得現代密碼學算法變得沒用。一個附帶的後果可能是，第一個研發出實用量子計算機的政府或機構只要“靜悄悄”地破解現代密碼系統並爬取全球的秘密，就可以獲得極大的增益。

“很大的可能性是，第一個大型通用量子計算機只能是那些不會明確聲張他們有如此計算能力的政府機關所擁有，”Schwabe説。他認為“在20年之內，可以破解我們當今廣泛使用的密碼的量子計算機很有可能產生。”

密碼學研究者們確知的是，要讓全世界的政府和工業界採用最新的密碼學標準需要很長的時間。舉例來説，儘管橢圓曲線密碼在上世紀80年代末就首次提出，但全球大部分地方仍在使用上世紀70年代末出現的更老的RAS密碼。這就是為什麼哪怕實用量子計算機仍然有幾十年之遙，NIST 已經開始在後量子密碼學標準化方面作出努力背後的緊迫性所在。

Misoczki説：“預測大規模量子計算機會在什麼時候出現是一個很難的問題，而另一方面，加密社區的人知道，加密算法的過渡需要幾年甚至幾十年。”

所幸的是，那些擁有極度敏感數據的機構不需要等待NIST的標準化過程實施，相反，他們可以提前採用NIST計劃中的部分已公開發表的免費候選算法來保護他們的系統與時俱進。

Lyubashevsky説：“如果你真的有敏感數據，那別遲疑，現在就遷移。如果沒有，那麼我覺得再等五年為好，讓這些算法在競爭中自生自滅，最終產生一個大多數人喜聞樂見的好標準。”

對那些願意等待的人，Lyubashevsky表示他有信心NIST聚攏的密碼學家們會在量子計算機出現之前做好準備。他説：“在量子計算機出現之前，我們必定已經有了後量子密碼學。我想如果我們在接下來五年裏真的準備好了後量子密碼學，那麼幾乎所有的應用都將有充分的時間做準備。”

本文翻譯自 spectrum.ieee.org，原文標題為“How the United States Is Developing Post-Quantum Cryptography”，點擊“閲讀原文”可查閲原文。

返樸購書優惠+抽獎贈書

雙十一將近，返樸讀者可享噹噹圖書購書優惠“滿200減30”，優惠碼：QH4FQW(截止至11月1日），歡迎大家進入返樸書單選購。書單中的書籍均為返樸推薦過的書籍，具體介紹可見公眾號下方菜單欄“精品專欄-更多專欄-展卷專欄目錄”。

今日繼續抽獎贈書活動：自本文發佈之時起至次日早晨8點，抽獎系統將隨機抽取一名參與者，贈送返樸書單上的任意一本書，贈書由獲獎者自行挑選。我要參加抽獎贈書活動

特 別 提 示

1. 進入『返樸』微信公眾號底部菜單“精品專欄“，可查閲不同主題系列科普文章。

2. 『返樸』開通了按月檢索文章功能。關注公眾號，回覆四位數組成的年份+月份，如“1903”，可獲取2019年3月的文章索引，以此類推。

版權説明：歡迎個人轉發，任何形式的媒體或機構未經授權，不得轉載和摘編。轉載授權請在「返樸」微信公眾號內聯繫後台。