為何我們不能等待更好的後量子簽章演算法

我們數十年來賴以維生的密碼學演算法 RSA 與 ECC，在足夠先進的量子電腦面前都顯得脆弱不堪。儘管這類量子電腦目前尚不存在，但它們問世的速度似乎會比預期來得更快。所幸，解決方案已然問世：遷移至 ML-KEM 加密與 ML-DSA 簽章。這兩者專為抵抗量子攻擊而設計，歷經長達八年的公開國際競賽後，已於 2024 年由美國國家標準與技術研究院 (NIST) 完成標準化。

後量子密碼學的遷移工程目前正如火如荼地展開。截至本文撰寫時，Cloudflare 處理的流量已有過半採用 ML-KEM 加密，從而抵禦了「先竊取、後解密 (harvest-now-decrypt-later)」攻擊對資料構成的威脅。然而，加密僅是防護的一環：為了全面抵禦能破解傳統密碼學的量子電腦，我們的目標是部署後量子簽章，以保護驗證系統免於未經授權的存取。我們設定了 2029 年為目標，讓 Cloudflare 全面達成後量子安全。

現今已標準化、各方面表現最均衡的後量子簽章方案 ML-DSA，確實有其缺點：它在網路傳輸時的資料量龐大得多，且許多過去能搭配 RSA 與 ECC 使用的技巧，在 ML-DSA 上根本無法實現。不過，更優秀的後量子簽章方案已指日可待：上個月，NIST 宣布將九種後量子簽章方案推進至「簽章入場機制 (signatures on-ramp)」的第三輪。此外，在上一屆競賽中選出的 FN-DSA（原名 Falcon）標準草案也預計在不久後發布。

我們一直密切關注後量子簽章演算法的進展，並在 2021 年、2022 年、2024 年與 2025 年陸續撰文探討。本篇部落格將為您詳細剖析最新的發展動態。

但首先我們必須正視一個顯而易見的問題：這些新式簽章演算法根本趕不上後量子遷移的時程——而且還差得遠，後文將會詳述。問題在於，威脅來得太快，我們等不起。ML-DSA 當下即可使用，且必須擔綱首次遷移的重任。正如 Eric Rescorla 在 2024 年所寫：

您必須使用現有的演算法而非理想中的演算法去應戰。

儘管如此，尋找更優異的後量子簽章演算法仍至關重要，原因有很多，我們也堅信這依然是 NIST 有限資源的最佳運用方式。

接下來，讓我們深入探討這些簽章演算法，接著檢視它們的可用時程，以及我們為何依然需要它們。

簽章演算法

下表比較了晉級第三輪的候選簽章演算法（標示為 🤔）、易受量子攻擊的傳統演算法（標示為 ❌），以及已完成（ ✅）或即將完成（📝）標準化的後量子演算法。每個候選方案都提出了數種變體。我們列出了與 TLS（用於保護網際網路連線的通訊協定）最相關的變體。若要探索所有變體，請參考 Thom Wiggers 的 signatures zoo。

關於此表還有幾點補充說明：大多數候選演算法在每個安全層級都有多種變體。我們展示的是 TLS 在 128 位元安全層級（業界黃金標準）下最相關的變體。CPU 時間數據取自 2026 年 6 月的 signatures zoo，數據來源為第二輪提交文件及後續進展。候選者可在第三輪中進行調整，這將影響上述數據。部分演算法在運算與體積方面會有所改善，另一些則可能為了抵禦新攻擊而有所退步。請查閱 zoo 以獲取最新數據。我們為 FN-DSA 與 SQIsign 的簽署標上了 ⚠️，因為兩者都難以在兼顧高效能與防範時序側信道攻擊的前提下實作。LMS 簽署也標記了 ⚠️，因為安全的 LMS 簽署需要跨簽署操作維護狀態，且表中列出的簽署時間假設具備 32MB 快取。SLH-DSA 的 128-24 變體標有 ⚠️，因為它設計用於產生少於 224 次簽署的場景。

沒有「全能型」演算法

首先讓人一眼注意到的，是容易受到量子攻擊的橢圓曲線簽章演算法 Ed25519 至今仍是整體表現最佳的選擇（忽略其量子脆弱性）：它在幾乎每一項指標上都有最好的數據，包括公開金鑰大小、簽章大小和簽署時間。它只在驗證時間上被擊敗，但對絕大多數應用場景來說，它的速度已經足夠快。

這與後量子演算法的陣容形成了鮮明對比。我們沒有一個單一的「全能型」演算法，而是大約有兩類方案：一類是「專精型」(specialists)，在某些指標上接近我們信賴的橢圓曲線簽章，但在其他方面則有問題，這使得它們在適當的部署場景中表現出色。另一類則是「通才型」(generalists)，例如 ML-DSA，它們在所有指標上都不如橢圓曲線，但其缺點相對均衡，沒有明顯的致命傷。

專精型

讓我們先從專精型演算法開始。

SQIsign：簽章小巧/簽署緩慢

如果只看網路傳輸的位元組數，SQIsign 看來幾乎是 Elliptic Curve Cryptography 的完美替代品。它的簽章僅 148 位元組，公開金鑰 65 位元組，甚至優於 RSA-2048。可惜世上沒有白吃的午餐：SQIsign 有三個弱點。首先，它是目前候選名單中數學架構最複雜的演算法。其次，它的簽章產生與驗證速度相當慢。最後，要以防範時序側信道攻擊的方式實作簽章產生相當困難，且即便做到，也會伴隨效能損耗。

到目前為止聽起來似乎不怎麼樣，但情況曾經更糟：回顧 2024 年，當時甚至還沒有任何能防範時序側信道的實作，且簽章驗證速度慢了 20 倍。此外，在簡化此演算法架構方面已有令人欣喜的進展。

儘管有這些顯著的改進，在可預見的未來，（具備側信道防護的）簽署速度仍不太可能快到足以應付典型的線上場景，例如 TLS 交握。然而，對於離線場景，例如 CA 簽章或 DNSSEC，這類驗證時間比簽署時間更重要的應用場景，SQIsign 或許能找到用武之地。

但我們真正該討論的議題是安全性。SQIsign 基於同源 (Isogenies) 數學難題。眾所週知，同樣基於同源的另一個演算法 SIKE，在首屆 NIST 後量子密碼競賽（（該競賽最終確立了 ML-DSA 標準））後期慘遭破解。SIKE 常被視為一個警告案例，顯示後量子密碼演算法可能會突然失效。對此需要更細緻的分析：首先，當時對 SIKE 的安全性已有疑慮，特別是導致其被破解的撓點 (torsion points) 問題。正因為這些疑慮，SIKE 未被選為標準化方案，而是在被破解前被推遲到了額外的評估輪次中。（事實上，這恰恰證明了 NIST 評估流程的有效性）。SQIsign 不使用撓點，因此不存在與 SIKE 類似的疑慮。

SQIsign 另一個值得注意的安全特性是，目前已知對其最佳的攻擊就是通用的暴力破解，這與針對精心挑選的傳統橢圓曲線的攻擊如出一轍。這與 RSA、晶格 (Lattices) 和多變量 (Multivariate) 演算法截然不同——後者的攻擊演算法一直在緩慢進步，迫使參數朝著更大的簽章方向調整。儘管如此，同源背後的數學極其豐富，與其他演算法相比，其數學攻擊面相當廣闊。即便如此，其安全性似乎仍比我們稍後將討論的結構化多變量演算法來得穩固。

SQIsign 是一個潛力巨大的演算法。如果太早將它標準化，那將是一種遺憾。對於其開發者，我們想提出以下期望清單：

• 理想情況下，應進一步減少驗證時間，即便這會犧牲簽署時間與簽章大小：SQIsign 的簽章已經夠小，且離線簽署時間本來就有緩衝空間。
• 防範時序側信道的實作應成為預設選項，特別是如果簽署時間能進一步降低，這可能會誘使某些線上簽署應用採用它。
• 但最重要的是，我們希望 SQIsign 能進一步簡化。

UOV：簽章極小/公開金鑰龐大

UOV（Unbalanced Oil and Vinegar，非平衡油醋）是一種經典的多變量簽章演算法，最早於 1999 年提出。它的簽章極小：僅 96 位元組。但其代價是，公開金鑰非常龐大：66 kB。這對 TLS 伺服器憑證（其公開金鑰在建立連線時需透過網路傳輸）毫無幫助，但對於公開金鑰可預先分發的場景則有幫助。

以 WebPKI 為例。典型的瀏覽器信任約一百個根憑證和 30 筆憑證透明化記錄。若使用 UOV，這些公開金鑰總計將佔用約 8 MB 的空間。

由於根憑證是透過帶外方式傳送給用戶端，一個構想是在此處使用 UOV 簽章。但這並非十拿九穩；由於 UOV 根憑證體積龐大，若將其作為中繼憑證進行交叉簽署，在實際操作中並不可行。同時，隨著後量子簽章普遍變大，交叉簽署與中繼憑證的吸引力本來就在下降。這反而鼓勵用戶端直接內建更多根憑證。這再次對 UOV 有利，但僅止於一定程度：如果根憑證的數量成長到超過一千個，我們將面對超過 66 MB 的金鑰資料，這將佔據瀏覽器下載檔案相當大的比例（例如 Firefox 151 的下載大小約為 90 MB）。

多變量演算法的安全性

安全性方面呢？多年來，已經提出了許多 UOV 的變體，它們利用一些額外的數學結構來縮減公開金鑰大小。這些結構化多變量方案的安全性記錄並不理想，例如 Rainbow 和 GeMMS 等方案就遭到了嚴重的破解。重要的是要將這些與 UOV 本身區分開來，UOV 的安全記錄要好得多，但並非完美。

與許多密碼學方案一樣，早期也有成長的陣痛，當時發現了基本攻擊與參數設定上的陷阱。事實上，UOV 中的「U」就是那段歷史的遺跡：它代表「非平衡 (unbalanced)」，這是為了修復 1997 年油醋方案（UOV 的基礎）中的一個參數設定錯誤。原始方案在作為公開金鑰的二次方程式系統中，油變數與醋變數的數量相等，結果證明這會招致攻擊。未免您對這個生動的名稱感到好奇，在此做出解釋：方程式系統包含醋 x 醋以及油 x 醋項，但沒有油 x 油項。這就像油醋醬汁，油滴以微小分離的狀態存在。現在繼續講那段歷史：從 2005 年到 2020 年，對多變量簽章來說是一段平靜的時期：對 UOV 的理解有所增長，但沒有出現對典型參數的新攻擊。

這種情況在 2020 年發生了變化，當時發現了交集攻擊 (intersection attack)，該攻擊建立在對平衡油醋的原始攻擊想法之上。交集攻擊使當時提議的 128 位元參數集損失了大約 30 位元的安全性。這是一個相當大的打擊，但不是致命的：稍微調整參數就能完全緩解該攻擊，且金鑰和簽章大小只會微幅增加。

更大的衝擊是 2025 年發表的利用「楔子」(wedges) 來攻擊多變量方案的想法。初期對 UOV 的影響較小：同樣在 128 位元安全層級下，僅損失幾位元。當時的擔憂在於這個構想來得突然，且不清楚此方法能被發揮到什麼程度。這份憂慮某種程度上是合理的：楔子構想極具成效，後續衍生出了多種攻擊方法，使安全性進一步降低了約 15 位元。然而，同時也變得明確的是，楔子攻擊及其推廣形式可被視為現有攻擊（例如截斷環上的交集攻擊）的特例——因此比我們想像的更為熟悉。同樣地，這些攻擊可以透過僅微幅增加金鑰和簽章大小來緩解。

該如何看待這一切？這樣的攻擊歷史並不罕見：在過去 25 年間，晶格演算法的安全性也曾大幅下降，儘管近年已趨於平靜。儘管如此，今日部署於生產環境的晶格密碼學仍使用保守的參數集，遠高於 128 位元，以應對未來的密碼分析。我們也希望對 UOV 採取同樣的態度。簽章大小僅隨安全層級線性成長，即便在 256 位元安全層級下也僅需 260 位元組。不幸的是，公開金鑰大小與安全等級呈三次方關係：256 位元層級下高達 446 kB。好在 UOV（正如大多數多變量密碼方案一樣）在選擇各種中間安全等級的參數集時具有很大的靈活性。

UOV 是一個基礎性的方案，雖應用場景有限，但的確具有實際用途。展望未來，我們希望看到一個安全邊際略高於 128 位元（例如 160 位元）的參數集，以應對未來密碼分析技術的進步。

QR-UOV：簽章小巧/公開金鑰龐大

與稍後將討論的 SNOVA 和 MAYO 一樣，QR-UOV 是一種結構化多變量方案：它是 UOV 的一種變體，透過在公開金鑰中新增更多數學結構來縮減其體積。但縮減幅度相當有限：最好情況下公開金鑰為 12 kB，但該特定參數集的簽章驗證速度慢到不切實際。更具實用性的參數集則從 24 kB 的公開金鑰起步。

在安全性方面，QR-UOV 是唯一一個無須因應新攻擊而調整其原始（第一輪）參數的多變量方案。這有點令人意外，因為任何針對 UOV 的攻擊同樣適用於 QR-UOV。原因是，攻擊確實有效，但 QR-UOV 天然的參數設定恰好讓這些攻擊失效。另一方面，針對 QR-UOV 新增的特定結構，其實早已存在數種已知的攻擊：事實上，針對某些參數集，這些結構專屬的攻擊才是最有效的攻擊手段。這與 MAYO 形成對比，對於後者所新增的額外結構，目前尚無已知得逞的攻擊方法。（我們稍後會再回頭探討 MAYO 和 SNOVA。）

與上一輪相比，QR-UOV 的簽署與驗證時間已有顯著提升，但速度依然相對緩慢。總體而言，QR-UOV 的賣點不足：它在 UOV 上增加了可被利用的結構，卻未能將金鑰大小壓縮到通用型方案的水準。

基於雜湊的簽章

基於具狀態雜湊的簽章

最早完成標準化的後量子簽章演算法，是具狀態的雜湊式簽章 LMS、HSS 和 XMSS(MT)。它們擁有極小的公開金鑰，且在許多參數設定下，簽章大小遠小於 ML-DSA-44。此外，它們的安全性建構於雜湊函數之上，而雜湊函數的特性已被充分理解，且是密碼學的基石。這使得雜湊式簽章成為非常保守穩健的選擇，無須透過提高安全層級來進行風險對沖。

那麼，缺點是什麼？

主要有兩個。最大的一個是維護所謂的「狀態」。這些具狀態的基於雜湊簽章方案是由一次性簽章金鑰建構而成，這些金鑰被收集到 Merkle 樹中。簽署者必須追蹤哪些一次性簽章金鑰已經被使用過，這可以透過簡單的計數器來實現。然而，如果簽署者搞砸了，不小心在不同訊息上重複使用了同一個一次性簽章金鑰，那麼任何人都可能利用這兩個簽章來為任何訊息建立自己的簽章。要正確維護狀態，您必須牢記許多細節。考量因素包括：必須確保在發出簽章之前將狀態更新寫入儲存體；必須防止舊狀態從備份中復原；此外，在不同位置間匯出或匯入私密金鑰時，必須就如何分割或保留狀態達成協議。正如 Adam Langley 數年前指出的，「狀態」是個巨大的「踩雷陷阱 (foot-cannon)」。

另一個缺點是，最具競爭力的參數集只能產生有限數量的簽章。1,112 位元組的簽章（如上表所列）只能用於產生約一百萬個簽章。您可以使用這個計算器來探索其中的權衡取捨。

綜上所述，具狀態雜湊式簽章的適用場景非常狹窄：簽署者必須有能力維護狀態；簽章大小必須是關鍵考量；且簽署者必須能接受簽章數量的硬性上限。

SLH-DSA：保守的安全性／龐大且緩慢

SLH-DSA 是一種雜湊式簽章，它沒有簽章數量限制，也規避了維護狀態的問題。其基本構想是讓一次性簽章金鑰的數量變得極其龐大，使得您可以隨機挑選金鑰，完全不必擔心重複使用，因為重複選中同一把金鑰的機率微乎其微。SLH-DSA 的效率比這更高一些，它用「有限次簽章金鑰 (few-time-signature key)」取代了一次性簽章金鑰作為建構模組，即便金鑰偶爾被重複使用，安全性也只會發生可控的衰減。但這依然有其代價。SLH-DSA 有兩種變體，一種針對較小的簽章尺寸進行了最佳化，另一種則針對更快的簽章速度進行了最佳化。但即便是以大小最佳化的版本，簽章也高達 8 kB，絕稱不上小；而以速度最佳化的版本，簽署速度甚至比 SQIsign 還慢。

SLH-DSA 更少的簽章變體

NIST 曾提議為 SLH-DSA 標準化一個額外的參數集，其簽章體積更小，但僅能產生約一千六百萬次簽章，之後安全性便會下降。其簽章大小為 3.8 kB，仍大於 ML-DSA-44，但公開金鑰與簽章的總體積非常接近。此參數集的選擇旨在讓簽章驗證速度變快，代價是簽署時間變得非常糟糕。而事實上，簽署時間確實極差。

使用場景

那麼，為何還要使用 SLH-DSA？其賣點在於保守的安全性。對於難以替換的長期信任金鑰，如果應用場景能夠忍受標準化變體的大體積簽章與緩慢驗證，或是新提議變體的緩慢簽署速度，那麼 SLH-DSA 可能是合理的選擇。對此還有兩個額外的提醒。首先，最好在建構系統時就確保金鑰演算法沒有被寫死，以便事後能夠替換。其次，在大多數情況下，系統（例如使用 TLS 的安全連線）不僅依賴簽章，也依賴金鑰協議 (Key Agreement)。目前並沒有基於雜湊的金鑰協議機制，因此我們最終還是需要信任晶格這類相對沒那麼保守的技術。

FN-DSA：金鑰與簽章小巧/簽署過程精細微妙

從數據上來看，FN-DSA-512（前身為 Falcon）在幾乎所有指標上都比 ML-DSA-44 表現更優異：驗證速度更快、公開金鑰更小，且簽章僅 666 位元組，體積大幅縮減。雖然簽署速度慢了三倍，但仍比 RSA-2048 快上 25 倍。此外，它已被選定將成為 FIPS 206 標準。那麼，為何我們不將 FN-DSA 視為通用型演算法呢？

原因在於 FN-DSA 的簽署實作難以確保安全性。FN-DSA 最廣為人知的「棘手之處」在於，它最自然且有效率的實作方式是使用硬體加速的浮點運算，這在密碼學標準中是首例。這帶來的一大挑戰是，我們缺乏以防範側信道攻擊的方式實作高速浮點運算的經驗。目前我們所知的是，這過程極其精細且不夠穩健：針對某款處理器使用浮點運算單元 (FPU) 實作的安全簽署版本，換到另一款處理器上可能就不安全了。如果不依賴 FPU，也可以模擬浮點運算。這種方法更容易正確，但速度會慢上約 20 倍，使其淪落到與 RSA-2048 差不多的慢速。近期在利用定點運算 (fixed-point arithmetic) 安全實作 FN-DSA 簽署方面已有令人欣喜的進展，其速度遠快於浮點模擬。既然如此，直接採用定點運算方案，FN-DSA 不就可以投入使用了嗎？這種想法可能過於樂觀，因為這預設了某種未必存在的認知層次。根據我們在研討會上的觀察，每當看到講者在基準測試中比較包含 FN-DSA 在內的後量子簽章演算法時，他們往往無法回答是否使用了浮點模擬。

使用浮點運算的另一個後果是，難以制定簽署的測試向量 (test vectors)。舉例來說，a+(b+c) 與 (a+b)+c 的結果只保證「接近」，而非「完全相同」。這意味著，若要擁有實用的測試向量，FN-DSA 規範就必須對浮點運算的順序規定得極其精確。另一個例子是 a*b+c，這可以分兩步驟計算（先乘後加），也可以透過融合乘加 (FMA) 指令一次算完。後者速度更快，但同樣會產生略微不同的答案，因為捨入只發生一次。並非所有處理器都支援 FMA，但對於支援的處理器，編譯器通常會為了效能提升而自動使用 FMA。此外，某些數學最佳化也會造成麻煩。例如，參考實作利用帕塞瓦爾定理 (Parseval’s theorem) 以更快的迂迴方式計算某個數值（範數）。在數學上答案完全相同，但由於浮點數只是近似值，最終的數值會有極細微的差異。同樣地，安全的定點運算實作也會產生略微不同的結果。

為何這是個問題？因為在實際應用中，捕捉大多數實作錯誤的往往是那些看似不起眼的測試向量。其他更精細的方法（如形式化驗證）確實能抓出更多錯誤，但論及簡便性，測試向量仍難以被取代。

缺乏統一實現標準還會帶來另一個意想不到的隱患：從同一把私密金鑰、由略微不同的實作所產生的兩個確定性簽章 (deterministic signatures)，可以推導出該私密金鑰的部分資訊。FN-DSA 並不使用確定性簽章，而是加入隨機因子來阻擋此類攻擊。這與測試需求產生了矛盾：您需要一個確定性的介面來測試簽署功能，但又不希望這個介面被用來產生實際的簽章。

如何處理 FN-DSA 規範中的彈性空間，無疑將成為討論焦點。實作間的差異或許蘊含著一線生機：NIST 可以決定根據定點運算實作來生成測試向量 (CAVP)。如此一來，風險較高的浮點運算實作將無法通過測試向量，這反而是一個特性 (feature) 而非錯誤 (bug)，因為它能引導實作朝向更安全的定點版本邁進！

您可以在這篇部落格文章中讀到其他幾個有趣的潛在隱患。撇開細節不談，重點在於 FN-DSA 是一個複雜的方案。NIST 花了數年時間（這還不包括目前的停滯期）才寫出標準草案，這並不令人意外。最終標準的發布以及密碼學函式庫的支援，將比往常耗費更長的時間。FN-DSA 的問世時間比它看起來的要遙遠得多。我們稍後會在本文中比較各演算法的時程。

如果這些參數指標仍然很有吸引力，還有最後一點要注意：FN-DSA-512 的參數設定對應的是 128 位元安全強度，而 ML-DSA-44 則提供了高達 160 位元的安全強度。如果晶格密碼分析技術進步，它並沒有中間的安全層級可過渡：下一級直接跳到 256 位元的 FN-DSA-1024。FN-DSA-1024 的金鑰與簽章大小翻倍，簽署與驗證時間也倍增。FN-DSA-1024 的簽章大小仍只有 ML-DSA-44 的一半，但公開金鑰加簽章的總體積差異僅約 20%。

在結束 FN-DSA 的討論前，值得強調的是，FN-DSA 的所有困難都在簽署這一側：FN-DSA 簽章的驗證過程非常簡單直接。

通用型演算法

現在，我們來看看那些旨在成為 ML-DSA 通用替代方案的演算法。

HAWK

HAWK 是個有趣的案例。在許多方面，它與 FN-DSA 相似：都是結構化晶格的「雜湊後簽署 (hash-then-sign)」方案，簽章與公開金鑰大小相近，且同樣缺乏中間安全層級。HAWK 相較於 FN-DSA 的主要優勢是簽署速度非常快，且不使用浮點運算，儘管它本身也不是一個簡單的演算法。但這伴隨著權衡取捨：HAWK 基於並引入了一個新的安全性假設——晶格同構問題（Lattice Isomorphism Problem，LIP）。2024 年，在 HAWK 問世兩年後，人們發現這個問題在「全實數體 (totally real number fields)」的特殊情況下很容易被解決，雖然這類數體並未用於 HAWK 或任何其他密碼學中。2025 年，這項攻擊被擴展到更廣泛的數體類別。雖然尚未直接適用於 HAWK，但距離已越來越近。2026 年 6 月發表的一篇新論文提出了將攻擊擴展至 HAWK 的方法。雖然該論文中已發現一個錯誤，但尚不清楚該錯誤對整個攻擊方法的根本性影響有多大。儘管如此，這種發展態勢令人擔憂。

即使忽略潛在的攻擊，HAWK 也面臨一些阻力：它額外的安全假設使其無法取代 FN-DSA，但其實際優勢（特別考量到缺乏中間安全等級）不如結構化多變量候選方案。它也沒有增加安全假設的多樣性，而這正是 NIST 所期望實現的目標。

知識證明方案

FAEST、MQOM 和 SDitH 都有相似的整體結構。它們的公開金鑰是某個困難問題的實例，而私鑰則是該問題的解答。

• FAEST 的公開金鑰，是使用一把秘密金鑰對已知明文進行 AES 加密後的結果。
• MQOM 的名稱源於多變量二次問題 (Multivariate Quadratic problem)，該問題與多變量方案背後的密碼學假設密切相關（但更為保守）。公開金鑰是一個二次方程組，私密金鑰則是該方程組的一個解。
• SDitH 基於隨機線性碼的伴隨矩陣解碼問題 (Syndrome Decoding problem) 的困難性。此問題與提交給首屆 NIST 競賽的基於編碼的方案相關，但那些方案在第三輪已被淘汰。

在所有這些方案中，簽章本質上是一種零知識證明，證明簽署者知道該困難問題的解答，同時（作為一種順帶的機制）將待簽署的訊息納入證明的一部分以示確認。

許多簽章方案（尤其是 ML-DSA、SQIsign 和 Ed25519）在底層機制上其實也是這類零知識證明。那麼，為什麼我們不把它們也歸類為知識證明方案呢？

差異在於通用性 (generalizability)：用於 ML-DSA 的零知識證明，只能針對 ML-DSA 所使用的特定 LWE 問題進行證明——該證明利用了金鑰中的數學結構。確實有方法可以使用晶格建立針對任何通用陳述的零知識證明，但那些證明系統與 ML-DSA 截然不同，且會產生大約 50 kB 的龐大簽章。

相較而言，FAEST、MQOM 和 SDitH 所使用的證明系統可以用來證明任意陳述。舉例來說，FAEST 可以經過修改，改用 MQOM 的困難問題。這催生了一個更高效的方案，稱為 KuMQuat（稍後我們會提到一些效能數據）。反之，MQOM 也可以調整為使用 AES 作為其困難問題。

這種靈活性之所以棒，有兩個原因。首先，它不需要困難問題具備任何特定的數學結構，因此我們可以挑選非常保守的問題，例如破解 AES。當然，有些問題會比其他問題帶來更高效的簽章，正如我們在 MQOM 使用的 MQ 問題中所見。MQ 依然是一個相當保守的假設：它不包含 UOV 及其他多變量簽章所使用的隱藏子空間。因此，交集攻擊 (intersection) 和楔子攻擊 (wedges) 都對其無效。事實上，MQ 問題屬於 NP-hard 問題。為了確保安全，仍需挑選適當正確的問題規模；儘管 MQ 問題已被研究多年，但它顯然尚未像 AES 等已廣泛部署的演算法那樣接受過同等程度的嚴格審查。

第二個也是更大的優勢在於，利用通用的零知識證明系統，我們不僅能建立簡單的簽章方案，還能實現盲簽章甚至功能完整的匿名認證系統。

這裡需要注意一個限制：這三種方案所產生的證明大小，會隨著所證明陳述的規模線性成長。用技術術語來說，它們不像 STARKs 或 LaBRADOR 那樣具有簡潔性 (succinct)，後者在處理大型陳述時表現遠遠優於它們。這再次印證了一個道理：有時，選擇一種在漸近複雜度上並非最優的方法，反而是更好的選擇。

回到優勢：除了所選擇的困難問題和雜湊函數的安全性之外，這三個方案不需要任何進一步的安全假設。這使得 FAEST 和 SLH-DSA 一樣保守。

那麼，除了選擇的困難問題不同，它們還有什麼差異？這些方案起初大不相同，但自第一輪篩選以來，它們都在不斷改進並逐漸趨同。MQOM 中的證明系統比 FAEST 稍微簡單一些，但效能也稍差：KuMQuat (FAEST+MQ) 的表現優於 MQOM。

談到效能，讓我們先與 SLH-DSA 比較。這三種方案都有變體，其效能優於任何已標準化的 SLH-DSA 參數集，且往往優勢明顯。SLH-DSA 確實有一個獨特的優勢：其驗證常式 (verification routine) 更容易實作。

與 ML-DSA-44 相比則更有趣。所有方案都能在速度和簽章大小之間自由取捨。舉例來說，以下是針對 KuMQuat (FAEST+MQ) 的權衡數據報告。其驗證時間與簽署時間相近。

KuMQuat 可以調整參數，使簽章大小略小於 ML-DSA-44，代價是冗長的簽署（及驗證）執行時間。在另一端，它可以達到與 ML-DSA-44 相似的簽署時間，但代價是簽章更大，儘管公開金鑰加簽章的總體積仍然相近。

多年來這些方案已有顯著改進，我們預期未來還會有一些進步。儘管它們對 ML-DSA 的改進可能不如其他一些替代方案那樣驚人，但它們保守的安全性，特別是在匿名認證等更廣泛應用上的潛力，使它們非常有吸引力。為了展示底層零知識證明系統的靈活性，我們希望此類別中的每個方案都能提供數據，說明如果使用不同的底層困難問題，它們的表現會如何。

結構化多變量：MAYO 與 SNOVA 的對決

如同先前討論過的 QR-UOV，MAYO 和 SNOVA 都是 UOV 的變體，透過在公開金鑰中新增額外結構來縮減其體積。但兩者採取了截然不同的路線：SNOVA 為了追求極致效能而大膽下注，而 MAYO 則秉持保守設計，步步為營。

SNOVA 的效能確實令人驚艷。其主要參數集的簽章僅 248 位元組（比 RSA-2048 還小！），公開金鑰也只有 1 kB。在公開金鑰加簽章的總體積上，它打敗了所有其他後量子方案（SQIsign 除外），且執行時間表現優異。

MAYO 的效能同樣不容小覷。MAYOone 擁有最佳的驗證時間，其 454 位元組的簽章依然小於 FN-DSA-512、HAWK-512 和 RSA-4096。搭配其 1,420 位元組的公開金鑰，MAYOone 在總體積上略遜於 FN-DSA-512 和 HAWK-512。然而若考慮到更高的安全餘裕，MAYO 便會再次取得領先。FN-DSA 和 HAWK 缺乏中間安全層級，因此必須直接躍升至 256 位元安全層級；MAYO 具有更細緻的參數粒度，可以透過略微增加公開金鑰和簽章大小來提升安全性。

如果這還不夠好，MAYO 和 SNOVA 都允許在簽章大小與公開金鑰大小之間進行權衡。因此，對於那些公開金鑰可以預先分發的場景，我們可以獲得更小的簽章。若將此特性推向極致，MAYO 便會退化為 UOV。

截至目前，我們討論的都是效能。那安全性呢？MAYO 在 UOV 之上新增了一層「鞭打 (whipping)」結構：任何針對 UOV 的攻擊同樣適用於 MAYO，但也可能存在專門針對 MAYO 鞭打結構的攻擊。迄今為止，尚未發現任何針對鞭打結構（也就是專門針對 MAYO）的攻擊。最壞的情況是，由於 MAYO 天然的 UOV 參數選擇，一些 UOV 攻擊對某些 MAYO 變體的影響比對典型 UOV 參數集更大。

這與 SNOVA 形成鮮明對比。SNOVA 的特定結構已經多次受到重創。作為回應，SNOVA 團隊不僅調整了參數，還持續變更了實際的結構。每一次，他們都向前邁進，提出效能更好的新型 SNOVA。我們去年就注意到了這一點，而這個模式仍在持續，相較之下 MAYO 的基本設計是穩定的。

此外，SNOVA 所使用的結構可以視為 MAYO 所使用的鞭打對應的一種特殊形式。這意味著任何針對 MAYO 的特定攻擊都適用於 SNOVA，但反過來則不然。

總體而言，我們在理解多變量安全性方面已見證了長足進步。NIST 曾表示，預期在標準化任何多變量方案前會額外增加一輪評選。這看來相當審慎。對我們而言，目前尚不清楚 SNOVA 屆時是否已準備就緒，但 MAYO 至今看來發展得相當成熟。

時間表

現在，讓我們展望未來，大致梳理一下這些新式簽章演算法究竟何時能真正派上用場。

ML-DSA 迄今為止的進展

回顧 ML-DSA 的發展歷程極具參考價值。

在 NIST 選定 Dilithium 成為 ML-DSA 後，耗時一年才起草標準提案，又花了一年才發布演算法標準。但光有演算法標準還不夠：各通訊協定必須就如何整合 ML-DSA 達成共識。就憑證而言，這又花了一年的時間。這還不是終點：軟體需要加入對 ML-DSA 及其通訊協定整合的支援。

這些步驟並非純然依序進行：ML-DSA 的軟體實作工作在最終標準發布前就已展開。此外，通訊協定整合標準通常在成為最終標準前就已「完工」。例如，TLS 中使用 ML-DSA 的規範已定案，但截至本文撰寫時，相關 RFC 還需數月才會發布。值得注意的是，OpenSSL 甚至搶先一步，在 IANA 代碼點分配前就加入了 ML-DSA 支援。目前明顯欠缺的是關於 TLS 中應使用哪些混合式簽章的共識（甚至根本還沒定案），截至撰文時，相關的 IANA 代碼點尚未分配。

這些新的簽章演算法何時才能投入使用？

那麼，這對新式簽章演算法意味著什麼？如果 FN-DSA 草案今日發布，且進展速度與 ML-DSA 相同，我們或許能在 2029 年初看到一些早期的軟體支援，但不太可能出現大規模部署。鑑於 FN-DSA 標準草案的製定耗時較長，最終標準、通訊協定整合及軟體支援的推進過程很可能同樣緩慢。預計 FN-DSA 要到 2033 年後才會廣泛應用。

多變量方案在密碼分析上的進展讓 NIST 趨於謹慎：他們表示預期多變量方案至少需要再經過一輪約兩年的評選。另一方面，多變量方案實作起來相對容易。這意味著我們可能在 2031 年看到多變量的 NIST 標準，而更廣泛的產品支援則不會早於 2034 年。

相較於多變量方案，NIST 對 SQIsign 的安全性更有信心。與 FN-DSA 類似，SQIsign 也是一種難以標準化和實作的方案。同時，在簡化 SQIsign 方面已經取得了很大進展。SQIsign 很可能會在第三輪做出重大變更，因此需要第四輪的評估。無論如何，該方案在 2035 年之前廣泛普及的可能性似乎不大。

如前所述，HAWK 處於 FN-DSA 與結構化多變量候選方案之間一個尷尬的中間地帶。即使它被標準化（鑑於近期的密碼分析進展，這似乎不太可能），預計相關產品也要等到 2034 年之後才會面世。

剩下的是知識證明演算法：MQOM、SDitH 和 FAEST。我們見證了這些方案在多輪評選中的顯著改進。如果這種變化速度持續，它們將需要額外一輪評選；但如果現在已趨於穩定，知識證明演算法將有望在 2030 年成為率先問世的新 NIST 標準。即便如此早問世，其效能也未必能大幅超越 ML-DSA。儘管如此，它對於建構匿名認證及其他超越單純簽章的密碼學原語仍將備受歡迎。

那麼，您是否應該等到這些簽章演算法問世後再進行後量子遷移呢？鑒於量子硬體與軟體的最新進展，我們認為我們等不起。在 Cloudflare，我們的目標是在 2029 年完成全面遷移。上述這些簽章演算法都趕不上這個時程。大多數監管機構設定的期限介於 2030 至 2035 年之間。這些期限並未考量近期的進展，我們預期它們會被調整。2026 年 6 月美國行政命令設定 2031 年為期限就是一個例證。即便期限不變，我們也不建議等待。

為何？在 2034 年部署後量子簽章以趕上 2035 年的期限是不夠的。在任何具備相當規模的系統中，都不可能實現所有元件的一次性升級。您需要一段過渡期，同時支援後量子與傳統簽章。而同時支援兩者會有招致降級攻擊 (downgrade attack) 的風險。防止此類降級最直接的方式是停用傳統密碼學。這需要時間，且坦白說，在像 WebPKI 這樣高度分散的系統中，這甚至不是一個選項。我們將在未來的部落格文章中探討如何應對降級問題。同時，如果您好奇，可以參考這些資料。無論如何，處理降級問題將耗費時日。

顯然，這些新式後量子簽章演算法將無法趕上首次遷移的時程。那麼，為什麼還要費心呢？

為什麼我們仍然需要它們

我們花了 50 年的時間，將公開金鑰密碼學編織到我們的數位社會中。我們只剩下短短幾年時間將其全面轉換為量子安全。對於大多數升級而言，流程很明確：直接換入後量子密碼學。但說起來容易做起來難：這是項艱鉅的任務。此外，有些情況本質上更為棘手。後量子世界裡沒有「全能型」簽章，且 ML-DSA 的體積在某些場景下確實是個問題。只要有足夠的資源與利害關係人的共識，系統可以透過重新設計來適應這些較大的簽章。事實上，由於持續的重新設計，後量子 WebPKI 的效能正逐漸優於今日易受量子攻擊的版本。但期望所有系統都能在期限前完成這項工程是不切實際的。有些系統將不得不接受效能損失，另一些則需以其他方式應對安全缺口，例如限制存取、建立通道、加強監控，或採取其他代價高昂的措施。一旦更小的後量子簽章問世，這些補償性管控措施便可移除，進而恢復完整的效率與安全性。

正在進行的 NIST 競賽還帶來一個間接但同樣重要的好處：它推動了後量子密碼學超越基礎原語的發展。畢竟，不僅是金鑰協議與簽章易受量子攻擊。在實際生產環境中，也廣泛應用許多進階密碼原語，如匿名認證、PAKE（密碼驗證金鑰交換）和門檻簽章等。對於大多數原語，可用的後量子變體要麼尚不成熟，要麼研究不足。對於某些應用場景，雖可透過非進階密碼學達成相同目標，但往往伴隨著隱私保障方面令人遺憾的退步。NIST 無法針對每個特定原語舉辦競賽來制定後量子標準，但幸運的是，簽章演算法競賽在此提供了巨大幫助。

最明顯的例子就是 FAEST。雖然它被設計為簽章方案，但其底層機制 (VOLEitH) 可與 MAYO 等多變量方案結合，創造出高效的後量子匿名認證。若沒有這場簽章競賽，VOLEitH 不會發展到今日這般成熟且經過嚴格審查的地步。

許多候選方案都簡要地指出了它們在簽章之外的用途。我們希望看到這些方案更多的間接應用能獲得重視。

儘管優秀的數位簽章方案和更先進的密碼學指日可待，但我們不應忘記當務之急：在近期維持安全。