Feistel 網路的 F 函式的 PRP 與 PRF
Feistel 網路通常使用 PRF 來定義其 F 函式，但也使用了 PRP。使用 PRP 而不是 PRF 的理論密碼學含義是什麼？它會影響 Luby 和 Rackoff 對具有理想 F 函式的 3 輪和 4 輪 Feistel 網路的觀察嗎？
它會影響 Luby 和 Rackoff 對具有理想 F 函式的 3 輪和 4 輪 Feistel 網路的觀察嗎？
不。
使用 PRP 而不是 PRF 的理論密碼學含義是什麼？
基於 F 的 PRF-Security，
我們對 Luby-Rackoff 的安全性有一個界限。我們對 PRP 的 PRF-security 有一個界限（“PRP/PRF-Switching-Lemma”）。
我們可以簡單地將一個插入另一個得到我們的答案！
所以，首先是切換引理：
讓 $ E:\mathbb K\times \mathbb X\to\mathbb X $ 是一個排列族和 $ N:=|\mathbb X $ |。進一步讓 $ \mathcal A $ 成為對抗 PRF 安全的有效對手 $ E $ 製造 $ q $ 查詢。那麼存在一個對手 $ \mathcal B $ 這樣$$ \mathbf{Adv}^{\text{PRF}}_E(\mathcal A)\leq \mathbf{Adv}_E^{\text{PRP}}(\mathcal B)+\frac{q^2}{2N}. $$
現在是 Luby-Rackoff-Bound（三輪）：
讓 $ F:\mathbb K\times \mathbb X\to\mathbb X $ 是一個函式族 $ N:=|\mathbb X| $ . 進一步讓 $ \mathcal A $ 成為對抗 PRP 安全性的有效對手 $ \operatorname{LR}(F) $ 製造 $ q $ 查詢，則存在對手 $ \mathcal B $ 這樣 $$ \mathbf{Adv}^{\text{PRP}}{\operatorname{LR}(F)}(\mathcal A)\leq 3\cdot \mathbf{Adv}{F}^{\text{PRF}}(\mathcal B)+\frac{q^2}{N}+\frac{q^2}{N^2}. $$
現在終於合併了：
$$ \mathbf{Adv}^{\text{PRP}}_{\operatorname{LR}(E)}(\mathcal A)\leq 3\cdot \mathbf{Adv}^{\text{PRP}}_E(\mathcal B)+\frac{3q^2}{2N}+\frac{q^2}{N}+\frac{q^2}{N^2} $$
如您所見，這裡沒有任何實質性變化。
切換引理和 luby-rackhoff 界可以例如在Boneh-Shoup 書中找到。