4.2 框架¶

• 让我们回到之前例子中对硬核函数的研究。第二个例子展示了如何证明函数$b$对于$f$不是硬核的——在给定$f(x)$的情况下计算出$b(x)$。另外第一个例子展示了如何证明函数$b$对于$f$来说是硬核的——如果能够计算$b(x)$，那么说明$f$是可逆的。数学上可以用反证法来证明：给定$f(x)$和某个能够计算$b(x)$的算法，观察其如何计算的到$x$，如果$f$是单向函数，那么这便是矛盾的，所以不存在这样的算法，因此$b$是硬核的。关键点在于如何将计算$x$归约成计算$b(x)$。由于关于单向函数的问题目前还没有解答，在实践中我们考虑单向函数的替代者，因此对于这种归约的得宜的解释是计算$b$并不比逆推$f$要简单。显然这句话反过来说也是成立的，所以我们说计算$b$和逆推$f$是一样难的。

• 预言机(Oracles) 为了将重点投到归约上，通常考虑有一个预言机能够提供出$x$的部分信息，记为$b(x)$。这种进一步的抽象$b(x)$的计算的好处是它统一对归约的不同研究的场景。除了本研究的理论方面，它的同样被应用到侧信道攻击(side-channel attacks)中，比如如果具有和$x$有关系的部分信息，那么就可能从中计算得到$x$。每个比特安全研究的副产品之一是这些归约能够用于实际目的，我们稍后会提到它。总的来说，我们使用预言机来模拟获取部分信息的不同情况，而不是具体的某种情况。

• 交互(interaction) 回到本章的开头部分，显然我们可以得到给定的$b(x)$部分信息。当然这不足以让我们知道$x$本身因为有很多不同的值也有着相同的部分信息。例如，我们知道$x$是奇数，这可以将可能值减少一半，但$x$依然还有很多可能值，因此需要和预言机进行交互。此外这些交互必须遵循一些代数关系，因次对于随机的$y$得到的$b(y)$来说，并不能从中得到关于$x$的任何信息。构成这些交互中的代数关系非常有价值，将会在后续章节重点介绍。

• 成功率(Success Probability) 不能认定算法总是可以得到$b(x)$，更通俗地说，不能假设预言机总是给出正确的$b(x)$值。总是给出正确的值的预言机我们称之为完美(perfect)预言机，有时无法给出正确值（或任何内容）的称之为不完美(imperfect)或不可靠(unreliable)预言机。当函数$b$只有几个位时，猜测$b(x)$的值都有不错的成功率，当然这肯定不是恢复$x$的好办法，优点是关于通过猜测的方法有概率计算出$b(x)$。预言机的优点反映了一个预言机能够被认定有多强。从比特安全角度考虑，处理成功率低的预言机的归约被认为是一个强结果。本文提出了两个极端观点：要么预言机是完美的，要么他们仅仅只比猜测的方法有着优势。