Provable-Security
確定性對手和機率性對手一樣強大嗎？
SOURCE在定理 2 的證明中陳述如下：
不失一般性，我將假設 A 是確定性的。如果 A 是隨機的，我們可以通過固定一個最大化 A 的條件成功機率的硬幣序列來確定它；不難看出，這並不能降低A的優勢。
這個對嗎？這是否意味著我們不需要在密碼安全遊戲中考慮機率對手？
按照 fkraiem 的回答，我會分享我的想法。
一般來說，我們不知道隨機性是否有幫助，即P=BPP是一個懸而未決的問題。因此，機率多項式時間 (PPT) 的對手可能不等於確定性的對手。
然而，密碼學似乎總是（如果我錯了，請糾正我）關注與 PPT 對手相關的優勢（或類似的東西）。在這種情況下，只考慮確定性對手就足夠了。這是一個簡單的證明：
假設你有一個擁有優勢的 PPT 對手 Ap $ p $ . 然後你可以修復所有可能的隨機硬幣並獲得一堆確定性對手一個1,一個2,…,一個n $ A_1, A_2, …, A_n $ ， 在哪裡一個 $ A $ 執行一個一世 $ A_i $ 有機率p一世 $ p_i $ . 自從一個d在(一個)=p1一個d在(一個1)+⋯+pn一個d在(一個n) $ Adv(A) = p_1Adv(A_1) + \cdots + p_nAdv(A_n) $ 和1=p1+⋯+pn $ 1=p_1+\cdots+p_n $ ， 那裡存在ķ $ k $ 這樣一個d在(一個ķ)≥一個d在(一個)=p $ Adv(A_k) \geq Adv(A) = p $ . 注意n $ n $ 可能是指數的，但每個對手一個一世 $ A_i $ 在多項式時間內執行。還有，知道一個ķ $ A_k $ 存在並不意味著可以在多項式時間內找到它。
===================
更新：上述論點也適用於資訊論（即計算無界）的對手。