HHRI/抵抗量子電腦攻擊新解:後量子密碼學的發展與挑戰

【鴻海研究院】
214 人閱讀

突飛猛進的量子運算技術,對現行的加密通訊帶來新威脅,其所具備的高速運算能力將會降低破解加密訊息的時間與成本。因此,人們開始尋找更安全的加密方式,其一是運用量子特性而發展出的量子加密通訊;另外則是能在傳統電腦設備上進行加密與解密以抵抗量子電腦攻擊的後量子密碼(Post Quantum Cryptography)系統。

圖片來源:pixabay

新創公司BTQ首席密碼學家鄭振牟博士,在鴻海研究院與台大量子科學及工程研究中心合辦「NExT Forum:量子通信技術與應用」論壇上,簡要介紹了密碼學原理,以及何謂後量子密碼與該領域的發展現況。

BTQ是由一群經驗豐富的後量子密碼學家構成,希望能解決量子電腦對區塊鏈造成威脅的急迫問題。透過與頂尖學術機構與大學的合作,整合軟、硬體並利用獨特的後量子技術和解決方案保障加密資產的安全。

古典密碼學與量子電腦帶來的衝擊

現行許多密碼系統所採用的數學架構皆會對應到「離散對數問題」(Discrete Logarithm Problem),也就是給定數學上一個循環群中的元素,及其x次方所對應的元素,想要得到未知整數次方x。對傳統電腦而言,隨著循環群逐漸增大,所需要的計算時間將成指數增長,這個問題將會變得非常困難。目前許多被廣泛應用的密碼學系統,如:Diffie-Hellman 金鑰交換、RSA加密演算法,都是這個數學問題的實際應用。

圖一:離散對數問題簡介:根據指數的性質,通訊兩方可藉由公開交換h1以及h2得到一個共享的金鑰s

儘管基於離散對數問題的密碼學系統迅速得到了廣泛的使用及信任,電腦科學家Peter Shor卻在1994年提出了一個關於離散對數問題的演算法,這個演算法將讓量子電腦能有效的解決離散對數問題,並對所有基於離散對數問題的密碼學系統的安全性造成衝擊。

密碼學的新方向:量子金鑰分發

儘管量子電腦對現有的密碼系統造成威脅,但是,量子資訊學家也運用量子力學的原理,設計出一種不依賴計算問題的困難度而達到安全性的密碼系統,更被稱作具「資訊理論安全性」(Information-theoretic security)的系統。以BB84金鑰交換協定為例,儘管量子力學的測不準原理,能保證其不可竊聽性,但因為長距離傳輸量子系統必須透過受信任的量子中繼器,因此,這種密碼系統如果要實際部署仍有極大挑戰。除此之外,我們也尚未能設計出基於量子金鑰分發的數位簽章系統。

圖二:BB84金鑰交換協定說明:通訊兩方(Alice和Bob)透過製備及隨機測量不同基底下的光子以及公開比對所用基底,可得到一組不被竊聽的金鑰。

後量子密碼學的優勢

考量到古典密碼及量子金鑰分發的問題,密碼學家們正積極設計一種密碼系統,稱作後量子密碼(Post Quantum Cryptography)。這種密碼系統可以在傳統的電腦設備上進行加密與解密,但同時又能抵抗量子電腦的攻擊。截至目前為止,已有許多基於不同技術的後量子密碼系統被提出,如基於雜湊函數的數位簽章、基於錯誤校正碼的加密方法、基於多變數多項式的加密方法、基於晶格數學問題的加密方法,以及基於數學同源性的加密方法,以下將分別介紹「基於雜湊函數的數位簽章」、「基於晶格數學問題的加密方法」兩種方法。

基於雜湊函數的數位簽章

這種演算法早在70年代便已經被提出,但因為其安全性所仰賴的假設非常簡單,也就是如果安全的雜湊函數不存在,那麼整個密碼學領域將會受到難以想象的打擊。因此在後量子密碼世代仍被密碼學者們抱持著相當的信心。下圖是一個單回合數位簽章演算法的說明:使用者持有一對私鑰,將其個別雜湊運算後產生公鑰,而使用者若想簽署一個訊息,只需公開其對應的私鑰,所有第三方皆可透過執行相同的雜湊函數驗證簽章的有效性。當然,每組私鑰一但公開後便不能再使用。

圖三:基於雜湊函數的數位簽章系統

基於晶格數學問題的加密方法

近年來,基於數學上的晶格問題所衍伸的加密系統也受到廣泛重視.如下圖所示,數學上的晶格定義是,在N維歐幾里得空間(由古希臘數學家歐幾里得建立的角和空間中距離之間聯繫的法則)的整數格子點集合,而給定任意一個晶格,要找到這個晶格中長度最短的向量,稱為最短向量問題。這個問題目前被廣泛認為,無論是對古典電腦或量子電腦都是相當困難的問題,根據這個數學架構,兩種相關的數學問題:Learning with Error 以及Short Integer Solution也被提出,許多後量子密碼系統則依賴上述數學問題的困難性。

圖四:數學晶格上的最短向量問題

後量子密碼競賽已經開跑

隨著量子電腦的迅速發展,資訊安全界對於後量子密碼標準的需求也日益迫切。因此,美國國家標準暨技術研究院在2016年舉辦了後量子密碼標準制定的競賽,希望藉由公開徵求及測試選出量子時代下可靠且易用的加密標準。今年七月已有四個演算法:CRYSTALS-Kyber、CRYSTALS-Dilithium、Falcon、SPHINCS+,有望突破重重難關達到標準化。

儘管目前許多後量子密碼系統的安全性已受到認可,但和古典密碼相比,許多系統仍有金鑰及數位簽章長度過長的問題,這在實際部署到資訊安全基礎設施時,可能會影響效能表現。因此,鄭振牟的團隊開發了「簽章聚合(Signature Aggregation)」的技術,名為PQScale。這個技術有望運用於基於晶格問題的數位簽章系統,也因為使用了零知識證明(Zero-knowledge proof)的技巧,讓第三方可以在不用檢驗個別簽章的情況下,驗證訊息的真實性,大幅減少所需的計算資源。(本文撰稿者:孫欣  shin-sun@oist.jp

**想了解更多量子通訊最新趨勢,別錯過鄭振牟博士的精彩分享:**

全文轉載自鴻海研究院TECH BLOG

留言評論
【鴻海研究院】

延伸閱讀