Signature

Lamport簽名的雜湊抗碰撞要求

  • August 31, 2014

根據原始論文,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 $ ,找到原像是微不足道的。

引用自:https://crypto.stackexchange.com/questions/3977