作者：Blocksteam Team
來源：https://blog.blockstream.com/schnorr-but-with-vectors-lattice-based-signatures-explained/
提醒。本文為我們的深度研究文章和課程的配套性介紹。想知道全面的技術解釋，請閱讀我們的研究報告、觀看我們的課程。
由於論述量子計算的 Google 量子 AI 論文出版，圍繞關於 有密碼學意義的量子計算機（CRQC）的問世時間的討論也日益集中。雖然對問世時間的預測多種多樣，密碼學社區中的共識是清楚的：我們現在就要開始準備和調查量子安全的密碼學算法。
首要任務是選擇一種量子安全的電子簽名方案，以取代我們今日在比特幣上使用的量子脆弱的橢圓曲線密碼學。但是，想要超越 Schnorr 和 ECDSA，並不只是切換成另一種算法那麼簡單。比特幣社區當前關注的是兩個主要的問題：如何 安全地執行遷移；以及，我們要遷移到 哪一種 後量子（PQ）方案。本文只關注後面這個問題，希望找出最有前景的一種後量子簽名家族。
以下是我們對當前的後量子領域的觀察。這些觀察也回答了為什麼 Blockstream 集中研究 “基於格的（lattice-based）” 密碼學，以及這些簽名方案是怎麼工作的。
後量子時代
關於後量子簽名，密碼學家們通常關注四種（據說）量子計算機難以打破的困難性假設。
1. 基於哈希函數的密碼學。這類方案的安全性依賴於無法逆推哈希函數的假設。在我們今日使用的所有密碼學原語中，這些假設被認為是最穩定的。
此外，帶狀態的方案（例如 SHRINCS）實現了非常緊湊的簽名，只有 324 字節；但這種緊湊型的代價是細緻的狀態管理。相反，避免這種狀態管理負擔的結果是一種最終簽名提及相對較大的無狀態簽名。不論是哪一種，它們都受困於代數不靈活性：也就是說，開發例如高效的多簽名和門限簽名這樣的變種，目前看起來是不可能的。
Blockstream 已經形成了一份對此種密碼學的集中研究，見《為比特幣研究基於哈希函數的簽名方案 》（作者是 Mikhail Kudinov 和 Jonas Nick）以及 《SHRIMPS 》（作者是 Jonas Nick）。現在，我門轉向考慮基於格的方法，它能解決前面提到的一些問題。
2. 基於格的密碼學。此類方案的安全性與叫做 “格（lattice）” 的數學對象的特定問題有關。這類對象從 18 世紀開始就得到了數學家的研究。你可以把一個 格 想象成一個由無數點構成的點陣，就像下圖所示。正如你把橢圓曲線上的兩個點 “相加” 就能產生（同一橢圓曲線上的）第三個點，你也可以把這個點陣上的兩個點相加，得出同一格上的另一個有效點。
那麼，你可以提出一些關於這個格的問題，比如說：在這個點陣上，最短的兩點間距離是多少？或者，如果你在平面上隨機選出一個點，那麼離這個點最近的格點是哪一個？對於恰當設定的格，量子計算機 —— 在不知道這個格的幾何學底層細節時 —— 被認為難以回答所有這些問題。
相比基於哈希函數的方案和體積更小的無狀態簽名， 格的主要特性就是代數靈活性（algebraic flexibility）。 我們會在下一個章節中更具體解釋這一點。
3. 基於編碼的密碼學。“糾錯碼（error-correcting codes，ECC）” 是這個領域的另一種被廣泛使用的數學工具。比如說，你可能已經聽過它，因為它在後量子證明系統比如 ZK-STARKs 中有自己的所有。不過，當前的基於 ECC 假設的簽名方案都是不實用的（相比基於哈希函數的和基於格的競爭對手），因為最終的公鑰和簽名的體積太大。一般來說，這些對象的體積會輕鬆超過 10 KB；NIST 候選方案 LESS 就是這種情況。
4. 基於同源的密碼學。這類密碼學可以產生比前述候選方案都要更小的公鑰和簽名。比如說，SQISign 的公鑰和簽名總計大小為 213 字節（做個對比，Schnorr 簽名方案是 96 字節），令人印象深刻。只是，其背後的數學依賴於非常新的代數幾何學（algebraic geometry）概念。在密碼學裡面，複雜性常常是安全性的敵人，因為這些繁瑣的集合結構可能遮掩了微小的漏洞。在我們集合集成這類方案到比特幣之前，這些方案還需要大量時間來做壓力測試。
如你所見，上述四種範式都有自身的取捨：簽名體積、安全性穩健性，以及靈活性，可以綜合成下圖
總結一下，（現在的）基於編碼的簽名，對於比特幣的嚴格的區塊空間約束來說太龐大了。基於同源的數學是緊湊的，但是非常難以安全地實現，而且依然有諸多爭議。基於哈希函數的簽名是非常安全的，也得到了充分的理解，但它們在代數上是 “死板的”。
從比特幣的久遠未來著眼，基於格的密碼學成為了可以說最均衡、最有前景的的候選之一。
為什麼要格簽名？代數靈活性
為了理解為什麼格密碼學對比特幣有吸引力，我們需要看看讓現在的比特幣簽名方案（Schnorr 和 ECDSA）非常高效的因素。
當前，比特幣上的簽名方案的安全性依賴於 “離散對數（Discrete Logarithm，DL）”難題。DL 方法的一個重要好處在於，它有一個非常好的數學結構。比如說，你要結合兩個私鑰，它們的公鑰的結合也是可以預測的：
[x + y].G = [x].G + [y].G這種幾何上的 同態 屬性，正是比特幣開發者們得以開發出多簽名（比如 MuSig2，來自 onas Nick、Tim Ruffing 和 Yannick Seurin）、門限簽名、層級式確定性派生以及 “適配器簽名” 這些高級協議的原因。
哈希函數（比如 SHA256 和 BLAKE）則正好相反， 它們就像隨機攪拌器一樣。如果你有一個哈希函數 H，把兩個輸入加在一起，不會得出它們的哈希函數輸出之間的任何關係：H(x+y) 不會等於 H(x)+H(y)。雖然缺少這種結構正是讓哈希函數具備安全性的原因，它也使得我們極難在上面開發高級協議。
不過，格，還給了我們這樣的數學結構。格密碼學不是在某條橢圓曲線上用標量去乘以某個點，而是將數字的網格（矩陣）與一列數字（向量）相乘。如果你有一個公開的矩陣 A 和兩個秘密值 x 和 y，那麼 A(x+y) = Ax + Ay（就像離散對數背景下的 (x+y)G=xG+yG 一樣）。
這裡有一個重要的提醒：在格密碼中，我們通常使用 短 的秘密值。在我們結合格等式時（比如，計算 x+y），“聚合後的”秘密值的長度會增加。但只要我們妥善控制這些誤差的大小，上述結構化特性就依然成立。這意味著，格有望實現高級的協議改進，比如後量子多簽名、零知識證據以及機密資產。
格簽名如何工作：帶有向量的 Schnorr
只要你能理解比特幣上的 Schnorr 簽名，你就 50% 理解了一部分格簽名，比如 Dilithium 。這種最主流的格簽名設計使用了一種技術，我們戲稱為 “帶有向量的 Schnorr 方案”。
在傳統的 Schnorr 簽名中，使用私鑰 x 的簽名流程是這樣的：
- 選出一個隨機數
r - 為該數字創建一個 “承諾”
- 哈希這個承諾和待簽名數據，得出一個隨機挑戰值
e - 使用這個挑戰值來遮掩你的私鑰，產生最終的響應值
z = r + xe
在基於格的簽名方案中，我們運行一摸一樣的步驟，只是使用矩陣和向量。等式看起來是相似的：比如說，許多對格簽名的早期研究都使用等式 z = r + Se，其中 S 是一個秘密矩陣，e 是挑戰向量，而 r 是一個隨機向量。
拒絕採樣*
這裡有一個很大的安全性問題。為了讓格等式對量子計算機來說難以求解，向量 z 和 r 中的數字都必須較小（這就是所謂的 “短整數解 ” 難題）。
但是，在我們計算 z = r + Se 時，它在簽名 z 和背後的秘密值 S 之間創造了一種統計依賴性（a statistical dependence）（在 Schnorr 簽名上不是這樣，因為 r 和 e 可以是任意的）。如果一個攻擊者能夠收集到足夠多你的簽名，TA 將注意到其中的統計學偏移，從而也許能揭曉你的私鑰。
為了解決這個問題，格密碼學使用了一種聰明的技巧，叫做 “帶拋棄的 Fiat-Shamir 變換”（也叫 “拒絕採樣（rejection sampling）”。
這個想法非常簡單：在簽名人生成簽名 z 之後，他們先檢查加上私鑰後是否使這個值發生重大偏移。如果這個簽名看起來 “有偏倚（biased）”、有可能洩露私鑰（如上圖所示），他們就丟棄這個簽名、用一個新的隨機數再次嘗試（生成簽名）。這個過程會重複多次，直到最終的簽名能夠完美遮掩這個私鑰（如上圖的虛線所示）。
提醒。在實踐中，中間的 Se 自身就是一種隨機分佈。不過，在原理上沒有什麼區別：分佈的偏移會洩露關於背後的秘密值 S 的一些信息，所以我們必須消除偏移（這也是因為，可以證明很簡單就能做到這一點）。
下一步
基於格的密碼學是深奧話題，也是後量子密碼學中的有前景的方向，遠遠不止是替代當前的數字簽名方案。它提供了數學基礎，讓我們可以確保比特幣的量子安全性，同時有望升級到更為高效的聚合方案和門限方案。
想要更深入的解釋，包括 “離散高斯函數” 背後的數學、最短向量問題、拒絕採樣，請閱讀我們的研究報告完整版，並觀看完整的視頻演示。
（完）
