“GGM 输出是任意函数,不保证置换或可逆。要构造分组密码模型中的可逆置换,还需例如Feistel/Luby–Rackoff 构造。相反,用 PRF 作为固定长度消息的认证标签,也还需把消息编…”
形式陈述
取正整数半块长
它总可逆,即使
用独立密钥的PRF作轮函数,并按时间顺序执行
下面的渐近结论以半块长
- 三轮构造
是 PRP:只允许对手查询正向置换 - 四轮构造
是强 PRP:对手可自适应查询正向和逆向,两边总查询数计入同一预算
若每轮从随机函数换为 PRF 的优势损失至多
的形式。不同定理版本的常数和运行时间口径可不同;这里明确保留半块长
直觉
一半输入先完整传到输出,另一半只被异或上
可逆并不等于伪随机。前几轮可能保留很强的差分关系,让选择输入的对手识破。允许逆向查询后,对手还能从输出一端把约束倒灌回内部;多一轮是在保护这个更强的接口。
图中交叉线表示半块交换;没有实心圆点的交叉处不连接。
例子与边界
可逆性不依赖轮函数可逆
取二位半块,令
从
两轮的正向攻击
两轮后写
输出为
右半块通常不会保持相同,攻击只需左半块关系。对随机
远小于一。这给出两轮不能成为安全 PRP 的明确区分器。
三轮为什么能保护正向查询
加入第三轮后,输出变成
先把三轮 PRF 通过混合论证替成独立随机函数。对不同正向输入,若内部
严谨的比较可以在一个参考游戏里始终独立抽取输出,并记录“内部
最后,独立随机输出与随机置换输出的差,只在完整
三轮一旦允许逆查询,就能被攻击
还是查询两条同右半块输入
向逆 oracle 提交新密文
三轮内部的
当
推论与应用
四轮定理给输入端和输出端都加上随机掩码层。其证明仍围绕中间两轮的输入、输出半块碰撞展开,但必须统一处理从左端来的正查询和从右端来的逆查询;不能把刚才只适用于正向新输入的懒采样论证原样照搬。[1,2] 本页完整展示了可逆性、三轮正向证明机制和少轮攻击,四轮双向界采用所引定理。
当
参考资料
-
[1] Michael Luby and Charles Rackoff, How to Construct Pseudorandom Permutations from Pseudorandom Functions, SIAM Journal on Computing 17(2), 1988, pp. 373–386。
-
[2] Ben Lynn, Pseudo-Random Permutations, Stanford 密码学笔记,Luby–Rackoff Construction:三轮与四轮的查询接口。本文两轮差分攻击只检查左半块,三轮逆查询攻击逐式推导。
-
[3] David J. Wu, CS 255 Lecture Notes, Theorem 3.7 及其前的 Feistel 逆运算。
-
[4] Dan Boneh and Victor Shoup, A Graduate Course in Applied Cryptography, version 0.6, 2023,§4.5,Theorem 4.9:三轮构造的完整坏事件比较及块空间相对安全参数的增长条件。