作者：David Wong
來源：https://cryptologie.net/posts/hash-based-signatures-part-iv-xmss-and-sphincs/
原文出版於 2015 年 12 月。
本文是本系列關於基於哈希函數的簽名方案的系列博客的終章。你可以在這裡找到本系列第一篇文章（中文譯本）。
現在，我們要到達有趣的部分了 —— 真正的簽名方案。
PQCrypto 在一個多月以前已經放出了一份初步建議。其中建議的兩種後量子算法是 “XMSS” 和 “SPHINCS”：
本文將先介紹 XMSS，一種帶狀態的簽名方案；然後是 SPHINCS，第一種無狀態的簽名方案！
XMSS
“延展的默克爾簽名方案（eXtended Merkle Signature Scheme，XMSS）” 在 2011 年出現，然後在 2015 年成為 IETF（互聯網工程任務組）的草稿。
其主要構造看起來就像一棵默克爾樹，只有少數區別。在 XMSS 樹上，子節點在哈希到親節點之前，回先與一個掩碼（mask）運行異或（XOR）運算。每個節點的掩碼都不同：
第二個特殊之處在於，XMSS 樹的葉子不是一個一次性公鑰的哈希值，而是另一種樹 —— 叫做 “L-樹” —— 的根值。
L-樹也在節點的哈希值上應用了掩碼；L-樹的掩碼與主 XMSS 樹的不同，但在所有 L-樹之間都是通用的。
L-樹的葉子存儲了一個 WOTS+ 公鑰的元素（這種方案在本系列的第一篇文章中有解釋（中文譯本））。
如果你像我一樣，疑惑什麼要在樹上存儲一個 WOTS+ 公鑰，以下是 Huelsing 的解釋：
樹結構的用途並不是存儲一個 WOTS 公鑰，而是為了哈希它，並且這種方式讓我們可以證明，一種具備 “第二原像抗性” 的哈希函數就足夠了（不需要具備碰撞抗性的哈希函數）。
此外，主公鑰由 XMSS 樹的根節點以及用在 XMSS 樹和 L-樹 中的比特掩碼組成。
SPHINCS
“SPHINCS” 是更新的一種方案，結合了這個領域的許多進步，還不止！它帶來了我們所有人期待已久的無狀態性。
沒錯，這意味著你不需要再保存任何狀態了。但在解釋它如何做到之前，我們先來看看 SPHINCS 的構造。
首先，SPHINCS 是由許多樹組成的。
我們來看第一棵樹：
- 每個節點，都是前面的節點的拼接與所在層級的比特掩碼運行異或運算的結果的哈希值。
- 公鑰是根哈希值以及比特掩碼。
- 樹的葉子是 WOTS+ L-樹 的壓縮公鑰。
請將 WOTS+ L-樹看成我們前面解釋的 XMSS L-樹，只是，其比特掩碼設計看起來更像一棵 SPHINCS 哈希樹（也就是樹的每一層有一個專門的掩碼）。
每一個葉子，都包含了一個 Winternitz 一次性簽名，允許我們簽名另一棵樹。所以，按照上圖，下一疊（layer）將有 4 棵 SPHINCS 樹，在它們的葉子裡都包含 WOTS+ 公鑰。
如是不斷往下延伸 …… 有多少疊的樹、每棵樹有多少葉子，全看你最初的參數。最終，在你到達第 0 層（layer 0）的時候，WOTS+ 簽名不再簽名其它 SPHINCS 樹，而是 HORS 樹。
HORS 樹與 L-樹在結構上是一樣的，只是它包含的是 HORS 少量次數簽名，而不是 Winternitz 一次性簽名。我們使用它來簽名我們的消息，而這將提高這個方案的安全性，因為，只要我們簽名一條消息時總是使用相同的 HORS 密鑰，就不會釀成大禍。
以下是一張圖，來自 SPHINCS 論文，它抽象掉了 WOTS+ L-樹（將它們顯示為下一棵 SPHINCS 樹的簽名），並展示通向一條消息的唯一路徑：
在簽名消息 M 時，我們先創建 M 的一個 “隨機化” 哈希值以及一個 “隨機” 索引號。我使用雙引號是因為，在 SPHINCS 簽名方案中，一切都是使用一個偽隨機函數確定性地計算除了的。這個參數告訴你，要用哪棵 HORS 樹來簽名 M 的隨機化哈希值。這就是為什麼你無需記憶狀態：因為索引號是根據消息確定性地取出的。簽名同一條消息總是會使用同一棵 HORS 樹；而簽名兩條不同的消息，將有很大的概率使用兩棵不同的 HORS 樹。
本系列到此結束！
補充：以下是來自論文《Armed SPHINCS》的另一張圖示，我認為非常好！
（完）
