如何從分組密碼構造一個好的 PRF？

我們想顯式地構造一個好的（如下暫定定義的）偽隨機函式 $ F $ 和 $ b $ -位輸入和輸出，來自（最好只是）一個偽隨機排列 $ E $ 的 $ b $ -bit，由 TDEA 在實踐中為 $ b=64 $ 或 AES-256 $ b=128 $ ，以及一個固定的隨機密鑰。

我暫時將一個好的PRF 定義為與隨機函式無法區分（具有小的常數優勢），假設 $ 2^{b(1-\epsilon)} $ 對執行我們建構的預言機的查詢 $ F $ 從 $ E $ ，並委託呼叫 $ E $ （編輯：並且除了 $ E^{-1} $ 如果有幫助）到一個隨機的預言機。根據需要修復此定義（更新：我被告知 $ \epsilon<1/2 $ ，這大致就是所謂的PRF 超出了生日限制的安全性）。

有沒有簡單的結構 $ F $ 從 $ E $ 有安全論據？

$ F(x)=E(x) $ 是完全不適合的：它可以通過在之後檢測碰撞來與隨機函式區分開來 $ 2^{b/2} $ 不同的查詢，對於隨機函式，這種情況以相當大的機率發生，但對於隨機排列則不然。這甚至可以通過使用Floyd 的循環查找來通過恆定記憶來完成。也可以建立一個區分器 $ F(x)=E(x)\oplus x $ .

現在我找不到區分 $ F(x)=E(E(x)\oplus x) $ ，但這甚至不是一個弱安全論點。更新：如果它的安全性無法證明，我仍然對區分攻擊感興趣，以便了解在實踐中可能是多麼不安全。

我同意 David Cash 的觀點，即您正在尋找的是一種具有“超出生日限制”安全性的 PRF 結構。關於這個主題已經有各種各樣的工作。

Stefan Lucks 分析了幾個簡單的結構：

• 和 $ ^2 $ ： 這裡 $ F_{K,K’}(x) = E_K(x) \oplus E_{K’}(x) $ . 這具有高達大約的安全性 $ 2^{2b/3} $ 查詢，這比瑣碎的構造要好。
• 和 $ ^d $ : 這是明顯的概括： $ F_{K_1,\dots,K_d}(x) = E_{K_1}(x) \oplus \dots \oplus E_{K_d}(x) $ . 這具有高達大約的安全性 $ 2^{db/(d+1)} $ 查詢。
• 雙胞胎 $ ^2 $ ： 這裡 $ F_K(x) = E_K(x||0) \oplus E_K(x||1) $ （與大衛現金提到的相同結構）。這具有高達大約的安全性 $ 2^{2b/3} $ 查詢。
• 雙胞胎 $ ^d $ ： 這裡 $ F_K(x) = E_K(dx+0) \oplus E_K(dx+1) \oplus \dots \oplus E_K(dx+d-1) $ , 我們考慮 $ 0 \le x <2^b/d $ . 這具有高達大約的安全性 $ 2^{db/(d+1)} $ 查詢。

這是論文：

• PRP 的總和是一個安全的 PRF，Stefan Lucks。歐洲加密貨幣 2000。

我認為關於這個主題還有更多的工作要做。

引用自：https://crypto.stackexchange.com/questions/5447