抵抗量子電腦攻擊新解：後量子密碼學的發展與挑戰
新創公司BTQ首席密碼學家鄭振牟博士，在鴻海研究院與台大量子科學及工程研究中心合辦「NExT Forum：量子通信技術與應用」論壇上，簡要介紹了密碼學原理，以及何謂後量子密碼與該領域的發展現況。
BTQ是由一群經驗豐富的後量子密碼學家構成，希望能解決量子電腦對區塊鏈造成威脅的急迫問題。透過與頂尖學術機構與大學的合作，整合軟、硬體並利用獨特的後量子技術和解決方案保障加密資產的安全。
古典密碼學與量子電腦帶來的衝擊
現行許多密碼系統所採用的數學架構皆會對應到「離散對數問題」（Discrete Logarithm Problem），也就是給定數學上一個循環群中的元素，及其x次方所對應的元素，想要得到未知整數次方x。對傳統電腦而言，隨著循環群逐漸增大，所需要的計算時間將成指數增長，這個問題將會變得非常困難。目前許多被廣泛應用的密碼學系統，如：Diffie-Hellman 金鑰交換、RSA加密演算法，都是這個數學問題的實際應用。
儘管基於離散對數問題的密碼學系統迅速得到了廣泛的使用及信任，電腦科學家Peter Shor卻在1994年提出了一個關於離散對數問題的演算法，這個演算法將讓量子電腦能有效的解決離散對數問題，並對所有基於離散對數問題的密碼學系統的安全性造成衝擊。
密碼學的新方向：量子金鑰分發
儘管量子電腦對現有的密碼系統造成威脅，但是，量子資訊學家也運用量子力學的原理，設計出一種不依賴計算問題的困難度而達到安全性的密碼系統，更被稱作具「資訊理論安全性」(Information-theoretic security)的系統。以BB84金鑰交換協定為例，儘管量子力學的測不準原理，能保證其不可竊聽性，但因為長距離傳輸量子系統必須透過受信任的量子中繼器，因此，這種密碼系統如果要實際部署仍有極大挑戰。除此之外，我們也尚未能設計出基於量子金鑰分發的數位簽章系統。
後量子密碼學的優勢
考量到古典密碼及量子金鑰分發的問題，密碼學家們正積極設計一種密碼系統，稱作後量子密碼（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）
**想了解更多量子通訊最新趨勢，別錯過鄭振牟博士的精彩分享：**