Provable-Security
澄清對手的優勢與機率/成功
在密碼學中，對於一個多項式有時間限制的對手 $ \mathcal{A} $ , 給定一個方案 $ \Pi $ , 成功或成功的機率 $ \mathcal{A} $ 是可能性 $ \mathcal{A} $ 打破_ $ \Pi $ ，而它的優勢在於它的成功與一成不變的知識之差的絕對值。例如：
- 如果目標是證明 $ \Pi $ 滿足 IND-CPA（不可區分的選擇明文）安全性，可以設計一種遊戲，其目標是 $ \mathcal{A} $ 是區分結果產生的 $ \Pi $ 和一個真正隨機的函式，並輸出它的答案 $ b^\prime $ . 的成功 $ \mathcal{A} $ 是 $ \mathrm{Pr}(b^\prime = b) $ ，它的優點是 $ \mathrm{Adv}_{\mathcal{A},\Pi} =|\mathrm{Pr}(b^\prime = b)-\frac{1}{2}| $ . 在哪裡 $ b $ 是挑戰選擇的位。在這裡，通過減去成功來獲得優勢 $ \frac{1}{2} $ ，這是隨機猜測的機率 $ 0 $ 和 $ 1 $ , 的分佈 $ b $ .
當必須輸出實際結果時，如何建立優勢？
例如，如果遊戲要計算一組中的離散對數 $ (\mathbb{G},g,p) $ , 我們假設成功 $ \mathcal{A} $ 是 $ \mathrm{Pr}(x\in \mathbb{Z}^*_p, y=g^x: x \leftarrow \mathcal{A}(y)) = \lambda $ ，它的優勢是什麼？
- 它是否簡單地等於它的成功，即， $ \mathrm{Adv}_{\mathcal{A}} = \mathrm{Pr}(x\in \mathbb{Z}^*_p, y=g^x: x \leftarrow \mathcal{A}(y)) = \lambda $ ?
- 或者是其成功與輸出分佈中隨機猜測成功的機率之間的差異，即 $ \mathrm{Adv}_{\mathcal{A}} = |\lambda-\frac{1}{\mathrm{order}(\mathbb{G})}| $ ?
最後，哪個概念在安全證明方面更好？計算優勢還是計算成功？
PS：我閱讀了這些問題的答案：
但我無法得到明確的答案。因此，這個新問題。
優勢與成功機率並沒有什麼特別之處，它們應該用在有意義的地方並提高可讀性。在考慮區分遊戲（如加密、PRG 等）時，優勢具有簡化符號的好處。此外，在能夠增加優勢等方面，它“表現得很好”（儘管這應該始終通過區分機率方程進行正式檢查）。請注意，在區分任務時，總是有可能以 1/2 的機率成功。所以，只有知道對手能成功超過1/2 才有趣，這就是優勢。這讓事情變得很好，因為我們可以只談論一個可忽略或不可忽略的優勢。
當考慮計算而不是區分任務時，優勢不再有意義。在這裡，如果對手能夠以不可忽略的機率成功，那麼它就被打破了。因此，成功機率就是您需要談論的全部內容。