關於約簡證明樣式的問題
在密碼學安全證明中主要使用約簡證明技術。我現在已經閱讀了很多簡化證明，並且我自己也做了一些，我想我理解得很好。在閱讀這些證明時，我注意到這種減少的兩種主要風格。
說我們有計劃 $ B $ 基於 $ A $ . 我們知道 $ A $ 是安全的。如果一個人想證明安全性 $ B $ 通過減少它的安全性 $ A $ 他可以進行如下操作：
- 風格：假設一個可以打破的對手 $ B $ $ \Rightarrow $ 為了減少一個人可以建立一個新的對手打破 $ A $ 使用對手破壞 $ B $ $ \Rightarrow $ 結果是一個矛盾表明，沒有不可忽略的對手反對 $ B $
- 風格：假設一個任意的 ppt 對手反對 $ B $ $ \Rightarrow $ 顯示（例如通過實驗的隨機分析）打破 $ B $ 像打破一樣難 $ A $ ，因此降低了破解的複雜度 $ B $ 打破的複雜性 $ A $ $ \Rightarrow $ 因為只有微不足道的對手 $ A $ 沒有不可忽視的對手 $ B $
當然這是簡化的，但我想告訴你我注意到了什麼。
我的問題：這些風格真的存在嗎？他們都可以（正確地正式寫下）證明相同嗎？它們都（尤其是樣式 1.）是否完整？對於什麼證明應該使用哪種風格？
**編輯：**風格 2 的更精確定義。：在現代密碼學簡介中，證明 PRG 上的密碼系統：在他們指出的隨機分析中，破解密碼系統與破解 PRG 一樣可能。他們用這個來暗示，任何任意的對手都必須在時尚中可以忽略不計：因為這是可以忽略不計的，並且它們具有相同的機率，另一個也必須可以忽略不計。
（注意：簡而言之，我將 1. 描述為： $ B \rightarrow A \rightarrow \unicode{x21af} \rightarrow B $ 2. 如： $ B \rightarrow A \rightarrow (B = A) \rightarrow B $ )
我在樣式 1 和样式 2 的適當修訂之間看到的唯一區別是樣式 1 缺少關於假設攻擊 B 的對手/算法以及攻擊 A 的結果對手/算法在 2 中明確的內容：
- 算法是機率多項式時間；即有一個帶有隨機位的隱式輸入，並且最多執行一段時間 $ P(n) $ 對於安全參數的所有值 $ n $ （或它們的輸入大小）超過某個下限。
- 它們具有不可忽略（或非消失）的成功機率，即：對於某些多項式 $ P’ $ , 對於任何固定界限 $ N\in\mathbb{N} $ 存在價值觀 $ n>N $ 對於安全參數（或其輸入大小），使得成功的機率至少為 $ 1/P’(n)>0 $ .
“破解密碼系統和破解 PRG 一樣可能”的證明證明了在 2 中我們可以重用多項式 $ P’ $ 和價值觀 $ n $ 對於給定的界限 $ N $ 在證明 A 的攻擊是具有不可忽略的成功機率的攻擊中，它們適用於 B 的假設攻擊。
換句話說，風格 1 是風格 2 的簡化，通常以犧牲嚴謹性為代價。對於樣式 1 中的某些證明，它掌握了樣式 2 以自信地判斷證明是否正確。
還有更複雜的樣式，例如成功機率是定量的。在這種情況下，“破解密碼系統就像破解 PRG 一樣可能”就是所謂的嚴格證明。其他一些定量證明更難遵循。