在 Dodis、Katz、Xu、Yung 2002 年關於密鑰絕緣簽名方案的論文中，對手的成功機率是如何計算的？
在這篇論文（Dodis、Katz、Xu、Yung（2002 年）的“強密鑰絕緣簽名方案”）中，我理解了引理 1（第 9 頁）的大部分證明；不過，我對如何計算某些機率感到困惑。
**我認為無需閱讀論文，**您所需要的只是以下內容：
語境
- 對手 $ A $ 打破（“新”）計劃 $ \Pi $
- 挑戰者 $ A’ $ 想打破底層方案 $ \Theta $ 使用 $ A $
- 簽名預言機將消息和時間段作為輸入 $ i $
- 對簽名預言機的最大查詢數是 $ q(k) $
令人困惑的部分：
在某些時候，挑戰者 $ A’ $ 隨機抽取 $ r \in {1,..,q(k)} $ 然後看著 $ r^{th} $ 簽署查詢 $ A $ 使。
- 如果此查詢輸入的時間段已在先前的簽名查詢中使用，則中止實驗。
- 如果這是該時間段的第一次（表示 $ i^* $ ) 被查詢，繼續。
- 如果 $ A $ 隨時查詢或查詢過“關鍵曝光”預言機的時間段 $ i^* $ ，也中止（密鑰暴露=顯示查詢期間的密鑰）。
到底， $ A $ 在一段時間內偽造簽名 $ i $ . （自適應地，我認為，所以 $ i $ 開始時不是固定的，但 A 在最後選擇了它。）
然後論文說：
至少有機率 $ 1/q(k) $ , 實驗沒有中止並且 $ i^∗ = i $
$$ .. $$.
我猜
$ P(\text{experiment not aborted } \wedge, i^∗ = i) =\ P(\text{period }i^* \text{not queried before } r^{th} \text{signing query } \wedge, \text{no key exposure query for }i^* \wedge, i^∗ = i ) $
現在怎麼辦？我不明白計算如何如此明顯。我能想到很多問題：
- 這些事件是否都是獨立的，因此 $ P(\text{period }i^* \text{not queried before } r^{th} \text{signing query } \wedge, \text{no key exposure query for }i^* \wedge, i^∗ = i ) = P(\text{period }i^* \text{not queried before } r^{th} \text{signing query })P(\text{no key exposure query for }i^)*P( i^∗ = i )? $
- 是 $ P( i^∗ = i )=1/q(k) $ 或者是對手選擇一個更高的機率 $ i $ 對於他們知道的偽造品（=他們之前查詢過的）？還是我們假設 $ A $ 的查詢是隨機的？為什麼我們會這樣假設？
- 是 $ P(\text{period }i^* \text{not queried before } r^{th} \text{signing query }) $ 所有人都一樣 $ r $ 還是小號更高 $ r $ （“早期”查詢）？是否取決於是否 $ P( i^∗ = i ) $ ?
老實說，我很困惑，沒有進一步解釋就給出了這個機率，我一定遺漏了一些基本的東西。你能幫我嗎？
對手 $ A $ 休息計劃 $ \Pi $ 通過生成某種偽造品。每個偽造品都可以被賦予一些標籤 $ i $ . 這個標籤 $ i $ 由對手選擇，但只有多項式的選擇 $ i $ .
減少算法可以將事物設置為看起來就像世界一樣 $ A $ 預計。此外，減少算法可以設置特定的東西 $ i^* $ 記住，所以如果對手製造了一個偽造品，其標籤恰好是 $ i^* $ ，則約簡算法可以成功破解方案 $ \Theta $ . 重要的是，這可能是你缺少的東西， $ A $ 對事物的看法獨立於 $ i^ $* . 換言之，無論具體 $ i^* $ 簡化是考慮到，它總是產生一個完美忠實的世界模擬， $ A $ 預計。
約簡算法應該如何選擇 $ i^* $ ? 它無法提前預測對手的偽造品將具有什麼標籤。所以它會選擇 $ i^* $ 從多項式的眾多選擇中均勻地隨機選擇。
為什麼這行得通？最終，對手輸出偽造品，偽造品帶有一些標籤 $ i $ . 如果對手的整個觀點獨立於 $ i^* $ ，那麼對手的選擇 $ i $ 是獨立的選擇 $ i^* $ . 自從 $ i^* $ 是均勻分佈且獨立於 $ i $ ，我們可以說 $ \Pr[i=i^*] = \frac{1}{\mbox{# of choices}} $ .
在您的設置中，“標籤” $ i $ 偽造是（顯然 - 我按照你的指示沒有實際閱讀論文）使用偽造中指定的時間段進行的第一個簽名-oracle查詢的索引。如果縮減算法可以預測在對手偽造的時間段內哪個簽名預言查詢將是第一個發出的，那麼它將對該查詢做一些特殊的響應（嵌入一些有助於它破解的資訊） $ \Theta $ ）。當然它無法預測偽造品的這個屬性，所以它猜測。只有 $ q(k) $ 這個“特殊”查詢的身份的可能性。
在您的設置中，也有一些中止發生，但這會分散真實機率問題的注意力。真正發生的事情是這樣的：減少只是成功打破 $ \Theta $ 當它的猜測 $ i^* $ 等於標籤 $ i $ 的 $ A $ 的贗品。這裡的作者說，當它看到它的猜測將是錯誤的時，減少可能會放棄（即中止）。如果他們將縮減算法編寫為永不中止，而只是在中斷時盲目地“在黑暗中刺傷”，那會很好 $ \Theta $ 在這些情況下。