DAOrayaki DAO研究獎金池：
資助地址: DAOrayaki.eth
投票進展：投票3/0通過
研究種類：Post-Quantum, Digital Signatures, Hash
創作者：Eric Zhang, VegeBun
翻譯者：heyyawn@DAOrayaki.org
審核者：DAOctor, Yofu@DAOrayaki.org
原文：How do hash-based post-quantum digital signatures work? (Part 1)
基於哈希的數字簽名方案是後量子數字簽名的一個類別。與目前用於驗證區塊鏈交易的數字簽名方案不同，哈希函數為量子計算機提供的可利用結構要少得多，而且廣泛認為它是量子安全的。
目前區塊鏈基礎設施上廣泛使用的數字簽名，如BLS 和ECDSA，都是基於離散對數問題。
對於那些不熟悉數字簽名的人來說，一個簽名方案由四部分組成：系統生成（SysGen），密鑰生成（KeyGen），簽名生成（Sign），以及簽名驗證（Verify）。
例如，在ECDSA 中，公鑰Pk 是通過橢圓曲線群上的生成點G 來生成的，私鑰Sk 滿足Pk＝Sk * G。給定Pk ，利用經典算法很難找到Sk。
BLS 簽名方案是在配對群
上構建的。公鑰/密鑰對滿足
量子算法善於尋找某些函數的周期性，它能發現經典難題的特殊結構，如因式分解和離散對數。當擁有數千個邏輯量子位的量子計算機出現時，BLS、ECDSA 和其他依靠因式分解和離散對數問題的簽名方案將不再安全。
例如，求一個數N=p*q的素因子可以簡化為
求一個函數的周期。其中c 是N 的互素數。一旦找到週期，那麼可以通過計算、
和
找到兩個互素因子。使用著名的輾轉相除法可以很快找到最大公除數，它可以在經典的計算機上運行。反之，在經典計算機上很難找到D(x) 的周期，但QPU 可以在多項式時間內完成。
儘管當今的量子計算機只有幾百個噪聲的物理量子位，但量子計算機的建造者確實擁有大量的路線圖來實現大規模的量子計算機。像IBM 和Rigetti Computing 這樣的超導量子計算機製造商正在向1000 個物理量子位的量子計算機邁進，並使用可疊加的模塊以獲得更多數量的邏輯量子位。除此之外，在可預見的未來，還有其他幾種方法可以帶來有意義的量子計算系統，包括離子阱、中性原子和基於測量的量子計算。
但是，到目前為止，還沒有發現有效的量子算法來破解哈希函數，而量子計算機只是將生日攻擊速度提高到
而在經典計算機上的生日攻擊速度為
現在讓我們來看看如何使用哈希函數來構建數字簽名，以及如何處理基於哈希的量子安全簽名。
一次性簽名方案
首個基於哈希的簽名是於1979 年首次推出的Lamport 簽名。一個Lamport 簽名密鑰只能安全地簽署一條信息，因此這是一個一次性簽名方案（OTS）。該簽名方案的工作原理如下：
對於每條信息，簽名者需要準備兩組密鑰對。
PKs 是通過哈希SKs 計算的。假設我們使用256 位的加密哈希函數來產生消息摘要，每組密鑰對由256 個密鑰和公鑰組成。總的來說，我們需要準備512 個密鑰和512 個公鑰來簽署任何一條消息。
要對一個消息簽名，首先將消息散列成一個256 位的隨機數；然後，根據散列數的位值，相應地選擇SK。
請注意，我們將始終對消息h(m) 的摘要進行簽名（其中h 是加密哈希函數），而不是對任意長度的消息進行簽名。為了簡化標記，我們在本文的剩餘部分將使用m 代替h(m) 。當你看到m，即表示著h(m)。
圖片註釋：簽名是 和消息本身。
為了驗證簽名，首先計算H(m)，然後根據簽名計算,驗證PK 是否確實是來自SKs 散列的結果，並且驗證索引是否正確。
在對任何消息進行簽名之後，該過程都會公開一半的密鑰。因此密鑰對只能使用一次，否則攻擊者將能夠使用公開的密鑰來驗證消息。
使用Merkle Trees管理OTS 密鑰
從21 世紀加密用戶的視角來看，Lamport 簽名方案乍一看可能很奇怪、很混亂。寫下一次私鑰或助記詞可能就已經給人帶來壓力和煩惱，如果私鑰只能簽署一份信息，而每份消息都要共享不同的公鑰，這不讓人抓狂嗎？
事實證明，如果我們能夠適當地引入管理密鑰的機制和工具，OTS（稍後介紹）簽名方案也不是那麼糟糕。
因為Lamport OTS 和Winternitz OTS 一次只能簽署一條消息，如果需要簽署多條消息，就必須有多個密鑰。 Merkle Tree的簽名方案（通常稱為“MSS”）是由Ralph Merkle 發明的，用於管理Lamport OTS 密鑰。
其基本原理是使用Merkle Tree 的葉子來存儲Lamport OTS 密鑰。因為Merkle Tree 是二叉樹，高度為h 的Merkle Tree 有的葉子。如果使用葉子來管理Lamport OTS 密鑰的摘要，那麼Merkle Tree 可以管理的Lamport OTS 密鑰對。
當簽署消息時，需要從樹上摘取一個之前從未使用過的Lamport 密鑰對。簽名由葉子的索引、Lamport 公鑰、Lamport 公鑰摘要（葉子）和該葉子的認證路徑組成。
圖片註釋：在這個簡單的Merkle Tree 中，由
簽名的消息是
，其中
，
是
的一半。
如果有很多消息需要簽名，可以重複上述過程。由於Lamport 密鑰對是一次性密鑰對，因此任何葉子都不能被選擇超過一次。因此，MSS 是一個有狀態的簽名方案。
你可能還注意到，如果驗證者只得到一個Lamport 簽名，那麼Lamport 簽名方案本身並不能防止中間人攻擊。
為了在沒有Merkle Tree 的情況下驗證簽名者的Lamport 公鑰是否真實，驗證者需要保留一份密鑰副本。因為所有單獨的密鑰對都只能一次性使用，因此驗證者需要保留一份所有公鑰的副本。使用Merkle Tree 可以有效地讓驗證者只保存Merkle 根（Merkle root），而不需要保存
密鑰對，從而將空間從
減少到O(1)。這意味著，安全地交換一個Merkle根就允許多個簽名驗證。
使用Merkle Tree 的結果是，每次簽名都必須包括認證路徑，這是一個更大空間，而且驗證者要對O(h) 計算更多的哈希值來驗證每個簽名。
Winternitz OTS
Lamport OTS 的另一個問題是，Lamport 公鑰和Lamport 簽名太長。 Robert Winternitz 提供了一個改進的簽名方案（現在將其稱為WOTS），大大減少了簽名的大小。
Winternitz OTS 不是為每一條消息準備私鑰和公鑰對，而是將哈希的消息分成幾塊。如果一個信息被分成N 個塊，並且每個塊有1 個比特，那麼我們就得到了lenth (m) = N * L。我們將在本文中使用相同的$l,N& 符號，以便於閱讀。
假設我們仍然在信息上使用256 位哈希函數，並獲得信息的256 位摘要。在這種情況下，N * L = 256（例如，N =64，l = 4，或N = 8，L = 32，等等）
使用上面的例子，m 被分割成64 個塊，每個塊有4 位。所以，WOTS 只需要準備64 個私有密鑰sk0， …， sk64。公鑰是通過對每個私鑰上應用次哈希函數來計算的。
一個WOTS 簽名的生成方法如下。
1、計算消息摘要中每個塊的十進制值。例如，第一塊的十進制值是5。
2、通過將相應的私鑰哈希運算計算：
第i 個區塊的簽名。在上面的示例中，sk0 將被哈希運算次
3、對N 個塊應用（1）和（2）並生成簽名
圖片註釋：每個公鑰是通過對相應的私鑰哈希運算
次來獲得的。
為了驗證簽名，驗證者將首先對信息進行哈希運算，得到一個256 位的摘要m。然後驗證者將m 分成幾塊，得到每組的十進制值。
然後驗證者將簽名的每個值哈希運算
次，得到
。如果
與公鑰集pk 相同，則簽名有效，否則簽名被拒絕。
WOTS 的折衷方案是在簽名生成和驗證中增加了更多的計算量。因此，WOTS 的簽名將明顯比Lamport 的簽名小得多（根據Merkle 的說法，約為4 至8 倍）。
值得注意的是，WOTS 仍然是一個一次性的簽名方案，因為一旦使用了密鑰對，只要塊的十進制值小於原始值，攻擊者就可以為每個塊生成有效消息。因此，多次使用WOTS 根本不安全。
WOTS+
WOTS+ 為WOTS 增加了隨機性。它首先向公鑰集
添加了一個額外的公鑰
。新的
是一組
的隨機數
c 是WOTS+ 使用的一個哈希函數，它取代了WOTS 中使用的h。 c 接受兩個輸入，並遞歸定義為：
其中x 是私鑰，H 是一個哈希函數。
圖片註釋：WOTS+ 公鑰的計算方式與WOTS 相同，只是將h 替換為c，並添加pkN
WOTS+簽名的生成方式與WOTS 類似，只是做了一些修改。它首先將一個消息m分成N塊
然後計算一個校驗和
，連接校驗和，生成b = m || c。
計算出簽名：
將簽名與隨機數公式一起發送給驗證者。
圖片註釋：簽名是根據
一組中間的方塊（哈希值）。
一個簽名可以通過對收到的元素進行持續的哈希運算來驗證，直到整個o集中的每個元素都經過pk 驗證。
具體來說，就是計算
如果
元素匹配pk，則該簽名有效，否則拒絕簽名。
儘管WOTS 和WOTS 的一些變體使用簡單的哈希鏈，但它們的迭代方法也很常見和簡單。然而，WOTS+有一些特殊的迭代模式，可以實現嚴密的安全性證明，而不需要使用的哈希函數族具有抗衝突性。
擴展的Merkle Tree簽名方案
因為WOTS+ 仍然是一個一次性簽名方案，如果有多條消息需要簽名，那麼密鑰管理就非常重要。
擴展的Merkle Tree 簽名方案（通常稱為XMSS）使用Merkle Tree 來管理WOTS+ 密鑰，其方式類似於MSS 使用Merkle Tree 來管理Lamport 密鑰。
我們已經知道MSS 是如何使用Lamport 密鑰對的，所以讓我們先看看頂層的Merkle Tree。
圖片註釋：用顏色標記驗證最終XMSS 公鑰的認證路徑
在XMSS 中，公鑰是XMSS Merkle 根。 Merkle Tree 的每個葉子都是WOTS+ 公鑰集的Merkle根。為了說明這一點，從上面“擴展”
我們將有一棵“子”Merkle Tree 連接到上面的葉
上。這棵樹在文獻中也稱為“L-tree”。
圖片註釋：一個由L-tree 管理的WOTS+ 密鑰集。實際樹高取決於WOTS+ 密鑰集的大小。
位掩碼用於L-tree。在每次將哈希函數應用於兩個節點之前，兩個底部值將使用相應的位掩碼進行異或運算。 L-tree 的每一層都有兩個位掩碼值
它們將該層的左、右節點進行異或運算。因此，一棵高度為h 的L-tree 總共需要2h 的位掩碼。
圖片註釋：L-trees 是如何計算的——在進入哈希函數之前，將一個值與一個位掩碼進行異或運算。
現在沿著L-tree 向下移動—— L-tree 的葉子是WOTS+ 公鑰。每片葉子代表一個WOTS+ 公鑰，該公鑰是使用WOTS+ 中描述的私鑰的哈希值鏈創建。
圖片註釋：L-trees 是如何計算的——在進入哈希函數之前，將一個值與一個位掩碼進行異或。
要對消息m 簽名，首先從XMSS 樹中選擇一個由i 索引的葉子，並確保該葉子以前從未被使用過。然後我們知道該葉子是WOTS+ 公鑰集的一個Merkle 根。 WOTS+ 私鑰可以用來對消息進行簽名，並得到消息m 的WOTS+ 簽名
。 XMSS 簽名
，其中i 是WOTS+ 密鑰對的索引，
是這個WOTS+ 公鑰集的Merkle 根。
要驗證該簽名，首先使用m 驗證
和使用i 索引的WOTS + 公鑰，然後使用
和XMSS 公鑰驗證
的正確性。
使用XMSS，可以管理和驗證多個WOTS+ 密鑰。
拓展閱讀
本文介紹的簽名方案是基於哈希的簽名方案的基本構建塊。 Andreas Hülsing 等人在該論文中對基於哈希的簽名方案的算法特性進行了更深入的分析。
還有其他以前NIST 推薦的簽名方案（如Leighton-Micali 簽名）和多樹方差（如分層簽名系統（HSS）和多樹XMSS（XMSS-MT））。 NIST最近的第三輪後量子密碼學標準化過程目前不推薦這些簽名方案以及本文第一部分所介紹的簽名方案。然而，了解這些簽名方案的細節非常重要，因為更新的、通常更複雜的簽名方案是根據這些算法思想設計的。
本文的第二部分將介紹基於哈希的簽名方案的最新發展，包括SPHINCS/SPHINCS+，以及工程和開源軟件的現狀。
