後量子密碼學標準化競賽

為了迎接後量子密碼學時代的來臨,美國國家標準與技術局(NIST)自 2016 年起舉辦「後量子密碼學標準化競賽」,吸引了來自全世界的團隊參賽一較高下,在這場競賽取得最終優勝者,將成為新一代的標準化密碼系統。最近,中研院資訊科學研究所楊柏因研究員的團隊以名為「Rainbow」的密碼學系統,通過了第一、二輪的考驗,於 2020 年成為進入決選的七組決勝者之一,距離成為世界標準,只剩一步之遙……

中研院資訊所楊柏因研究員所屬的團隊以名為「Rainbow」的密碼學系統,參與美國國家標準與技術局(NIST)自 2016 年起舉辦「後量子密碼學標準化競賽」,於 2020 年成為進入決賽的七個最終候選者 (Finalist) 之一。
圖│研之有物

不論是網路購物,還是網路銀行的交易,我們在網路上的一舉一動,都依賴著嚴密的加密系統,保護我們的隱私不讓駭客從中盜取,守護我們的資訊安全。然而隨著量子電腦的發展,現行的加密系統卻面臨被破解的威脅。(有關目前的加密系統,請見研之有物另一好文〈量子電腦到底有多霸氣?即將引爆終極密碼戰?!〉)

因為當前加密系統的根基,都是一道複雜的數學難題,而主流的公鑰加解密系統,包括 RSA 加密演算法、橢圓曲線密碼系統,背後的數學難題複雜得讓古典電腦一籌莫展,卻正好是量子電腦最擅長解決的問題型態。

這些數學難題的答案,皆可轉化成週期性的結構。理論上,只要找到答案的週期,量子電腦就可以「較為輕鬆」的破解問題。

怎麼做?量子電腦的每個量子位元的數值是以機率呈現,意即每個位元會有一個最高機率的數值,代表這個位元最可能的數。研究者可針對以上答案具有周期性構造的數學函數,構造出相應的量子組態,使量子位元最高機率數值之間的差距,恰恰就是原本函數週期的整數倍 (例如:函數的週期是 4,量出來的差距可能是 4、8、12……。)接著,研究員只要測量這些差距,就能反推出函數的週期,破解古典密碼學加密系統所仰賴的數學難題!

全球密碼武林大會

幸好,加密系統不只一兩種,這就好像武俠小說中總會有武當派、峨嵋派等,各種派別都有自己的獨門招式,加密系統也根據數學難題結構分成好幾派,除了當紅的 RSA 加密演算法、橢圓曲線密碼系統外,還有晶格、偵錯修正碼、多變量二次函數、雜湊函數及超奇異橢圓曲線同源等等。

為了因應量子電腦即將引爆的終極密碼戰,美國國家標準與技術局(NIST)自 2016 年起舉辦「後量子密碼學標準化競賽」,就如同一場武林大會,要找出能夠抵禦量子電腦的武林盟主,做為後量子密碼學時代的新標準。不過最後的標準至少要有兩個,分別用在數位簽章和加解密,所以與賽者也就很自然分成兩組。

美國國家標準暨技術研究院(National Institute of Standards and Technology,簡稱NIST),負責推動美國的度量衡學、標準、技術,例如後量子密碼標準化。因為美國官方標準通常也會通行世界,本次密碼學競賽結果預測將決定未來全球密碼學標準。
圖│美國國家標準暨技術研究院官方網站

武林大會的英雄帖一出,自然吸引了全世界的密碼學高手前來較勁,而中研院資訊所研究員楊柏因也是其一──他組了一個團隊,以 Rainbow 演算法參賽。在多變量二次函數這個派別,楊柏因也算是長老了,這一派的獨門絕技,就是多變量二次函數這個數學難題,也是楊柏因長期投入的主題。他和團隊也殺進了這場武林盛會中,而 Rainbow 這個難題的核心,是要解一個多變量方程組,其中包括 100 個變數,64 個二次方程組。

多變量二次函數問題的答案,沒有週期性結構,不是量子電腦擅長的難題,因此在後量子密碼學時代也能擁有很好的安全性。

演算法大亂鬥

武林大會的第一場比武是個大亂鬥── 69 組參賽者提出的演算法,必須接受彼此的攻擊,如果被破解,代表安全性不夠,在這個階段就會被淘汰。楊柏因形容:「過程很像練蠱,最強的才能從甕裡爬出來。」2017 年 12 月 21 號公布這 69 組演算法後,雖然緊接著美國的聖誕節,但才短短幾天,就有不少演算法被破解,「大概阿宅是不過節的。」楊柏因笑稱。在一番廝殺後,Rainbow 順利通過考驗,成為進入第二階段的 26 個參賽者之一。

第二場比武要看的則是演算法的性能。一個派別的武功如果到了深山或森林等特殊環境就難以施展的話,那便無法成為武林盟主。同理,NIST 要求晉級的團隊將自家演算法在一般電腦、計算能力較弱的微處理機、硬體晶片上,都要能順利運作,而且效果不能太差。楊柏因解釋:「我們在這階段要做的是,在能保證 Rainbow 安全性的情況下,找出讓它跑得最快的參數。」

事實上,通常密碼系統的複雜度都是可大可小的,所以一個跑得比較快的演算法,相當於可以修改成跑得跟其他演算法一樣快、但更安全的演算法。

在現在的密碼學上,速度基本上可以等同於安全性,效能愈高相當於實用上安全性愈好。

第二階段的比武仍舊沒有難倒 Rainbow,一路過關斬將,Rainbow 成了七個有資格站上決選擂台的候選者之一。此外,在中研院資訊科技創新研究中心,周彤助理研究員所屬團隊提出的 Classic McEliece 也和 Rainbow 一樣是 Finalist。在七組 Finalist 中,中研院就佔了兩組,整體表現可說是相當不錯呢。

 

欲瀏覽完整精采文章,請至研之有物官網:

https://research.sinica.edu.tw/postquantum-cryptography-yang-bo-yin/

(趕快點進來喔!還有更多精采圖文!)