形式陈述
设 , 是单向函数理路单向函数One-way function易于正向计算,但随机输入所产生的像难以被任何高效算法反演的函数族。,并采用同一安全参数 下的统一概率多项式时间对手。下文省略的 输入均包含 。对独立均匀的 ,定义
Goldreich–Levin 定理说 是 的硬核谓词理路单向函数的硬核谓词Hard-core predicate · Hard-core bit区分整份输入难反演与某一位难预测,定义带公开像的硬核谓词,并证明单向置换加一枚硬核位得到长度加一生成器。,这里该定义的输入长度取 ,安全参数仍为 :给出 和公开随机向量 ,仍不能以不可忽略优势预测随机内积。[1]
一个定量归约足以看清结论。假设预测器 满足
给定一个有效下界 ,可构造在 及 的运行时间上为多项式的反演器,以至少 的概率找到 的某个原像。这里并不要求它找回生成该像时选用的唯一原输入;若 不是单射,任何通过验证的原像都算成功。
例子与边界
第一步:平均优势不能只属于极少数输入
固定 ,令它的预测相关度为
它等于该 上预测成功率的两倍减一,取值于 。总成功率假设给出 。
称 的输入为好输入,比例记为 。不好输入的相关度小于 ,好输入最多为一,因此
这一步保证反演器有至少逆多项式比例的机会遇到可恢复输入。只证明“某个输入可恢复”不足以反驳平均情形单向性。
第二步:固定像后,预测器提供一个有噪声的函数接口
反演器收到 ,不知 。对任意自行选择的 ,它可以重新运行公开算法 。定义理论上的平均响应函数
它不需要被精确计算;每次运行 就得到一个取值为 、期望为 的独立样本。其Fourier 系数理路Fourier–Walsh 展开与影响度Fourier-Walsh expansion · Boolean Fourier analysis在均匀布尔立方体上用字符正交基展开函数,把方差和坐标影响写成 Fourier 系数的平方和。为
对真实隐藏输入 ,有 。如果 好,这个系数至少为 。
这里不能固定一份会在不同 上造成未知相关性的噪声表,再假装已有精确成员查询。每次调用 使用新的独立随机币,才得到下面需要的乘积无偏性。
第三步:复用重系数搜索,生成短候选表
已有 KM 搜索页证明了以 为阈值找到所有重系数的前缀质量算法。它在此只需一个明确扩展:把确定的 Boolean 函数换成 ,并用独立随机响应查询。
Parseval 给出 ,所以重系数仍至多 个。对共享后缀的两次成员查询,独立响应 满足
于是 KM 的前缀质量估计器仍然无偏,取值仍在 ,原来的集中界、剪枝余量与节点上限原样适用。这核对了接口,不必重新发明一套频谱搜索。
取 、失败概率 。得到的列表 包含全部 的位置,并且可以用该页的保守实现,在
次预测器调用内完成,列表规模至多 。在所有估计准确的事件上,每个好输入 都在列表中。上述次数计的是 调用;总运行时间还要乘每次调用成本并加上记录前缀的多项式工作。
第四步:列表方向必须变成可验证原像
反演器依次计算 ,只要 且 就输出。错误候选不会通过验证;若其中有别的有效原像,输出它同样成功。对好输入,列表以至少 的概率包含真实 ,所以由式 (1),总反演成功率至少 。
若预测优势在无穷多个长度上至少为某个逆多项式,可用该逆多项式作搜索阈值,在这些长度上得到不可忽略反演概率,违反单向性。无需假装反演器事先知道实际每一长度的精确优势。
一个小编码例子
取 ,按 排列,内积位为
它不是某个固定坐标,而是所有坐标按公开 选择后的奇偶。若平均响应函数为
则 ,可通过随机返回 的概率 实现。真实方向 的相关度为 ,对应预测成功率 。搜索可能还留下 这个相关方向;只有最后的 验证才把“有相关”与“是有效原像”区分开。这个三位例子演示接口,不提供小参数密码安全。