WOTS+：為什麼在通過散列函式執行數據之前進行異或？
我正在用一種新語言實現 WOTS+，我似乎無法理解 WOTS+ XOR 在散列之前使用遮罩輸入的事實。
我試圖尋找任何理由，但到目前為止還沒有找到任何理由。在我看來，我似乎也無法想出使這更安全的邏輯。例如，此消息來源說：
在每次迭代中，PRF 用於生成 F 的密鑰和位遮罩，該位遮罩在 F 處理之前與中間結果進行異或。
但這並不能解釋為什麼這個 XOR 如此重要。為什麼首先需要一個隨機遮罩？據我所知，您應該將遮罩連同簽名和消息一起公開，以便獲得對其進行簽名的最終公鑰。
它允許將結構的安全性降低到第二原像抗性，而不是碰撞抗性。這是一個顯著的區別，因為對抗碰撞阻力的蠻力是 $ 2^{n/2} $ 而針對第二原像抵抗的蠻力是 $ 2^n $ . 簡而言之，這個 XOR 技巧允許方案中的簽名/密鑰的長度是相同安全級別的一半。
很難解釋為什麼 XOR 技巧有助於證明，而不涉及雜草。但這裡有一個關於如何證明類似 Winternitz 方案的安全性的草圖。
安全性降低 $ \mathcal{S} $ 扮演一個試圖打破第二原像抵抗的對手的角色。它必須向對手提供公鑰和簽名 $ \mathcal{A} $ 試圖打破不可偽造性。在這種情況下 $ \mathcal{A} $ 產生簽名偽造， $ \mathcal{S} $ 應該打破第二原像阻力。
在普通的 Winternitz 中，我們想像一個雜湊鏈從 $ x_0 $ 與 $ x_i = f(x_{i-1}) $ . 公鑰是 $ x_n $ . 減少 $ \mathcal{S} $ 會猜測一個索引 $ i^* $ 這樣 $ \mathcal{A} $ 將要求籤名值晚於 $ i^* $ 在鏈中，但會生成一個由等於或之前的值組成的偽造 $ i^* $ 在鏈中。如果猜測是正確的，那麼我們想要 $ \mathcal{S} $ 打破第二原像抗性 $ f $ 不知何故。
$ \mathcal{S} $ 本身就是試圖打破第二原像抵抗。它將請求第一個原像 $ a $ 並嘗試找到第二個原像 $ a’ \ne a $ 和 $ f(a) = f(a’) $ . 它需要納入 $ a $ 以某種方式進入雜湊鏈 — 理想情況下，設置 $ x_{i^} = a $ ，因此如果對手計算出一個原像 $ x_{i^+1} $ , 這將是 $ a $ .
但如果 $ x_{i^}=a $ , 那麼是什麼 $ x_0, \ldots, x_{i^-1} $ 這樣 $ x_i = f(x_{i-1}) $ ? 減少 $ \mathcal{S} $ 無法形成一致的鏈條。它接收 $ a $ 在外部，需要計算一個原像 $ a $ .
然而，如果我們以 W-OTS+ 的方式擴充該方案，我們有額外的 $ r_i $ 價值觀和 $ x_i = f(x_{i-1} \oplus r_{i-1}) $ . 這些 $ r_i $ 值允許減少“將事物拼湊在一起”。
減少 $ \mathcal{S} $ 選擇 $ x_0 $ 併計算一個前向鏈，直到 $ x_{i^} $ ， 照常。然後它收到 $ a $ 外部，並選擇 $ r_{i^} $ 以便 $ r_{i^} \oplus x_{i^} = a $ . 這意味著輸入到下一個 $ f $ 是 $ a $ . 這意味著要偽造， $ \mathcal{A} $ 將不得不找到一個原像去 $ a $ . 從這一點開始，鏈的其餘部分將正常計算。
因此，額外的 XOR 只是為減少提供了額外的靈活性，可以在雜湊鏈中插入“陷阱”——確保特定的 $ a $ 用作輸入 $ f $ 在鏈中，即使當歸約算法 $ \mathcal{S} $ 自己沒有選擇 $ a $ . 這正是將簽名安全性降低到第二原像抗性所需要的。