Feistel-Network
3輪Feistel足以製作PRP嗎？
我知道一輪 Feistel 不足以製作 PRP（偽隨機排列）。我也知道兩輪是不夠的。三輪Feistel怎麼樣？
我在這個主題上做了很多閱讀，但沒有幫助。例如，這裡他們說由於 Luby-Rackoff 定理，我們在三輪後有一個 PRP，但這裡說這還不夠。
它是哪一個？
我們將考慮一個對稱的Feistel密碼 $ n $ 位塊在每一輪使用理想的獨立隨機函式。
使其在計算上與隨機排列無法區分需要一些輪數，具體取決於攻擊模型；如果我們滿足於漸近安全 $ O(2^{n/2}) $ 工作，或者想要更多工作的漸近安全，或者想要規定的小安全 $ n $ .
漸近安全的經典結果 $ O(2^{n/2}) $ 工作：
- 在隨機已知明文下，我們需要 2 輪；
- 在選定的明文下（即假設一個加密預言機，即所謂的弱 PRP的標準），我們需要 3 輪；參見 Michael Luby 和 Charles Rackoff 的著名作品，How to Construct Pseudo-random Permutations from Pseudo-random Functions（在SIAM Journal on Computing Vol. 17, No. 2, 1988中，最初發表於Crypto 1985）；
- 在選定的明文和密文下（即另外假設一個解密預言機，即所謂的強 PRP的標準），我們需要 4 輪；要證明 3 輪還不夠，請參閱此答案。
這些經典的結果很好，並且相對容易建立，但不能直接應用在通常的實踐中。第一的， $ O(2^{n/2}) $ 建議對於 128 位安全性（目前基線），我們需要一個 256 位分組密碼（這是不常見的：128 位是主流，64 位曾經是）。此外，假設每一輪的理想獨立隨機函式，但實際輪函式與此相去甚遠。
對於漸近安全，事情更複雜（需要更多輪次），需要更多工作；請參閱 Jacques Patarin在Crypto 2004 程序中的5 輪或更多輪隨機 Feistel 方案的安全性，或他更早的Luby-Rackoff: 7 Rounds are Enough for $ 2^{n(1−\epsilon)} $ 安全性，在Crypto 2003 的程序中。
規定的小程序需要更多輪次 $ n $ ，據我所知，我們只有啟發式方法。