单向函数与单向函数族的硬核谓词

【引入】

单向函数 $f$ 的含义是：给定 $y=f(x)$，想要找到 $y$ 在 $f$ 下的某个原像 $x$ 是计算上困难的。

但是，这并不意味着给定 $f(x)$ 后，关于 $x$ 的所有部分信息都难以获得，即单向性只保证整体反演困难，不保证原像的每一部分信息都被隐藏。

例如，给定一个单向函数 $f$，可以构造函数：

$$g(x,r)\stackrel{\mathrm{def}}{=}(f(x),r)$$

其中 $|x|=|r|$。显然，$g$ 仍然包含 $f(x)$ 的单向性部分，但它直接暴露了 $r$。虽然从 $g(x,r)$ 中恢复完整的 $(x,r)$ 仍然困难，但其中的 $r$ 是完全公开的。因此，单向函数本身并不一定隐藏其原像的部分信息，这限制了它在安全加密等任务中的直接应用。

为了解决这个问题，需要研究一种特殊的部分信息：它本身可以由原像 $x$ 高效计算出来，但仅凭 $f(x)$ 却无法有效预测。

【单向函数的硬核谓词】

基本定义

设 $b:\{0,1\}^{*}\to\{0,1\}$ 是一个多项式时间可计算的谓词。若对任意概率多项式时间算法 $A’$、任意正多项式 $\mathrm{poly}(\cdot)$，以及所有充分大的 $n$，都有：

$$P[A'(f(U_n))=b(U_n)]<\frac{1}{2}+\frac{1}{\mathrm{poly}(n)}$$

则称 $b$ 是函数 $f$ 的硬核谓词（Hard-Core Predicate）。其中，$U_n$ 表示在 $\{0,1\}^n$ 上均匀随机选取的输入。

直观来说，硬核谓词就是反演困难性的核心部分：$b(x)$ 只是关于 $x$ 的一个比特信息，即使攻击者拿到了 $f(x)$，也无法以显著优于 $\frac{1}{2}$ 的概率预测 $b(x)$，即攻击者最多只能做到接近随机猜测。

这里的关键不是完全不能猜中，而是不能比随机猜测好一个非可忽略量。

概率基准

由于 $b(x)$ 是一个比特，所以即使完全不知道 $b(x)$，也可以随机输出 $0$ 或 $1$。这种算法的成功概率就是：

$$\frac{1}{2}$$

因此，硬核谓词要求的是：任何高效算法都不能把成功概率提高到 $\frac{1}{2}$ 加非可忽略量，即只允许成功概率比 $\frac{1}{2}$ 高出可忽略量。

此外，如果 $b$ 是某个函数的硬核谓词，那么 $b(U_n)$ 本身必须几乎是无偏的，即：

$$|P[b(U_n)=0]-P[b(U_n)=1]|$$

必须是关于 $n$ 的可忽略函数。

这是因为，如果 $b(U_n)$ 明显偏向 $0$ 或明显偏向 $1$，那么攻击者即使完全不看输入，也可以总是输出概率更大的那个值，从而以显著优于 $\frac{1}{2}$ 的概率猜中 $b(U_n)$。

信息丢失与计算困难

硬核谓词 $b$ 本身是多项式时间可计算的，即如果知道原像 $x$，那么计算 $b(x)$ 是容易的。

因此，给定 $f(x)$ 后无法预测 $b(x)$，可能有两种原因：

1. 信息论原因：函数 $f$ 本身丢失了关于 $x$ 的信息
2. 计算复杂性原因：函数 $f$ 没有丢失信息，但反演 $f$ 在计算上困难

下面以信息丢失导致硬核谓词为例。设输入可写为 $\sigma\alpha$，其中 $\sigma\in\{0,1\},\alpha\in\{0,1\}^{*}$，定义：

$$b(\sigma\alpha)=\sigma,\quad f(\sigma\alpha)\stackrel{\mathrm{def}}{=}0\alpha$$

函数 $f$ 直接丢掉了输入的第一位 $\sigma$，并把它改成 $0$。因此，从 $f(\sigma\alpha)$ 中根本无法恢复 $\sigma$，所以 $b(\sigma\alpha)=\sigma$ 对于 $f$ 来说是硬核的。

这个例子中的困难不是计算困难，而是因为 $f$ 真的丢失了信息。

在密码学中，更关心的是另一种情况：函数 $f$ 不丢失信息，但由于反演 $f$ 在计算上困难，所以无法从 $f(x)$ 中预测 $b(x)$。在这种情况下，硬核谓词才真正体现了单向函数的计算困难性。

此外，如果 $f$ 是单射，那么 $f$ 存在硬核谓词的前提是 $f$ 必须是单向函数。

【单向函数族的硬核谓词】

基本定义

硬核谓词也可以定义在单向函数族上。

对于一族单向函数 $(I,D,F)$，谓词可以依赖于函数索引 $i$。因此，硬核谓词可写为：

$$B:\{0,1\}^{*}\times\{0,1\}^{*}\to\{0,1\}$$

其中，$B(i,x)$ 表示在索引为 $i$ 的函数中，输入 $x$ 对应的硬核比特。

若对任意概率多项式时间算法 $A’$、任意正多项式 $\mathrm{poly}(\cdot)$，以及所有充分大的 $n$，都有：

$$P[A'(I_n,f_{I_n}(X_n))=B(I_n,X_n)] < \frac{1}{2}+\frac{1}{\mathrm{poly}(n)}$$

则称 $B$ 是单向函数族 $(I,D,F)$ 的硬核谓词。其中，$I_n\stackrel{\mathrm{def}}{=}I(1^n)$ 是随机生成的函数索引，$X_n\stackrel{\mathrm{def}}{=}D(I_n)$ 是从对应定义域中采样得到的输入。

这个定义说明：攻击者即使知道函数索引 $I_n$，也知道函数值 $f_{I_n}(X_n)$，仍然无法显著优于随机猜测地预测 $B(I_n,X_n)$。

常见候选例子

RSA 函数族

对于 RSA 函数族，如果假设 RSA 函数族是单向的，那么 $x$ 的最低有效位就是 RSA 的硬核谓词。

也就是说，给定：

$$\mathrm{RSA}_{N,e}(x)=x^e\bmod N$$

想要以显著高于 $\frac{1}{2}$ 的概率猜出 $x$ 的最低有效位，在计算上是困难的。

Rabin 函数族

对于 Rabin 函数族，如果假设整数因子分解是困难的，那么对于 Blum 整数 $N$，给定：

$$\mathrm{Rabin}_N(x)=x^2\bmod N$$

其中 $x\in Q_N$，$Q_N$ 表示模 $N$ 下的二次剩余集合，那么想要猜出 $x$ 的最低有效位是困难的。

DLP 函数族

对于离散对数函数族，如果假设 DLP 函数族是单向的，那么给定：

$$\mathrm{DLP}_{P,G}(x)=G^x\bmod P$$

想要判断 $x<\frac{P}{2}$ 是否成立在计算上是困难的，即关于指数 $x$ 的高低半区信息可以作为 DLP 函数族的硬核谓词。