Hash-Signature
Lamport-Diffie + 試圖反轉 OWF
我正在研究 Lamport-Diffie 簽名方案，並在我的講座中介紹了嘗試反轉單向函式的以下算法 $ f $ ， 在哪裡 $ f $ 用於從私鑰計算此簽名的公鑰 $ sk=\left(\begin{array}{rrrrrr} x_{1,0} & x_{2,0} & \cdots & x_{l,0} \ x_{1,1} & x_{2,1} & \cdots & x_{l,1} \end{array}\right) $ . 我的問題是為什麼可以執行句子 2，如果 $ x_{i,b} $ 是私鑰的一部分嗎？
唯一的要求是 $ i,b \neq i^,b^ $ 在哪裡 $ i^* $ 是一個隨機值 $ 1 $ 到 $ l $ 和 $ b^* \gets{0,1} $ 因此，如果 $ b^*=0 $ 然後 $ b=1 $ .
不要被它所迷惑 $ x $ ，和秘鑰沒有關係，只是後來變成的一個變數 $ y_{i,b}=f(x_{i,b}) $ . 它也可以稱為 $ a $ .
我猜這是您的另一個問題Lamport-Diffie + Security Proof的算法。
這裡發生的是這樣的：
- 我們為 LD-Sign 方案創建一個特殊的公鑰和密鑰：我們選擇 $ x_{i,b} $ 除一個條目外的所有條目（即 $ x_{i^,b^} $ ) 這是我們的密鑰。在公鑰中我們只是應用 $ f(x) $ 到所有隨機選擇的值。一個空的條目被設置為我們的挑戰 $ y $ .
- 我們假設算法 $ \mathcal{A} $ 存在，它獲取公鑰並可以向 oracle 請求籤名。
- 我們扮演預言家的角色。這對一半的查詢沒有問題：如果創建簽名不需要 $ y $ ， 我們可以完成這個。如果我們不得不用原像來回答 $ y $ ，我們只是重新開始。
- 我們希望攻擊者的最終偽造 $ \mathcal{A} $ 包含原像 $ y $ , 有 50% 的機會。
這個PPT能夠回答原像查詢 $ f $ ，但這取決於存在 $ \mathcal{A} $ . 不涉及其他任何內容：如果 $ \mathcal{A} $ 存在，所以存在 $ \mathcal{I} $ . 但是，如果我們假設，那 $ f $ 是單向的，那麼 $ \mathcal{I} $ 一定不存在。因此 $ \mathcal{A} $ 一定不存在。