Lamport簽名的雜湊抗碰撞要求
根據原始論文，Lamport 一次性簽名方案使用兩個單向函式： $ F $ 和 $ G $ . 前一個， $ F $ , 用於通過對私鑰的元素進行散列處理來創建公鑰（也用於在驗證時對簽名元素進行散列處理）；後者， $ G $ , 用於在簽名和驗證時對消息進行雜湊處理，以獲得與密鑰中的對數相對應的位數。
據我了解，要求 $ F $ 是它必須能夠抵抗原像攻擊，並且 $ G $ ，除此之外，還必須具備抗碰撞能力。
給定滿足所有這些要求的標準雜湊函式，我假設 $ F $ 和 $ G $ 可以是相同的，例如 SHA-256，它提供 256 位安全性防止原像攻擊和 128 位安全性防止衝突攻擊。使用它，我們有以下密鑰和簽名大小（描述為維度數組）：
Private key: [256][2][32]byte (16 KiB) Public key: [256][2][32]byte (16 KiB) Signature: [256][32]byte (8 KiB)我的問題是：如果我們的目標是整體 128 位安全性，我們可以減少 $ F $ 到 128 位而不是 256 位，留下 $ G $ 照原樣。做 $ F $ 需要抗碰撞性？
例如，如果我們使用 SHA-256/128 $ F $ 和 SHA-256 $ G $ ，這將為我們提供以下尺寸：
Private key: [256][2][16]byte (8 KiB) Public key: [256][2][16]byte (8 KiB) Signature: [256][16]byte (4 KiB)這會給我們 128 位的安全性嗎？
在描述 Lamport 簽名的維基百科頁面上，有這樣一段：
對於每個私鑰 $ y_{i,j} $ 及其對應的 $ z_{i,j} $ 公鑰對，必須選擇私鑰長度，因此對輸入長度執行原像攻擊不會比對輸出長度執行原像攻擊快。例如，在退化的情況下，如果每個私鑰 $ y_{i,j} $ 元素長度只有 16 位，窮舉搜尋所有元素是微不足道的 $ 2^{16} $ 可能的私鑰組合 $ 2^{15} $ 無論消息摘要長度如何，都可以找到與輸出匹配的操作。因此，平衡的系統設計可確保兩個長度大致相等。
但是我不明白：什麼是輸入和輸出以及什麼消息摘要長度（是輸出的長度嗎？ $ G $ , $ F $ , 或兩者都有），哪一部分是指鍵中元素的數量，哪一部分是指單個元素的長度？我會很感激一個更好的解釋。謝謝！
是的，將散列截斷為 128 位是有意義的。安全證明實際上表明，如果為 F 找到原像需要努力 $ 2^{n} $ ，然後打破 Lamport 簽名方案 $ G $ 擁有 k 位摘要需要努力 $ 2^{n}/2k $ . 所以嚴格來說，與 $ F $ 截斷為 128 位和 $ G $ 有 256 位 $ (2k=512=2^{9}) $ ， 你將會有 $ 128-9=119 $ 一點安全感。
這不是安全證明的產物：因為有 $ 256*2=512 $ 與普通的單一原像攻擊相比，攻擊者找到原像的機會多 512 倍。
在 Merkle 簽名方案中，結果是相同的，但您需要將 k 乘以可以簽名的消息數。EG 100萬 $ (2^{20}) $ 消息，安全級別是 $ 128-9-20=99 $ 位。
維基百科的文章是關於 $ F $ 僅：“輸入”是私鑰之一，“輸出”是對應的公鑰，“消息摘要大小”是輸出大小 $ F $ . 我認為它只是試圖說當私鑰很短並且無論輸出大小如何 $ F $ ，找到原像是微不足道的。