本日重點：ht_sign、xmss_sign 和 wots_sign

ht_sign 的演算法還有 3 個地方要講 wots_sign、xmss_pk_from_sig 和 wots_pk_from_sig。

xmss_sign、wots_sign、xmss_pk_from_sig 和 wots_pk_from_sig，他們的 output 和 input 以這個流程互動

1. xmss_sign 產生 XMSS Signature 的時候，會用 wots_sign 產生一個 WOTS+ signature
2. xmss_pk_from_sig，會去 call wots_pk_from_sig，然後將 XMSS Signature 裡的 WOTS+ signature 做為 wots_pk_from_sig 的 input

Page 34, HT Signature 是 (h + d * len) * n bytes

FIPS 第 22 頁[1] 是 XMSS signature 的結構

XMSS signature 的 size 就是 (len * n) + h' * n, (len + h') * n bytes

第 26 頁，hypertree 有 d 層，每一層的高是 h'，全部加起來就是 ℎ = 𝑑 ⋅ ℎ′

The hypertree has 𝑑 layers of XMSS trees with each XMSS tree being a Merkle tree of height ℎ′, so the total height of the hypertree is ℎ = 𝑑 ⋅ ℎ′

所以 d = h/ℎ′

一個 HT signature 有 d 個 XMSS signature，一個 XMSS signature 的 size 是 (len * n) + h' * n

xmss_sign 的產出是一個長度為 (len + h') * n bytes, 704 bytes 的陣列, 704 是這麼算的

h' = 9
n = 16
𝑙𝑒𝑛 = 2𝑛 + 3 = 35
𝑙𝑒𝑛 + h' = 44
(𝑙𝑒𝑛 + h') * n = 44 * 16 = 704

xmss_sign 在 ht_sign 裡簽的是 XMSS public key 或 FORS public key，不論是哪一種, 都是 n bytes，這個 n 取決於是 Parameter Sets 的哪一種，因為本系列只探討 SLH-DSA-SHA2-128s，所以 n 是 16。

所以 xmss_sign 應該是這樣

xmss_sign(uint8_t out[704], 
          const uint8_t M[16], 
          const uint8_t sk_seed[16], 
          unsigned int idx,
          const uint8_t pk_seed[16],
          const uint8_t adrs[32]);

當然，hardcode 不好，很快會改成 #define

line 7，xmss_sign 會 call wots_sign

wots_sign 的演算法

message M 可以是 XMSS public key 也可以是 FORS public key

像以下這行，root 就是 XMSS public key，它也可以是 wots_sign 的 input (經過 xmss_sign 去 call wots_sign)

𝑟𝑜𝑜𝑡 ← xmss_pkFromSig

所以 wots_sign 應該是這樣

wots_sign(uint8_t out[35],
          const uint8_t M[16], 
          const uint8_t sk_seed[16], 
          const uint8_t pk_seed[16], 
          const uint8_t adrs[32]);

在這裡我要提到 KAT 的 rng.c，NIST 提供的 Known Answer Tests (KAT) 包括了 rng.c，因為簽完之後，會用 KAT 來驗證，所以，必須和NIST使用一樣的亂數，才能得到一樣的結果以進行比對。基於這個考量，我們的實作會開始導入 KAT 的 rng.c。

KAT 的使用方式，簡單來說, 要自己寫 api.h 和 sign.c，然後在編譯的時候使用 NIST 提供的 PQCgenKAT_sign.c、rng.c 和 rng.h。

今天先寫到這裡，明天就會將 SK.seed、PK.seed 使用 KAT 的 rng.c 來產生亂數。

References

1. FIPS 205 Stateless Hash-Based Digital Signature Standard
2. PQC - Known Answer Tests and Test Vectors