动机
一个概念类即使由可高效求值的函数组成,也可能无法被高效学习。求值时掌握秘密密钥;学习时密钥隐藏,学习器只能看到样本。伪随机函数形式化了一种特别强的差异:不知道密钥时,即使算法能选择多项式数量的输入,也无法可靠地区分带密钥函数与均匀随机函数。
如果高效 PAC 学习器能从随机样本预测这种族中的每个函数,其预测器在带密钥函数和随机函数上的表现便会不同。这一差异可以转化成预言机区分器。论证依赖明确的伪随机函数假设:它既不证明无条件计算困难性,也不声称每个密码构造都难以学习。
两个计算模型
定义 10.1.1
(可高效计算的伪随机函数族)
对每个安全参数 ,令 ,密钥从 均匀选取,其中 为多项式。该族由确定性函数
组成,并由同一个算法在关于 的多项式时间内计算。预言机区分器 接收 ,可自适应地选择输入并查询函数,最后输出一个比特。若其包括预言机调用在内的运行时间关于 为多项式,则称它为概率多项式时间区分器。
若对每个这样的 ,以下两个实验中输出一的概率之差的绝对值关于 可忽略,则称该族伪随机:
- 带密钥实验:抽取一个均匀密钥 ,每次查询都使用同一个函数 回答。
- 随机函数实验:均匀抽取一个函数 ,每次查询都使用同一个 回答。
非负函数 可忽略,指对每个正多项式 ,充分大的 均满足 。在随机函数实验中,不同输入处的值是独立公平比特,但重复输入会重复此前答案。等价地,可以只在某输入第一次被查询时赋予新的公平比特,并保存该值。
随机函数是理想预言机,不是交给区分器的多项式大小表格。对于多项式次数的调用,可以按需生成并保存答案。不可区分性假设量化所有自适应区分器,其访问方式比随机有标签样本更强。下文归约只使用独立均匀抽取的查询点,所以仅对多项式个此类随机查询的安全性也已足以产生矛盾。每个实验中密钥或随机函数只抽取一次,而非每次查询重新抽取。
定义 10.1.2
(高效的无分布假设 PAC 学习)
令 。无分布假设 PAC 学习器接收 、精度和失败参数 ,并能取得独立有标签样本 ,其中 是 上任意分布,目标 。它输出二元假设 ,满足
“高效”要求对所有输入及随机选择的最坏情况运行时间与请求样本数关于 为多项式,并要求输出表示能够在多项式时间内求值。学习器不必输出 中的成员:允许非恰当假设。
外层概率针对训练数据和学习器随机性,内层概率是所得假设的总体误差。保证必须对每个目标和每个输入分布成立。证明只使用均匀分布,所以实际上也排除了只需满足这个固定均匀分布上保证的高效学习器;学习器可以知道该分布。
归约定理
引理 10.1.3
(随机函数的新点测试界)
令 均匀随机。一个算法至多进行 次预言机查询,查询可自适应且允许重复,并根据记录和随机性产生可高效求值的二元预测器 。之后独立均匀抽取 ,其预测与 一致的概率至多为
这是信息界,去掉高效性要求仍成立。证明是对记录取条件:未查询处的随机函数值仍是独立公平比特,而 落在至多 个已查询点的概率至多为 。
定理 10.1.4
(伪随机性排除高效学习器)
假设上述二元函数族对每个概率多项式时间预言机区分器都是伪随机的。则在上述模型中,不存在该 的高效无分布假设 PAC 学习器。事实上,即使学习器只需满足均匀分布下的 PAC 保证、且允许输出类外可高效求值的假设,这样的学习器也不存在。
这是有条件的蕴含。它不声称只要密钥隐藏,某个具体带密钥算法就伪随机,也不无条件地建立所假设的函数族存在。
构造区分器
证明
(训练后在独立点测试)
假设这样的学习器 存在。固定 后,其运行时间和样本数在所有输入及随机选择下都由某个多项式 控制。区分器 能访问未知预言机 ,它不是 就是 。
每当 请求一个有标签样本, 就独立均匀抽取 ,查询 并返回 。这些输入独立抽取,但可以重复。当 输出可高效求值的假设 后,区分器再独立均匀抽取一点 、查询 ,并且仅在 时输出一。整个模拟包括这个求值和预言机调用,都在概率多项式时间内完成。
在带密钥实验中,先固定任意密钥 。模拟数据是由 标记的独立均匀样本,所以 PAC 保证适用。所得假设以至少 的概率在均匀分布下具有至多 的误差。给定这样的假设,独立测试点以至少 的概率被正确标记。因此
此下界对每个密钥都成立,然后才对随机密钥取平均。未满足 PAC 保证的训练运行,其接受概率非负;无需额外假设。
在随机函数实验中,令 为训练输入中不同点的集合。给定训练记录和学习器随机性后, 和 都固定。若 , 是新的独立公平比特,条件匹配概率恰为 ;若 ,匹配概率可能达到一。因为 且 独立均匀,
所以
区分器的优势至少为 。因为 是多项式,充分大的 均满足 ,因此优势至少为 。一个最终始终不小于 的量不可忽略,这与伪随机性矛盾,定理得证。
证明透视
碰撞项是归约的一部分
真正的随机函数会记住某个输入处的答案。只有测试输入未在训练中出现时,测试标签才是新的独立公平比特。有限定义域上必须估计碰撞概率,比较才有效。带密钥情形使用 PAC 泛化;随机函数情形使用新输入处的独立性;假设能高效求值则保证所得区分器是多项式时间的。
样本数不必恰好为 。即使学习器根据此前样本决定何时停止,其调用次数仍至多为此多项式上界,而测试点在训练后才抽取。对完整记录取条件概率得到相同估计。无需要求所有训练输入互异:重复训练点只会使 变小。
例题
例题 10.1.5
(有限定义域上的优势计算)
设 ,学习器至多请求 个样本。归约中随机函数的接受概率至多为
带密钥实验的接受概率至少为 ,因此差至少约为 。这些是界,不是精确接受概率。渐近矛盾使用的是对所有充分大 均成立的多项式 ,而非单一数值参数。
例题 10.1.6
(为什么同一个随机函数必须记住答案)
在两点定义域 上,设一个训练输入和一个独立测试输入都均匀抽取。预测器记住所观察标签:如果测试输入重复便使用它,否则公平随机猜测。测试发生碰撞的概率为 ,所以它与均匀随机函数一致的概率为
若把每个测试标签都称为独立公平比特,就会错误地得到 。一般界在此也给出 。当 增大而样本数为多项式时,碰撞项趋零,但有限 时它并非恒为零。
例题 10.1.7
(归约不要求假设属于原类)
学习器可能输出一个电路,它不等于任何密钥 所对应的 。区分器仍可在 求该电路的值并与预言机比较。证明只使用 PAC 误差保证及高效求值,从不要求恢复密钥。因此矛盾不需要破解秘密密钥;能预测新输入便已足够。
反例模式
密钥隐藏本身不保证伪随机性
令 ,其中 。该函数可高效计算且密钥隐藏,但对每个密钥都有 。区分器查询一次 ,若答案为零便输出一。在带密钥实验中接受概率为一,在均匀随机函数实验中为 ,优势为 。该函数族不满足所述伪随机性假设;该奇偶族也可从均匀有标签样本通过二元线性代数高效学习;这不与定理矛盾,因为该族不满足伪随机假设。秘密参数本身不是安全证明。
常见错误
常见错误
(对重复输入把随机函数换成独立标签)
随机函数在此前未见过的输入上给出独立公平标签,但对重复输入不会如此。应考虑碰撞事件,或者有意从训练集之外抽取测试点并分析分布变化。上面的证明保持测试点均匀,并明确计入碰撞项。
常见错误
(夸大有条件归约的结论)
结论假设存在高效可计算且满足预言机伪随机性的函数族,并不无条件地证明这样的族存在,也不保证某个具体实现安全。它还依赖学习器的输出可高效求值:否则所构造的区分器未必在多项式时间内运行。
总结
若能在均匀分布下 PAC 预测每个带密钥函数,就可以用一个新的随机测试输入区分伪随机函数与真正随机函数。带密钥实验中预测经常成功;随机函数在未见过的点不可预测,有限定义域上的碰撞概率由显式项控制。因此预言机伪随机性在所述模型下有条件地排除高效学习,即使允许非恰当假设也如此。
练习
快速检查
(在随机函数实验中,令 ,训练样本至多 个。用证明中的界估计单点测试接受的概率。)
使用界 。
解答 · 答案
证明给出 。实际值取决于学习器及训练输入是否重复;该表达式是上界。
快速检查
(将归约中的参数改为 、。给出带密钥实验接受概率的下界,以及用 表示的区分优势下界。)
把假设良好的概率乘以测试点被正确标记的概率。
解答 · 答案
带密钥接受概率至少为 ,随机函数接受概率至多为 ,故优势至少为 。若 是多项式,则充分大的 使该界为正且不可忽略。
快速检查
(某模拟器对重复的预言机查询每次都回答一个新的独立公平比特。给出一个两次查询的区分器,说明这不是随机函数实验。)
随机函数会记住它的答案。
解答 · 答案
对同一输入查询两次;若两次回答相同则输出一。对同一个随机函数,答案总相同;对每次重新生成的独立公平比特,相同概率为 ,两种接受概率之差为 。
快速检查
(对带密钥奇偶族 ,计算零输入区分器的一次查询优势,并解释它违反了什么假设。)
在 处计算每个带密钥函数的值。
解答 · 答案
带密钥函数在 的答案恒为零,而随机函数在该点的值是公平比特。答案为零时接受,得到接受概率一与 ,故优势为 。此族对所允许的预言机区分器不伪随机。