Block-Cipher
廣義 Feistel 的 Luby-Rackoff 定理
我正在從各種來源閱讀 Luby-Rackoff 定理：[ 1 ]、[ 2 ]、[ 3 ]，這表明您至少需要 3 輪 $ 2 $ -branch Feistel 網路以獲取 PRP，如果基礎 $ f $ 函式是一個 PRF。我還了解了具有兩個以上分支的廣義 Feistel 網路。
從廣義上獲得 PRP 的最少輪數是多少 $ n~(>2) $ 分支Feistel網路，給定底層函式 $ f $ 是PRF？
正如您可能在連結的參考資料中看到的那樣，有多種“基本”廣義 Feistel 網路：Type-1、Type-2 和 Type-3。據我所知，所有這些都是由 Zheng、Matsumoto 和 Imai 在 CRYPTO'89 在*“關於可證明安全且不依賴任何未經證實的假設的塊密碼的構造”中介紹的*。
假設您的狀態分為 $ k $ 塊，那麼上面的論文實際上證明/聲稱這些廣義 Feistel 結構的安全性（所有輪次中使用的每個 PRF 並且每輪的所有狀態部分都是獨立的）：
- 對於 Type-1，安全性經過驗證 $ 2k-1 $ 回合
- 對於 Type-2，安全性經過驗證 $ k+1 $ 回合
- 對於 Type-3，安全性經過驗證 $ k+1 $ 回合
該論文還證明/聲稱這些輪數實際上是最小的。
供大家參考，以下是三種基本類型的精美圖形：圖片來源
可以清楚地看到，前兩種類型是第三種類型的“特殊情況”，其中某些 PRF 呼叫和 XORing 選擇被刪除。該論文確實提供了對在以某些模式丟棄這些時保持安全性的輪數的進一步分析
