證明從 PRP 構造的函式是還是不是 PRF？
讓 $ E $ 是一個偽隨機排列族 $ b $ 位，與 $ E_K $ 與努力小於的隨機排列無法區分 $ O(2^b) $ , 易於計算以及逆排列，例如由 AES-192 實例化 $ b=128 $ . 讓 $ E_A $ 和 $ E_B $ 成為這個家庭的兩個公共成員。
為 $ E_K $ 在 $ E $ ， 讓 $ F_K $ 和 $ G_K $ 成為函式
$$ F_K:x\mapsto F_K(x)=E_K(E_A(x))\oplus E_K(E_B(x)) $$ $$ G_K:x\mapsto G_K(x)=E_K(E_A(x)\lor1)\oplus E_K(E_B(x)\land\overline{1}) $$ 在哪裡 $ \lor1 $ （分別。 $ \land\overline{1} $ ) 設置（分別清除）最右邊的位，並且 $ \oplus $ 是異或。 問：是 $ F $ 和 $ G $ 與隨機函式無法區分的偽隨機函式族，工作量小於 $ O(2^b) $ ?
注意：以前，我想到了攻擊 $ F $ 通過考慮一個循環 $ x\mapsto E^{-1}_B(E_A(x)) $ ; 但仔細想想，那次攻擊是 $ O(2^b) $ .
這是一種不同的攻擊，它執行在 $ O(2^{b/2}) $ 時間。我還將提供一個理論框架，用於如何考慮這類方案的安全性。最重要的是，這種形式的方案似乎都不是安全的。我將在下面嘗試更準確地說明我的意思。
我們可以考慮一個廣義的方案， $ H_K(x) = E_K(f(x)) \oplus E_K(g(x)) $ ， 在哪裡 $ f,g $ 是可以反轉的公共函式（給定 $ f(x) $ , 可以快速找到所有可能的值 $ x $ , 同樣對於 $ g(x) $ ).
定義。定義圖形 $ H $ 是一個有頂點集的無向圖 $ {0,1}^b $ 和一個邊緣 $ (f(x),g(x)) $ 對於每個可能的輸入 $ x $ . 換句話說，對於每個可能的輸入 $ x $ ， 如果 $ H_K(x) $ 採取形式 $ E_K(u) \oplus E_K(v) $ ，然後我們添加邊緣 $ (u,v) $ .
*例子。*圖表為 $ F $ 是隨機排列的圖（即， $ \pi = E_B \circ E_A^{-1} $ ).
*例子。*圖表為 $ G $ 是一個二分圖，其中兩個頂點集的每一個都有大小 $ 2^{b-1} $ . 粗略地說，每個頂點都連接到二分圖另一側的兩個隨機其他頂點。
請注意，假設 $ f,g $ 意味著我們可以很容易地遍歷這個圖：例如，給定一個頂點 $ v $ ，我們可以快速找到所有的邊緣 $ v $ .
直覺如下：我們想到每個頂點 $ v $ 用值標記的圖 $ E_K(v) $ , 我們考慮每條邊 $ (f(x),g(x)) $ 圖的標記為 $ H_K(x) $ . 這些標籤有一個特殊的屬性。如果 $ (u,v) $ 是圖中的一條邊，然後給定以下三個值中的任意兩個，您可以推斷出第三個值： $ u $ ，標籤上 $ v $ ，標籤上 $ (u,v) $ . 當然，我們只會得到邊緣上的標籤，而不是頂點上的標籤，但這種觀點有助於建構我們的思維。
**攻擊 3.**現在是攻擊 $ G $ . 構造圖 $ G $ . 構造一個連結一些的生成樹 $ 2^{b/2} $ 頂點一起形成一個連接的組件（沒有任何循環）。
如何找到這樣的生成樹？一種簡單的方法是選擇任意根頂點 $ r $ ，然後從以下開始進行深度優先（或廣度優先）搜尋 $ r $ , 直到您訪問過 $ 2^{b/2} $ 不同的頂點。一路上，如果你發現一個循環，有一個單獨的方法來區分 $ G $ 從隨機（見下文），所以不失一般性，我們將假設這個搜尋沒有檢測到任何循環。因此，您可以輕鬆地形成所有已遍歷邊的生成樹。
一旦你有了生成樹 $ T $ ，我們在輸入中查詢每個邊對應的oracle $ T $ . 這告訴我們所有這些邊上的標籤。
現在，直覺地，我們將檢查是否存在任何兩個頂點 $ v,w $ 在 $ T $ 具有相同標籤的。當我們沒有在頂點上給出標籤時，我們怎麼能做到這一點？答案是我們實際上會檢查一個不同的標準：對於每一對 $ v,w $ 中的頂點數 $ T $ ，我們將檢查從 $ v $ 到 $ w $ （總有一條這樣的路徑，因為 $ T $ 是一棵生成樹），我們將檢查這條路徑邊緣的標籤是否異或為零。如果他們這樣做，我們將推斷預言是用隨機函式實例化的。如果這從未發生過，我們會猜測我們正在與一個預言機互動 $ H_K $ .
為什麼這行得通？如果我們正在與一個預言機互動 $ H $ ，那麼所有頂點上的標籤應該總是不同的，因為 $ E_K $ 是雙射的。當然，路徑中邊緣上的標籤的異或 $ v $ 到 $ w $ 與標籤上的異或完全相同 $ v $ 和標籤上 $ w $ ， 因此，如果 $ v,w $ 有不同的標籤，那麼這個路徑異或必須是非零的。另一方面，如果我們的預言機被實例化為一個隨機函式，那麼每個路徑異或都是一個隨機值，所以根據生日悖論，一些這樣的路徑異或很可能為零。
從表面上看，這種攻擊需要 $ 2^{b/2} \times 2^{b/2} = 2^b $ 計算步驟，檢查所有可能的對 $ u,v $ . 但是，它實際上可以在 $ 2^{b/2} $ 時間，稍微聰明一點。對於每個頂點 $ v \in T $ ，我們計算路徑的路徑異或 $ v $ 到根 $ T $ . 所有這些值都可以在 $ 2^{b/2} $ 使用由上而下遍歷的步驟 $ T $ . 接下來，我們對所有這些值進行排序或散列，以檢查是否存在一對頂點 $ u,v $ 在此階段收到相同的值。為什麼這行得通？這是因為路徑異或來自 $ u $ 到 $ v $ 當且僅當路徑異或來自 $ u $ 到根的路徑與來自的路徑異或相同 $ v $ 到根。
所以，這給了我們一個獨特的攻擊 $ G $ 執行時間約為 $ 2^{b/2} $ . 事實上，如果你仔細想想，它會讓我們對任何具有以下形式的方案進行攻擊 $ H $ ， 在哪裡 $ H $ 如上。
現在讓我發展分析所有此類方案的理論框架（即，可以表示為 $ H_K $ 如上）。構造圖 $ H $ . 我聲稱這些方案的安全性歸結為該圖的循環結構。
對於熱身，假設不是使用 PRP $ E_K $ ，我們改為使用隨機函式 $ E_K $ . 然後我聲稱：
定理。 $ H $ 是安全的當且僅當圖 $ H $ 沒有循環。更準確地說，有一個明顯的攻擊 $ H $ 要求 $ q $ 查詢當且僅當存在一個長度循環 $ \le q $ 在圖中為 $ H $ .
證明。“如果”部分很簡單：如果有一個長度循環 $ q $ ，然後我們可以在 $ q $ 對應於那些的輸入 $ q $ 邊緣。如果響應異或為零，那麼我們正在處理 $ H $ ; 否則，我們正在處理一個隨機函式。這行得通，因為由於方式 $ H $ 構造時，一個循環中邊緣上的標籤的異或總是保證為零，而當我們與隨機預言機互動時，循環周圍的路徑異或是一個均勻隨機值。
“僅當”部分：假設長度圖中沒有循環 $ \le q $ . 然後讓我們看看任何查詢預言機的攻擊 $ q $ 輸入。這些 $ q $ 輸入對應於 $ q $ 邊，並且假設這些邊之間沒有循環。因此，我們可以建構一個生成樹的森林，它恰好覆蓋每個邊緣一次。
讓我們考慮一個單一的生成樹 $ T $ . 考慮當我們與現實互動時會發生什麼 $ H $ 作為我們的神諭。通過假設，每個頂點上的標籤 $ T $ 是一致隨機的並且獨立於所有其他的。如果我們以自上而下的方式（從根開始）遍歷樹，我們可以看到每條邊上的標籤也是均勻隨機的，並且獨立於所有之前訪問過的邊。因此，邊緣上的標籤是一致隨機且相互獨立的——與我們的預言機與隨機函式互動時獲得的分佈完全相同。由於分佈相同，因此沒有攻擊可以區分這兩種情況。
這可能暗示了尋找一些結構的方向 $ H $ 如果我們可以實例化，那將是安全的 $ E_K $ 作為隨機函式。
不幸的是，這似乎是一個死胡同。當我們只有一個分組密碼時（即，當 $ E_K $ 用 PRP 或隨機雙射實例化），那麼似乎沒有希望：總會有一個複雜的區分攻擊 $ \le 2^{b/2} $ . 如果長度圖中有任何循環 $ \le 2^{b/2} $ ，那麼該方案是不安全的，使用上面的攻擊。另一方面，如果沒有這樣的循環，那麼我們可以使用我描述的攻擊來對付 $ G $ 區分：建構連接的生成樹 $ 2^{b/2} $ 邊，然後使用生日效應檢查生成樹中是否有路徑異或為零的路徑。
所以，據我所知，當 $ E_K $ 通過分組密碼實例化，並且 $ H_K(x)= E_K(f(x)) \oplus E_K(g(x)) $ 在哪裡 $ f,g $ 滿足上述條件，似乎沒有希望超越 $ 2^{b/2} $ 查詢。