Merkle 改進 Lamport 的 OTS 的 KeyGen 是如何工作的？

在他的論文中

$$ 1 $$在第 17 頁和第 18 頁，Merkle 提出了對 Lamport 的 OTS 的改進，方法是僅在消息中籤名 1 並結合消息中 0 數量的校驗和。我得到了直覺，以及為什麼這會平均將簽名大小減少一半。但是，我不確定私鑰/公鑰應該是什麼樣子？ 我覺得如果密鑰的生成方式與“預設”Lamport 的 OTS 相同，那麼公鑰/私鑰將不必要地大。

在這個部落格中

$$ 2 $$，我發現確實不是這樣，作者說 pk/sk 也被減半，因為只包括了 1。對我來說，不清楚消息中的每一位（0 和 1）是否只生成一個隨機字元串 $ sk_{i,1} $ 並在公鑰中散列，或者如果消息中的每個 1 位都有一對字元串 $ (sk_{i,0},sk_{i,1}) $ 生成，並且沒有 0 位？ 另外，我認為校驗和的 0 位也已簽名，並且僅省略了消息的 0 位，這是正確的嗎？

1. http://www.merkle.com/papers/Certified1979.pdf
2. https://blog.cryptographyengineering.com/2018/04/07/hash-based-signatures-an-illustrated-primer/

您只需要儲存 1 的雜湊值。最後的校驗和位（對 0 的數量進行編碼）確保消息不能以將 1 向下翻轉為 0 的方式製作，因為這樣做會在校驗和部分中創建額外的 1，這將需要從私有中揭示額外的原像鑰匙。

引用自：https://crypto.stackexchange.com/questions/70371