Post-Quantum-Cryptography
256 位雜湊安全級別的廣義 Haircomb OTS 與 Winternitz OTS
假設使用 256 位散列（SHA2、SHA3、…）。Winternitz OTS 在各種簽名大小下的表現如何？
我想與廣義的 K 牙髮梳進行比較：
- 它的簽名是 $ K $ 這些 256 位雜湊
- 公鑰是一個雜湊。
- 我們也在簽署一個 256 位的消息摘要
- 鍊長近似為¹（根據白皮書）： $$ X\approx2^{256/(K-1)}\times{(K-1)!}^{1/(K-1)}-K/2 $$
- 密鑰生成執行 $ X\times K+1 $ 雜湊
- 簽名呼叫執行 $ X\times(K-1) $ 雜湊
- 驗證呼叫執行 $ X+1 $ 雜湊。
問題：例如 SPHINCS+ 標準所使用的 Winternitz OTS 的等效雜湊呼叫計數是多少？
請注意，我專門詢問用於簽名、驗證和密鑰生成的雜湊呼叫的數量。
¹ $ X $ （對於一個鏈）在此表中近似（四捨五入，不精確）。
問題：例如 SPHINCS+ 標準所使用的 Winternitz OTS 的等效雜湊呼叫計數是多少？
好吧，至少我可以回答。
對於 Sphincs+（或者，一般來說，WOTS $ w=16 $ ）， 和 $ n=32 $ （256 位雜湊），我們有 $ x=15 $ （因為 $ w=16 $ 並且鏈條比那個少一個），並且 $ k=67 $ .
因此，在 OTS 密鑰生成期間，我們執行 $ kx+1 = 1006 $ 雜湊
$$ 1 $$, 簽名大約是$$ 2 $$ $ (k/2)x = 503 $ 雜湊，驗證大約是 $ (k/2)x + 1 = 504 $ 雜湊。 對於 Sphincs+，OTS 密鑰生成是主要成本（因為我們在 Sphincs+ 簽名生成期間執行了很多）；Haircomb 似乎需要更多，因此不太適合。
$$ 1 $$: 有點誤導；最終的散列相當昂貴，因為散列的數據量要大得多。 $$ 2 $$：大約是因為它取決於被散列值的權重。