安全 PRP 的反面也是安全 PRP 嗎？
如果分組密碼是安全 PRP，那麼它是否也是安全 PRP 的逆？我的直覺說是的，但我不確定。
在相關的說明中，如果分組密碼是安全的 sPRP，那麼它是安全的 sPRP 的逆嗎？
我使用的術語“PRP = 防止選擇明文攻擊”、“sPRP = 強 PRP = 防止選擇明文/密文攻擊”，其中“安全 = 與隨機排列無法區分”。
**理論上。**不，安全 PRP 的逆不一定是安全 PRP。
這是我們可以保證的。安全 sPRP（強偽隨機排列）的逆保證是安全 sPRP。任何安全的 sPRP 都是安全的 PRP。因此，安全 sPRP 的逆將是安全 PRP。
僅供參考，如果您不熟悉 PRP/sPRP，PRP 和 sPRP 之間的區別是：
- PRP 對自適應選擇明文攻擊是安全的
- sPRP 對自適應選擇明文/密文攻擊是安全的
警告：我剛剛了解到，這個術語顯然不是 100% 標準的，有些人使用不同的術語（例如，弱 PRP / PRP 或 PRP-CPA / PRP-CCA 而不是 PRP / sPRP）。因此，請注意，如果您更喜歡其他術語，請務必相應地翻譯我的陳述。我意識到這可能會影響您問題的含義。
**在實踐中。**在實踐中，當我們做出“AES 是安全的”這樣的陳述時，我們通常指的是“AES 是一個安全的 sPRP”。有時您可能會看到人們對 PRP 和 sPRP 之間的區別很草率，但任何未破解的現代分組密碼通常都可以被認為是安全的 sPRP。因此，任何現代分組密碼（如 AES）的逆也將是一個安全的 PRP。
**證明。**對於加密純粹主義者來說，這裡證明了安全 PRP 的逆不一定是安全 PRP。
定義 $ E_k $ 如下：
$$ E_k(x) = \begin{cases} 0 &\text{if $x=k$}\ \text{AES}_k(k) &\text{if $x=\text{AES}_k^{-1}(0)$}\ \text{AES}_k(x) &\text{otherwise.} \end{cases} $$ 很容易檢查 $ E_k(\cdot) $ 是每個的排列 $ k $ .
證明也很簡單 $ E $ 是一個安全的 PRP（對 AES 做出合理的假設，例如，它可以被建模為一個理想的密碼）。為什麼？因為 $ E_k(\cdot) $ 同意 $ \text{AES}_k(\cdot) $ 除了兩個輸入值之外，攻擊者不知道這些輸入值是什麼。對手能做的最好的事情就是希望偶然擊中這兩個輸入之一。對手碰巧碰到這兩個值之一的機率很小：在 1 次查詢之後，機率為 $ 2/2^{128} $ ， 之後 $ q $ 查詢，機率為 $ \le 2q/2^{128} $ . 如果 $ q $ 受任何合理值的限制（例如 $ q \le 2^{64} $ )，這個機率可以忽略不計。
也很容易證明 $ E^{-1} $ , 的倒數 $ E $ , 不是安全的 PRP。您所要做的就是查詢明文的逆 $ 0 $ ，然後你取回密鑰（因為我們的定義 $ E $ 已確保 $ E^{-1}_k(0)=k $ ）。因此，單個選擇明文查詢完全中斷 $ E^{-1} $ .
這證明了存在一個 PRP 但其逆不是 PRP 的密碼，或者換句話說，PRP 的逆不一定保證是 PRP。