中央研究院 資訊科學研究所

列印可使用瀏覽器提供的(Ctrl+P)功能

量子世代下的密碼學:機會與挑戰

:::

現代密碼學是探討如何在抵禦壞人行為下達成保密性、真實性與各種所需功能的學科,這可被比喻為「好人」(Honest Party)與「壞人」(Adversary)的戰爭。經過超過三十年的研究,密碼學已發展為一門極其豐富且有重要實際應用的領域。從理論的角度來說,密碼學的發展已遠超越歷史上安全通訊的目標,使我們能實現許多看似矛盾不可能的密碼學任務,如零知識證明(Zero-knowledge Proofs)、安全多方計算(Secure Multi-Party Computation) 與對加密資料的計算等,並伴隨著嚴謹的安全性保證。從實務的角度來說,密碼學是保護現代網路安全的基礎。每次與Google或成千上萬個網站建立連接時,我們都會使用加密技術。沒有它,現代網絡商務將無法生存一秒鐘。

我們長期致力於密碼學的理論與實務研究。楊柏因研究員是廣泛使用的Ed25519數位簽章的共同作者。Ed25519將被美國國家標準暨技術局(NIST)納入FIPS 186-5標準中,並有數億用戶使用。 楊柏因和王柏堯研究員也是在「高安全性加密軟體」(High Assurance Crypto Software)領域的先驅研究者。在理論研究方面,鐘楷閔研究員的研究涵蓋了多項重要研究主題如零知識證明與(平行)隨機存取機((Parallel) RAM)計算模型下的密碼學等。

隨著最近量子科技與量子電腦的快速發展,了解量子對於密碼學的影響是十分重要的研究課題。(大型)量子電腦能利用秀爾演算法(Shor’s Algorithm)對現今公鑰加密系統造成災難性的影響,這也是少數目前確認的量子計算的殺手級應用之一。秀爾演算法基本上是個利用量子特性尋找週期的演算法,能有效率的破解RSA與橢圓曲線密碼學(Elliptic Curve Cryptography; ECC)。 儘管量子電腦的出現速度比預期的要慢,但NIST的一份報告曾謹慎的預估量子電腦最早可能將於2030年破解橢圓曲線密碼學。

鑑於轉換現行密碼架構的困難性,這是當今亟待解決的問題。其嚴重性體現在轉換現行密碼架構所需的成本與時間。前者可以從當年解決Y2K問題的成本推估,後者我們則應注意到業界已經花了二十年但仍未完全轉換到AES。後量子密碼學(Post-quantum Cryptography; PQC)是一個快速發展的領域,它通過開發可抵禦量子攻擊的安全密碼系統(通常是公鑰密碼系統)來應對這一挑戰。

我們也可以將量子視為一把雙刃劍。 儘管可能無法在可見的未來實用化,但量子也增強了好人的能力,使其達成更強安全性或更多的任務。近年來量子密碼學對於當好人取得量子能力時的可能性有豐富且令人興奮的發展。

後量子密碼學

密碼學是量子電腦造成最早也最可見實體影響的學科:美國國家標準局 (NIST)在 2015 年就開始討論新一代的,可抗量子的公鑰密碼系統,在 2016 年他們公開向全世界徵求後量子密碼系統,這個甄選過程在 2017 年截止收件。在這四年間,幾乎所有實作派的密碼學家都參與後量子密碼系統的設計,實作和破密。

NIST 的標準化過程進行到第二階段,在 82 個投稿的系統中有 69 個「完整而正確」,它們成為第一階段的候選者,並被邀請參加 2018 年四月的第一次候選者大會。而幾乎是 NIST 才剛公布全部的名單,後量子密碼學家就已經在分析和攻破這些系統。大概有 50 個沒被攻破的系統中 NIST 挑出 26 個 (其中17個加解密系統和 9 個數位簽章)晉級第二階段,並邀請它們參加 2019 年八月的第二次候選者大會。第三階段預計將在2020六月開始。晉級這一階段的最後決選者中將預計在 2022 年選出勝利者,並在再 1-3 年後標準化。這個過程和 AES 與 SHA-3 的競賽是類似的。

楊柏因研究員在這十幾年來一直研究後量子密碼學,並成為國際知名的專家 (他是後量子密碼學國際研討會指導委員會的成員)同時他的實驗室也是在台灣唯一參加2017年NIST甄選投稿的團隊。

楊研究員是所謂多變量密碼系統的專家。這種密碼系統的安全性是繫於解多變量非線性方程組的複雜度。他的團隊完成了很多多變量密碼系統的理論和實務面的探討,而幾乎所有現存的多變量密碼系統的設計都有他經手的部份。
他的團隊在 NIST 的甄選中投了兩個系統,其中之一 (Rainbow簽章系統)晉級第二階段且很可能進入第三階段。

同時,楊團隊也研究其他的後量子密碼系統的設計,實作和攻擊。他們曾在幾個公開的晶格密碼系統分析的競賽中名列前茅。在其他的密碼系統中也可以看到他的影響。他最近的一個研究是如何高速且定常時間的計算最高公因式 (數) 和模乘法反元素,這在 NTRU 及相關的密碼系統的金鑰生成上非常重要。

量子為壞人帶來的能力其實不僅限於量子計算,還有如處理量子信息,利用量子糾纏,與進行量子疊加的操作等,這些能力在不同的密碼學領域,如在Leakage-resilient Cryptography與Tampering-resilient Cryptography領域,以及在分析使用隨機預言機(Random Oracle)的構造的安全性時,可能為壞人帶來優勢。 從理論的角度,了解這些優勢對安全性的影響,以及如何證明安全性是重要的研究課題。這樣的理論研究也會對實務上決定後量子密碼系統的安全參數產生影響。在此研究方向我們的研究集中在探討具有量子信息壞人,發展對此證明安全性的技術。我們也探討量子隨機預言模型下的安全性。

量子密碼學

相對於後量子密碼學探討古典密碼系統如何抵禦量子壞人,量子密碼學廣泛地探討當好人也具備量子能力時能實現的密碼學任務。如量子密鑰分發(Quantum Key Distribution; QKD)可以實現具資訊理論安全性(Information-theoretic Security)的安全通訊(Secure Communication),這在古典密碼學(好人不具備量子能力時)可被證明是不可能實現的。又例如當未來資料也變成量子資料時,我們如何對量子資料進行加密,能否像對古典資料一樣,對加密後的量子資料進行運算,也是量子密碼學探討的重要問題。儘管這樣的研究可能在可見的將來無法實用化,量子密碼學是令人興奮的跨領域的學科,需要結合密碼學、量子物理、複雜度理論(Complexity Theory)與資訊理論(Information Theory)等領域的最近技術來研究。量子密碼學也提供了豐富的情境與研究課題,往往能協助發展新的技術與深入的觀察,反過來推動這些領域的研究。

鐘楷閔研究員是理論學家,從事(後)量子密碼學的理論研究近十年。他曾在各主要國際密碼學會議,如CRYPTO,Eurocrypt,Asiacrypt,QCrypt與TCC擔任議程委員會(Program Committee)委員。 除上述關於後量子密碼學的理論課題外,他也研究了量子密碼學中的多個課題,如設備無關密碼學(Device-independent Cryptography)、安全多方量子計算(Secure Multipart Quantum Computation)與古典委託量子計算(Classical Delegation of Quantum Computation)等,並利用量子密碼學中的技術來回答量子複雜度理論中的猜想。底下重點介紹其中兩項研究工作。

第一項是關於設備無關密碼學,其目的是設計協定(Protocol)讓古典的好人能安全地利用不可信任的量子設備。我們的研究工作提出了一個基於最少假設的設備無關亂數增強(Device-independent Randomness Amplification; DI-RA)協定。具體來說,我們的協定能只利用一個具足夠亂度(Sufficient Min-entropy)的弱亂數源(Weak Random Source),在不需要其他結構上的假設下可驗證的產生純隨機數(Truly Random Bits)。其他已知協定均需要使用具一定結構的Santha-Vazirani 亂數源與特定的條件獨立性假設。此研究結果在基礎物理學上也有應用:我們的協定可被解讀為一個關於物理世界具隨機性或確定性的二分定理(Dichotomy Theorem):只要物理世界不是確定性的,就可驗證的存在完全隨機無法預測的事件,因此排除了「弱隨機世界」的可能。

我們近期的研究工作發展並利用量子密碼學的技術來研究「低量子深度的經典量子混合計算模型」的計算能力,並回答Scott Aaronson與Richard Jozsa過去提出的猜想。在可見的未來量子電腦的能力可能會被侷限在低深度的量子計算,因此此類混合計算模型可以說是短期內利用量子電腦所能取得的計算能力。Jozsa於2006年提出一個猜想,認為所有多項式時間(Polynomial-time)的量子計算都可以在一種基於所謂Measurement-based Computation所定義的混合計算模型下被模擬。但另一方面,Aaronson持不同立場,猜想BQP與另一種自然的混合計算模型之間應該存在所謂的Oracle Separation。我們利用量子密碼學的技術證明了BQP與這兩種混合計算模型之間的Oracle Separation,證明了Aaronson的猜想,也表示Jozsa的猜想相對於Oracle並不成立。