4.1 研究动机¶

• 单向函数（one-way function）是指容易计算得到结果但很难从结果进行逆推得到输入的函数。或者说，给定一个输入$x$对于单向函数$f$，计算$f(x)$是很容易的，但是对于给定的$f$和$f(x)$，想要得到$x$是很困难的。并且想找到一个多项式时间内从$f,f(x)$中计算得到$x$的算法是不存在的。但是是否存在一个算法能够得到$x$的部分信息(partial information)呢？是否能够判断$x$的素性？是否能够判断$x$的奇偶性？

• 硬核函数(hardcore functions)是这些问题的一种表现形式。令函数$f$，函数$b$是计算硬核的(computationally hardcore)当对于给定的$f(x)$难以计算$b(x)$时。注意虽然逆推函数$f$是“足够困难”的，但$f$也并不一定是一个单向函数。此外，这个例子中有趣的是对于给定$x$，计算$f(x)$，特别是$b(x)$将是非常容易的。一种定义硬核函数$b$的方法是：无法区分得到的结果是$b(x)$还是随机数，我们不使用这个概念，所以我们使用“硬核”代指“计算硬核”。

• 现在我们来看第一个例子，离散对数问题（discrete logarithm problem）。在$\mathbb{Z}_p^{*}$中计算幂是很容易的，但是计算对数就不一定了。例如对于$p>2$且$2^n<p<2^{n+1}$的情况，令$g\in \mathbb{Z}_p^{*}$计算$exp_{g,p}(x): \mathbb{Z}\rightarrow \mathbb{Z}_p^{*}$，即

  $$exp_{g,p}(x) := g^x\pmod{p}$$

  所以问题是当给出$g^x\pmod{p}$时如何计算$x$的值。

  我们来看下最高有效位(most significant bit)函数

  $$MSB: \mathbb{Z}_p\rightarrow \{0,1\}$$

  当且仅当$0\le x<2^n$时有$MSB(x)=0$，显然$exp_{g,p}$是硬核的。

  令$x$的二进制表示为$x = \sum_{i=0}^{n}x_i2^i$。注意$MSB(x)$输出的是$2^n$的系数，假设算法$\mathcal{A}$将输出对于$g^x\in\mathbb{Z}_p$中$x$的$MSB(x)$。

  即$\mathcal{A}=x_n$，对于给定的$x_n,\dots,x_{n-j+1}$，令$z = \sum_{i=0}^{n-j}{x_i2^{i+j}}$并且计算

  $$\begin{aligned} \left(g^xexp_{g,p}(-(x_n2^n+\cdots+x_{n-j+1}2^{n-j+1}))\right)^{2^j} &= (g^xg^{-(x_n2^n+\cdots+x_{n-j+1}2^{n-j+1})})^{2^j}\\ &=g^{2^j(x_{n-j}2^{n-j}+\cdots+x_0)}\\ &=g^z \end{aligned}$$

  对$g^z$调用$\mathcal{A}$算法将会得到$x_{n-j}$。这样我们可以利用$\mathcal{A}$递归得到$x$的所有比特位。因此通过$MSB$我们将能够逆推计算$exp_{g,p}$。

• 事实上一个函数难以逆推计算并不意味着逆推出原象的任何信息，接下来我们将会来分析这种情况。再次考虑函数$exp_{g,p}$，现在$g\in\mathbb{Z}_p^{*}$是一个素数。对于$g^x\pmod{p}$，我们将展示如何利用勒让德符号(Legendre symbol)来获取$LSB(x)$，函数$LSB: \mathbb{Z}_p\rightarrow\{0,1\}$将会给出输入值的奇偶性。$\mathbb{Z}_p^{*}$的阶是$p-1=2q$，有

  $$g^{p-1}\equiv 1\pmod{p}\\ g^{q} \equiv -1\pmod{p}$$

  对于$x=2n+x_0,\ x_0\in\{0,1\}(0\le n<q)$，有

  $$\begin{aligned} (g^x)^q &= g^{(2n+x_0)(p-1)/2}\\ &= g^{n(p-1)+x_0(p-1)/2}\\ &=(g^{p-1})^n(g^q)^{x_0}\\ &\equiv (-1)^{x_0}\pmod{p} \end{aligned}$$

  因此，如果$(g^x)^q\equiv 1\pmod{p}$则意味着$x$是偶数，如果$(g^x)^q\equiv -1\pmod{p}$则$x$为奇数。

  注意这是群论中的结果，所以它适用于任何偶数阶（有限）群中素数的幂函数。它也可以被推广到群的阶能够被$2$的更大的幂整除的情况中。

• 这些关于单向函数的情况和整数的二进制表示息息相关，所以最大的要点便是研究硬核位，比如上述的例子中的情况。此外，位可以认为是表示整数的原子，吸引着人们去探索。如果函数是一个单向函数，那么显然不能逆推出原象的所有位。但我们可以考虑多有少位是无法计算的呢？或者是否有特殊的位，不管什么输入，始终都是硬核位呢？对于这些领域的研究我们称为比特安全。

• 为了强调函数$f$的困难性可能来源，通常说函数$b$对于各类著名问题是硬核的。例如在上面的例子中，我们讨论的是幂运算，所以我们称为“硬核DLP”。有例如对于$RSA_{N, e}: \mathbb{Z}_N\rightarrow\mathbb{Z}_N$，有$RSA_{N,e}(x) := x^e \pmod{N}$，其中$N$是两个素数的积（有关RSA加密系统的描述，以及这里介绍的其他概念，请参考Galbraith [31] or Stinson [88]的书）。RSA和DLP的硬核位都拥有广泛的研究，对于RSA每一位都是硬核位。此外，在一个素数阶的群中离散对数中，DLP的每一位也都是硬核位，这些结果我们在之后的内容中会进行解释。更多的例子、联系和讨论可以在[31, Chapter 21]中找到，同时在[39]中包含了关于硬核函数我们没有写出的一些研究结果，它同样包括了我们在本章中介绍的内容。