Feistel 网络与 Luby–Rackoff 定理

一半输入先完整传到输出，另一半只被异或上 $f$ 的值，因此解密时总能找回计算 $f$ 所需的那一半。这是可逆性的来源，而不是靠求 $f^{-1}$。

可逆并不等于伪随机。前几轮可能保留很强的差分关系，让选择输入的对手识破。允许逆向查询后，对手还能从输出一端把约束倒灌回内部；多一轮是在保护这个更强的接口。

图中交叉线表示半块交换；没有实心圆点的交叉处不连接。

可逆性不依赖轮函数可逆 ​

取二位半块，令 $f_1$ 恒为 $01$、$f_2(x)=x$、$f_3$ 恒为 $10$。输入 $(L,R)=(11,01)$ 的三轮状态为

从 $(11,00)$ 开始，按式 (1) 用 $f_3,f_2,f_1$ 逆序恢复，依次得到 $(10,11)$、$(01,10)$、$(11,01)$。其中两个轮函数是常数，仍不影响可逆性；它们当然不是安全 PRF，这个算例只检查线路与逆运算。

两轮的正向攻击 ​

两轮后写

输出为 $(a,b)$。查询 $(L,R)$ 与 $(L\oplus \mathrm{\Delta },R)$，其中 $\mathrm{\Delta }\ne 0$。两个输出的左半块必满足

右半块通常不会保持相同，攻击只需左半块关系。对随机 $2n$ 位置换，第二个输出必须避开第一个输出；其左半块满足这个指定非零差的概率为

远小于一。这给出两轮不能成为安全 PRP 的明确区分器。

三轮为什么能保护正向查询 ​

加入第三轮后，输出变成

先把三轮 PRF 通过混合论证公理库混合论证Hybrid argument在一串相邻实验间逐步替换组件并累加不可区分优势的证明方法。替成独立随机函数。对不同正向输入，若内部 $a$ 从未重复、输出左半 $b$ 也从未重复，那么每次访问 $f_2(a)$、$f_3(b)$ 都命中一个新位置。懒采样可使新 $(b,c)$ 像独立均匀输出。

严谨的比较可以在一个参考游戏里始终独立抽取输出，并记录“内部 $a$ 碰撞”或“$b$ 碰撞”这两类坏事件；到首次坏事件前，两个游戏的 transcript 一致。参考游戏中输出不依赖隐藏的 $f_1$ 表。对两次相同 $R$、不同 $L$ 的输入，$a$ 不可能碰撞；对不同 $R$ 的输入，隐藏随机掩码让碰撞概率为 $2^{-n}$。独立输出的 $b$ 碰撞也为 $2^{-n}$。用并集界公理库并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。，坏事件概率至多 $2(\genfrac{}{}{0ex}{}{q}{2})/2^n$。

最后，独立随机输出与随机置换输出的差，只在完整 $2n$ 位输出碰撞时出现，概率至多 $(\genfrac{}{}{0ex}{}{q}{2})/2^{2n}$。两项合起来给出三轮正向接口的 $O(q^2/2^n)$ 信息论误差，再加三次 PRF 替换损失。重复输入用缓存回答，不算新随机位置。

三轮一旦允许逆查询，就能被攻击 ​

还是查询两条同右半块输入 $(L,R)$、$(L^{\prime },R)$，令 $\mathrm{\Delta }=L\oplus L^{\prime }\ne 0$，得到 $(b,c)$、$(b^{\prime },c^{\prime })$。若 $b=b^{\prime }$，本轮攻击可放弃；这个事件本身在随机轮函数模型下很少发生。

向逆 oracle 提交新密文

三轮内部的 $a^{\prime }=a\oplus \mathrm{\Delta }$。逆算第一步得到的中间值正是 $a^{\prime }$，所以返回明文的右半块必为

当 $b\ne b^{\prime }$，该密文不同于两次已经查询的密文。对随机置换，新的逆像在剩余 $2^{2n}-2$ 个输入中均匀；恰满足式 (2) 指定右半块的概率至多 $2^n/(2^{2n}-2)$。这说明三轮的正向安全并不能升级成强 PRP 安全。

四轮定理给输入端和输出端都加上随机掩码层。其证明仍围绕中间两轮的输入、输出半块碰撞展开，但必须统一处理从左端来的正查询和从右端来的逆查询；不能把刚才只适用于正向新输入的懒采样论证原样照搬。[1,2] 本页完整展示了可逆性、三轮正向证明机制和少轮攻击，四轮双向界采用所引定理。

当 $q$ 接近 $2^{n/2}$ 时，上述半块生日项不再小；这一具体保证不会因完整块长是 $2n$ 而自动延伸到 $2^n$ 次查询。分组密码公理库分组密码Block cipher由密钥索引、作用于固定长度分组且可高效求逆的置换族；消息级保密与认证还取决于工作模式。作为消息加密组件时，还要选择正确模式、nonce 规则和认证机制；PRP 或强 PRP 定义本身都不等于完整消息级加密安全。