不是強 PRP 的 PRP 範例
偽隨機排列的安全性的確切定義很簡單——對於某些加密方案 $ E,\colon,\mathcal{K}\times\mathcal{D}\rightarrow\mathcal{D} $ , 一定是沒有有效的對手可以區分的情況 $ E_k(\cdot) $ 從 $ \Pi(\cdot) $ （上的隨機排列 $ \mathcal{D} $ ) 除非機率可以忽略不計。“強” PRP 的定義方式相同，除了 $ E_k(\cdot) $ 和解密 $ D_k(\cdot) $ 必須共同無法區分 $ \Pi(\cdot) $ 和 $ \Pi^{-1}(\cdot) $ .
我已經考慮過這一點，但我無法舉出一個例子 $ E $ 其加密與隨機排列無法區分，但其解密不具有相同的屬性。有沒有人有一個很好的例子？
三輪 Feistel 網路是安全“弱”PRP 但不是“強”PRP 的現實構造的一個很好的例子。
Feistel 網路使用排列 $ P_f(L, R) = R, (L\oplus f(R)) $ ， 在哪裡 $ f $ 是偽隨機函式族的一個元素。此 PRP 將使用三個鍵進行鍵控 $ k_1, k_2, k_3 $ , 這將用於加密 PRF $ F $ 每一輪都不一樣。
我們定義 $ E_{k_1,k_2,k_3} $ 成為一個三輪Feistel網路：
$ E_{k_1,k_2,k_3}(L | R) = \operatorname{Concat}(P_{F_{k_3}}(P_{F_{k_2}}(P_{F_{k_1}}(L, R)))) $
假設 $ F $ 是一個 PRF， $ E $ 將滿足弱 PRP 的定義。我相信這個證明最初歸功於 Luby, Rackoff（有關證明的詳細資訊，請參見此處，從第 11 頁開始）。同樣，逆 $ D_{k_1,k_2,k_3} = E^{-1}_{k_1,k_2,k_3} $ 也是一個弱PRP。
不過有趣的是， $ E $ 不是一個強大的PRP。當同時訪問“前向”預言機和“後向”預言機時，攻擊者可以區分 $ (E_{k_1,k_2,k_3}(\cdot), D_{k_1,k_2,k_3}(\cdot)) $ 和 $ (\Pi(\cdot), \Pi^{-1}(\cdot)) $ ， 在哪裡 $ \Pi $ 是同一域上的隨機選擇排列。
這是一個以高機率區分兩者的對手：
- 用兩個零位字元串查詢解密預言： $ (a|b) \leftarrow D(0|0) $
- 查詢加密預言機： $ (c|d) \leftarrow E(0|a) $
- 再次查詢解密預言機： $ (e|f) \leftarrow D((b\oplus d)|c) $
- 如果 $ e=c\oplus a $ ，然後返回 $ 1 $ , 否則返回 $ 0 $ .
這就是為什麼它有效：
- 通過展開，我們看到 $ D_{k_1,k_2,k_3}(L|R) = (x|y) $ ， 在哪裡：
$ x=R \oplus F_{k_2}(L \oplus F_{k_3}(R)) $
$ y=L \oplus F_{k_3}(R) \oplus F_{k_1}(R \oplus F_{k_2}(L\oplus F_{k_3}(R))) $
- 因此，第一個 oracle 查詢將導致：
$ a=F_{k_2}(F_{k_3}(0)) $
$ b=F_{k_3}(0) \oplus F_{k_1}(a) $
- 通過展開，我們看到 $ E_{k_1,k_2,k_3}(L|R) = (x|y) $ ， 在哪裡：
$ x=R \oplus F_{k_2}(L \oplus F_{k_1}(R)) $
$ y=L \oplus F_{k_1}(R) \oplus F_{k_3}(R \oplus F_{k_2}(L\oplus F_{k_1}(R))) $
- 因此，第二個 oracle 查詢將導致：
$ c=a \oplus F_{k_2}(F_{k_1}(a)) $ 和
$ d=F_{k_1}(a) \oplus F_{k_3}(c) $ .
- 注意 $ b $ 和 $ d $ 兩者都包含該術語 $ F_{k_1}(a) $ . 當我們計算 $ b\oplus d $ ，條款取消：
$ b\oplus d=F_{k_3}(0) \oplus F_{k_3}(c) $
- 最後，在第三個 oracle 查詢中，特製的 $ L $ 和 $ R $ 導致以下簡化：
$ e=c \oplus F_{k_2}((b\oplus d) \oplus F_{k_3}(c))\=c \oplus F_{k_2}(F_{k_3}(0))\=c \oplus a $
- 對手發現 $ e=c\oplus a $ 根據需要，對於真正隨機排列的可能性很小。
基本思想是進行設置，以便 $ F_{k_2} $ 在兩個不同的查詢中接收相同的輸入。這會導致左預言機輸出被相同的值掩蓋，這可以被對手檢測到。
至關重要的是，如果沒有在兩個方向上查詢排列的能力，這種攻擊就不會起作用。