返回学习路线

单元终点任务：把安全归约与去随机化预算接起来 ​

任务背景 ​

这一单元的目标不是背出“单向函数可以产生伪随机性”，而是能写出一个构造的输入、输出、观察者接口，以及每一步损失的优势和时间。以下任务同时使用有限小例子和明确的条件性大参数假设；小例子只验证结构，不作为密码安全证据。

主线从硬核位公理库单向函数的硬核谓词Hard-core predicate · Hard-core bit区分整份输入难反演与某一位难预测，定义带公开像的硬核谓词，并证明单向置换加一枚硬核位得到长度加一生成器。与Goldreich–Levin 归约公理库Goldreich–Levin 硬核位定理Goldreich–Levin theorem把随机内积预测器的平均优势转为好输入比例、带独立随机响应的重Fourier列表及原像验证，完整证明通用硬核位的反演归约。进入伸长放大公理库伪随机生成器的伸长放大PRG stretch amplification将长度加一生成器迭代为状态链，用从早到晚替换的混合证明多项式伸长安全，说明最终状态何时能输出及为什么不能与未来输出同时公开。、GGM公理库GGM 伪随机函数构造GGM construction沿长度倍增生成器的二叉树求值，以按需展开和逐层混合证明自适应查询安全，并核算触及节点而非指数全树的代价。和Feistel公理库Feistel 网络与 Luby–Rackoff 定理Feistel network · Luby–Rackoff theorem用Feistel的可逆结构从PRF构造PRP，给出两轮与三轮的区分攻击，解释三轮正向安全和四轮双向安全的不同接口及生日项。。去随机化分支经过小偏空间公理库小偏分布与线性测试Small-bias distribution · Epsilon-biased space以所有非零奇偶测试的偏差定义小偏分布，用有限域多项式构造短种子分布并证明偏差界，区分线性测试保证与密码学安全。、NW 构造公理库Nisan–Wigderson 生成器Nisan–Wigderson generator · NW generator以小交集设计复用种子位，通过下一位预测与固定外部坐标重建困难函数，逐项核算交集真值表造成的电路规模损失。、种子枚举公理库伪随机种子枚举与 BPP 去随机化PRG-based derandomization把固定输入下的随机带判决视为有限规模电路，枚举能欺骗它的对数种子并验证接受概率间隙，分别计算种长、安全资源与生成器求值时间。和IW 定理公理库Impagliazzo–Wigderson 困难性—随机性定理Impagliazzo–Wigderson theorem在E中存在逐充分大长度的指数非一致电路下界这一明确假设下，经局部列表译码式困难性放大、NW设计和种子枚举推出P=BPP，并逐项对齐参数。。

题目 ​

A. 从随机内积预测到原像 ​

假设有预测器 $A$，在均匀 $X,R\in \{0,1{\}}^n$ 上，以至少 $11/20$ 的概率从 $(f(X),R)$ 预测 $⟨X,R⟩$。按正文的相关度定义，把 $c_x\ge 1/20$ 称为好输入。

1. 好输入比例至少多少？
2. 使用失败概率 $1/3$ 的重系数搜索，列表长度上界与反演总成功率下界各是什么？
3. 若 $f$ 非单射，验证器应要求恢复原来的 $X$，还是任意满足 $f(z)=f(X)$ 的 $z$？
4. 解释为什么同一个 $(y,r)$ 的两次预测器调用仍要使用独立随机币

B. 一条密码学构造链 ​

给定一个 $\lambda \to \lambda +1$ 的安全 PRG $G$。假设在覆盖本题全部模拟开销的统一资源预算下，每个单步区分器优势至多 ${ϵ}_0(\lambda )$。

1. 用 $\lambda$ 次状态更新构造 $\lambda \to 2\lambda$ 的生成器，明确最终输出是否包括末状态
2. 用它构造输入长度为 $\lambda$、输出长度为 $\lambda$ 的 GGM PRF，核算 $q$ 次查询的优势损失与底层 $G$ 调用数量级
3. 用三个独立密钥的上述 PRF 构造 Feistel PRP。写出正向 $q$ 次查询的总优势界，并说明若开放逆查询需要改变哪一项构造
4. 若工程报告称“已经公开的末状态后面还可继续安全输出同一链的比特”，给出一个具体区分检验

C. 三轮 Feistel 的逆向攻击 ​

半块为二位，视为整数 $0,1,2,3$。取

$$f_1(r)=r\oplus 1,f_2(r)=r+1(\mathrm{mod}4),f_3(r)=2r(\mathrm{mod}4).$$

先查询明文 $(0,1)$ 和 $(2,1)$，计算两份密文。再按正文三轮攻击构造一个新密文，查询逆像并核对其右半块关系。请同时写明，这不声称上述小函数是安全 PRF。

D. 小偏保证究竟挡住了什么 ​

在 ${\mathbb{F}}_4={\mathbb{F}}_2[\alpha ]/({\alpha }^2+\alpha +1)$ 中，用基 $(1,\alpha )$。均匀取 $A\in {\mathbb{F}}_4$ 和二位向量 $B$，输出

$$Z_i=⟨\mathrm{vec}(A^i),B⟩,i=0,1,2.$$

1. 枚举16个种子产生的输出多重集
2. 计算全部7个非零字符的偏差，说明为什么最大值为 $1/2$
3. 找出一个非线性事件，计算它对该输出分布与三位均匀分布的区分优势
4. 解释该例为什么不能当成密码学 PRG，也没有发生种长压缩

E. NW 接线、反例与真正的去随机化 ​

以 ${\mathbb{F}}_5^2$ 的25个点作种子坐标，给每个次数至多二的多项式 $p$ 一个集合 $S_p=\{(x,p(x)):x\in {\mathbb{F}}_5\}$。

1. 核对集合数、每集大小及最大交集
2. 若片段函数 $f$ 是五位奇偶，比较五条水平线 $p_j(x)=j$ 与五条斜线 $q_j(x)=x+j$。找出它们十个输出之间的恒定线性关系，给出区分优势
3. 现在换成一个真正满足放大后困难性条件的函数。若规模 $M$ 的测试可被误差 $1/M$ 欺骗，种长为 $O(\log M)$，生成器求值时间为 $M^{O(1)}$，说明枚举为什么推出确定性多项式模拟
4. 指出报告“任意普通密码学 PRG，取种长 $\log n$，即可证明 P=BPP”的资源错误

完整解答 ​

A. 把平均优势变成反演成功率 ​

预测优势为 $\epsilon =1/20$，所以平均相关度至少 $2\epsilon =1/10$。若好输入比例为 $p$，

$$\frac{1}{10}\le p+(1-p)\frac{1}{20},$$

故 $p\ge 1/19$。取重系数阈值 $\theta =1/20$，正文的保守列表上界为

$$\frac{2}{{\theta }^2}=800.$$

在好输入上，列表以至少 $2/3$ 的概率包含原 $X$，因此反演总成功率至少为

$$\frac{2}{3}\cdot \frac{1}{19}=\frac{2}{57}.$$

对非单射 $f$，任意通过 $f(z)=y$ 验证的候选都是合法原像。要求回到最初采样的那个 $X$ 会擅自加强单向性任务。

固定像 $y$ 后，平均响应 $g_y(r)=\mathbb{E}(-1{)}^{A(y,r)}$ 是一个实值函数。两次调用独立随机化，才能保证响应乘积的条件期望等于 $g_y(r)g_y(r^{\prime })$；复用随机币可能引入额外相关，破坏前缀质量估计器。

B. 逐层核算，不把同一个ε重复当最终界 ​

记 $G(s)=(L(s),b(s))$。运行 $\lambda$ 轮，释放 $z_1,\dots ,z_{\lambda }$，输出这 $\lambda$ 位加末状态 $s_{\lambda }$，恰得 $2\lambda$ 位。逐轮混合使优势至多 $\lambda {ϵ}_0$。

GGM 的输入长为 $\lambda$，一次查询沿 $\lambda$ 层树求值。每次分支求值使用长度倍增器，而该倍增器内部用 $\lambda$ 次原始 $G$，所以直接求值最多 ${\lambda }^2$ 次原始调用；$q$ 次查询为 $O(q{\lambda }^2)$，缓存共享前缀可能减少实际次数。

GGM 混合最多替换 $q\lambda$ 个倍增器，故优势界为

$$q\lambda \cdot (\lambda {ϵ}_0)=q{\lambda }^2{ϵ}_0.$$

三轮 Feistel 还要替换三个独立轮 PRF，得到

$$3q{\lambda }^2{ϵ}_0+O(q^2/2^{\lambda }).$$

第一项是计算安全归约损失，第二项是理想随机轮函数模型中的碰撞误差。若开放正逆两种查询，三轮本来就有结构性攻击，应改用四轮强 PRP 定理，第一项相应为 $4q{\lambda }^2{ϵ}_0$，并按总查询数重新使用双向安全界。

所有这些界都假设单步 PRG 的安全预算足以覆盖模拟其他调用的时间；不能只写优势乘法而忘记归约运行时间。

若末状态 $s_{\lambda }$ 已公开，又给出 $z_{\lambda +1}=b(s_{\lambda })$，区分器只需自行计算 $G(s_{\lambda })$ 并检查该位。真实输出通过概率一，独立公平位通过概率 $1/2$。

C. 一次实际的三轮逆攻击 ​

对于 $(L,R)=(0,1)$，

$$a=0\oplus f_1(1)=0,b=1\oplus f_2(0)=0,c=a\oplus f_3(b)=0.$$

第一份密文为 $(0,0)$。对 $(2,1)$，

$$a^{\prime }=2,b^{\prime }=1\oplus f_2(2)=2,c^{\prime }=2\oplus f_3(2)=2,$$

第二份密文为 $(2,2)$。取 $\mathrm{\Delta }=0\oplus 2=2$，提交新密文 $(b,c\oplus \mathrm{\Delta })=(0,2)$。

逆算得到 $a^{\ast }=2\oplus f_3(0)=2$，然后

$$R^{\ast }=0\oplus f_2(2)=3,L^{\ast }=2\oplus f_1(3)=0.$$

所以逆像为 $(0,3)$，恰满足

$$R^{\ast }=R\oplus b\oplus b^{\prime }=1\oplus 0\oplus 2=3.$$

这项恒等关系对三轮结构成立，小函数只是让计算可手工完成。随机置换在剩余输入中返回一个指定右半块的机会很小，正是攻击的依据。

D. 四元素域的完整输出分布 ​

16个种子的输出计数为

输出	次数
000	6
100	2
111	2
101	2
011	2
110	2
001、010	0

字符系数顺序与输出坐标 $Z_0,Z_1,Z_2$ 对齐。全部非零字符期望为

字符	001	010	011	100	101	110	111
$\mathbb{E}\chi$	$1/4$	$1/4$	$1/2$	0	$1/4$	$1/4$	$1/2$

因此最大绝对偏差为 $1/2$。其中字符011对应多项式 $t+t^2$，在四元素域里有两个根，所以偏差就是 $2/4$。

事件“输出属于六点支持集”在生成分布中概率一，在三位均匀分布中概率 $6/8$，区分优势为 $1/4$。这也是此例的总变差距离：000的额外质量为 $1/4$，两个未出现点各缺 $1/8$。

种子包含两个域元素/二位向量，共四位，而输出只有三位，未发生伸长。一般的大参数小偏构造可以节省随机位，但仍只保证线性测试，不自动给密码学安全。

E. 设计正确，也可能选错片段函数 ​

二次以下多项式有 $5^3=125$ 个，每集5点；不同多项式之差最多两个根，故交集至多2。这些参数本身成立。

若 $f$ 取奇偶，五条水平线各读取一行网格，彼此不交并覆盖全部25坐标；五条斜线 $x+j$ 同样彼此不交并覆盖全部坐标。因此

$$\underset{j=0}{\overset{4}{⨁}}{G}_{p_j}(z)=\underset{v\in {\mathbb{F}}_5^2}{⨁}{z}_v=\underset{j=0}{\overset{4}{⨁}}{G}_{q_j}(z).$$

左右涉及不同的十条曲线，产生一个恒定线性关系。真实输出总满足，独立均匀的125位输出以概率 $1/2$ 满足，区分优势为 $1/2$。NW 设计不能代替片段函数的平均困难性。

在真正满足条件的情形，若种长 $d=O(\log M)$，则种子数为 $2^d=M^{O(1)}$；每个种子展开和算法执行又是多项式，总时间仍多项式。误差 $1/M$ 在充分大 $M$ 时小于 $1/12$，把 BPP 的 $2/3$ 与 $1/3$ 两端分别留在 $1/2$ 的两侧。取 $M=\mathrm{poly}(n)$，即得到关于原输入长 $n$ 的确定性多项式模拟。

普通密码学 PRG 若种长 $k=\log n$，其通常定义只抵抗 $\mathrm{poly}(k)$ 时间攻击者；待模拟算法却可能花 $n^{10}=2^{10k}$ 时间。缺失的是这个指数资源范围内的伪随机保证，不能靠枚举动作补出来。

验收标准 ​

• 归约始终对齐输入分布、秘密与公开量；GL最后执行原像验证
• 每个优势损失同时写出调用次数与模拟时间，未把 ${ϵ}_0$ 当作最终优势
• 三轮PRP与四轮强PRP的oracle权限没有混用
• 能实际运行GGM路径与Feistel正逆运算，且不把玩具函数称为安全实例
• 小偏的字符偏差、事件区分优势和种长三个数分别计算
• NW同时具备设计与平均困难函数；P=BPP仍保留充分大长度的指数电路下界假设

下载 Python 复算脚本。脚本只使用标准库，枚举有限例子并核对式子；它不证明任何密码学困难性假设。