在上一篇文章中，我們了解到量子電腦攻擊是如何發生的，在這篇文章中，我們將討論後量子密碼學標準。本文源自 BTQ 所著文章 《Blockchain security in the quantum era》，由 動區編輯部 整理。
（前情提要：BTQ研究》後量子時代的區塊鏈資安(上)：量子攻擊將發生？密碼學面臨的困境 ）
（背景補充：淺析量子密碼學與加密技術：更強大的安全系統 ）
後量子密碼學的標準化
美國國家標準技術研究院（NIST）是一個隸屬於美國商務部（United States Department of Commerce）的機構，該機構制定了保護敏感數據和關鍵資料的標準。任何為美國國防部（DoD）、聯邦總務署（GSA）、美國國家航空暨太空總署（NASA）以及其他政府機構處理、儲存或傳輸敏感訊息的人都必須遵守 NIST 的標準，因此大家普遍認同 NIST 為全世界制定密碼學標準的機構。
從 2016 年起，NIST 宣布開始一系列的後量子密碼學（Post-quantum crypography）競賽，過程中徵求、評估並標準化抗量子攻擊的公鑰加密演算法和數位簽章演算法，確保即使在量子電腦出現之後，這些演算法仍然可以保護敏感資訊。等待了近六年後，在 2022 年 7 月，NIST 正式宣布了這個後量子密碼學競賽第三輪的演算法標準。以下我們會把重點放在後量子數位簽章演算法。
後量子數位簽章演算法
可以實現後量子安全數位簽章的密碼演算法可以分為以下幾類：
- 格密碼學（Lattice-based cryptography），適用於公鑰加密（PKE）和簽章
- 多變量密碼學（Multivariate cryptography），適用於簽章
- 雜湊密碼學（Hash-based cryptography），適用於簽章
在這三者之中，格密碼學因其彈性和歸約安全性（Reductionist security），在近年來受到了許多關注。密碼系統的安全性通常是基於「某些數學問題是困難的」這個假設上，以及一個「如果攻擊者可以破解該密碼系統，那麼我們可以把這種攻擊轉變為一種解決底層難題的有效演算法」的歸約性證明（reductionist proof）。另外，許多格密碼系統都依賴於所謂的「可歸約最壞情況到平均情況」的難題。這大致的意思是，這個難題在「高維度中的一般實例」和在「低維度中最難的實例」的困難度是一樣的。因此，我們可以對這些格密碼系統的安全性有更高的信心，因為我們有更強的證據證明某個難題在平均情況下確實是困難的。
雜湊簽章的實現方法是將安全性假設最小化。雜湊函數在現代密碼學中是不可或缺的，沒有它，區塊鏈就不可能實現。就算假設我們只有一個安全的雜湊函數，那麼我們仍然可以構建一個數位簽章，大致過程是這樣：首先，我們使用一次性雜湊簽章，例如 Lamport’s signature 或 Winternitz signature，作為實際簽名和驗證訊息的基礎。這些一次性雜湊簽章的公鑰和私鑰最多只可以用來簽名和驗證一次，所以我們還需要一種有效的方法將許多這樣的密鑰對捆綁在一起，以實現安全和實用的數位簽章。這裡我們使用 Merkle tree 的概念來組合一次性公鑰，並使用 Merkle root 作為我們的公鑰。每次我們使用一次性密鑰對簽名時，除了發送簽章本身，我們還需要將驗證路徑（authentication path），也就是從 Merkle root （樹根）到此密鑰對（葉子）的路徑一併發送出去，以便驗證者可以確認該簽名確實來自於正確的公鑰。當然，我們也需要紀錄哪些私鑰已經被使用，例如 XMSS in RFC8391 就是一種已被標準化的有狀態雜湊簽章（stateful hash-based signature）。
還有一種多變量密碼學，其安全性主要基於解決多變量多項式方程式（multivariate polynomial equations）的困難性，以及其他例如判定兩個多項式是否同構（isomorphic）的 IP 問題。在用於數位簽章時，多變量密碼系統的簽章大小相對較小，但公鑰相對較大，這使得它應用範圍較小，比較適合系統中只有少數公鑰這樣的場景。在區塊鏈中，因為大多數公鑰只使用一次，所以並不適合這樣的簽章方式。然而，NIST 似乎仍然對多變量密碼學非常感興趣，因此也把它納入在後量子密碼學標準的名單中。
接下來，我們一一討論 NIST 選擇進行標準化的三種數位簽章。
- Dilithium：這是一種基於格密碼學的數位簽章方案，其安全性基於在模格（modular lattices）中找到短向量的難度。它使用均勻抽樣來在格中抽樣短向量，相比基於高斯抽樣的傳統方法更容易且更快。因此，Dilithium 在公鑰和簽章大小之間有一個還不錯的平衡。
- Falcon：這是另一種基於格密碼學的數位簽章方案，其安全性基於在 NTRU 格上的短整數解（short integer solution，SIS）問題的困難度。這樣的假設使 Falcon 在公鑰和簽章的大小總和，相較於其他格密碼系統（如 Dilithium）有著更大的優勢。這也是我們認為它是最適合應用於後量子區塊鏈的數位簽章的原因。
- SPHINCS+：這是一種基於雜湊密碼學的無狀態數位簽章方案。它與一樣基於雜湊的有狀態數位簽章（如 XMSS）的主要區別在於，SPHINCS+ 使用了大量的非一次性密鑰對，並將它們組織成一棵「樹的樹」，而非一棵樹。更具體地說，母樹的葉子並不直接簽署任何訊息；它們只簽署子樹的根，這與證書權威機構簽署公鑰的概念非常相似。最後，雖然這種情況很少發生，但非一次性密鑰對也解決了在母樹底部意外選擇相同私鑰的問題。即使簽名者碰巧選擇了母樹的同一葉子，它也將簽署與子樹相同的 Merkle root。
後量子密碼學應用於區塊鏈的困境
為了使區塊鏈在下一個世代仍保持安全和可行，我們必須設法過渡到後量子安全標準，不過，這並非想像中容易，因為相較現行密碼學標準，後量子數位簽章演算法的公鑰和簽章大小都增加了許多。在 NIST 認證的數位簽章演算法中，即使是最小的 Falcon 公鑰（897 B）也比現行的 ECDSA （32 B）大了 28 倍以上。如果比特幣和以太坊今天採用後量子密碼學安全標準，兩條鏈的大小都將會爆炸。即使用最節省空間的 NIST 後量子數位簽章演算法，公鑰和數位簽章在比特幣和以太坊中將分別多消耗 21.2 倍和 24.3 倍的空間，它們各自的帳本的大小將增加 2.2 倍和 2.22 倍，遑論使用其他的後量子數位簽章演算法。這不僅影響交易速度、gas 費用 ，也可能影響整個網路的去中心化。升級區塊鏈安全並不只是替換演算法那麼簡單，我們必須設計一種方案讓安全性與效率達成平衡。
後量子區塊鏈
目前有許多團隊正在研究中長期的解決方案，要將現今的區塊鏈轉換為使用後量子密碼學的區塊鏈。像是 Algorand 就使用 NIST 認證的 Falcon 簽章在他們的狀態證明中，使 Algorand 鏈能夠與其他鏈進行相互作用，也防止未來量子電腦夠成熟時可能可以回溯並產生新分叉鏈的問題。以太坊研究團隊的成員們也開發了一種多簽章方案，將多個獨立的簽章壓縮成一個短簽章，從而同時驗證所有簽章。當有多個驗證者需要對進行區塊同步的情況下，這種技術尤其有用。另外，BTQ 也已經完成 Falcon 簽章替換以太坊 ECDSA 的測試鏈，並加入了概念類似於前述以太坊的 PQScale 聚合簽章技術（aggregate signature），已達到效率和安全的平衡。
總結
量子電腦對現今的密碼系統帶來了威脅，而為了保護數位資產和區塊鏈系統，我們極需找到新的密碼演算法和數位簽章演算法。區塊鏈系統的創新和發展需要與密碼技術的發展並行，以確保未來在量子電腦真正問世並普及時，我們所使用的區塊鏈與所擁有的資產仍然能維持安全。
