常见的单向函数族

【概述】

在单向函数族中已经将单向函数表述为函数族的形式，从而更方便地描述一些自然的单向函数候选对象。

下面节介绍几个基于计算数论的常见候选函数族，包括：

1. RSA 函数（RSA Function）
2. Rabin 函数（Rabin Function）
3. 因子分解置换（Factoring Permutations）
4. 离散对数函数（Discrete Logarithms）

这些例子并不是无条件证明为单向函数族，而是基于一些被广泛相信计算困难的数论问题。

【RSA 函数族】

基本思想

RSA 函数来自整数分解问题（Integer Factorization Problem）。

给定两个大质数 $P,Q$，计算它们的乘积

$$N=P\cdot Q$$

是容易的，可以在多项式时间内完成；但是反过来，给定合数 $N$，想要恢复出它的两个质因子 $P,Q$，通常被认为是困难的，尤其是在 $P,Q$ 足够大时。

这种困难性进一步影响模 $N$ 意义下的幂运算反演问题。给定一个整数 $e$，从 $x$ 计算：

$$x^e\bmod N$$

是容易的，可以通过快速幂算法在多项式时间内完成；但反过来，在不知道 $N$ 的质因子分解时，给定 $x^e\bmod N$ 想要恢复 $x$ 是困难的。

因此，可以把模合数上的幂映射：

$$x\mapsto x^e\bmod N$$

看作一个候选单向函数。

索引、定义域与函数映射

为说明 RSA 函数满足单向函数族定义中的容易采样和计算条件，考虑对应三元组 $(I_{\operatorname{RSA}},D_{\operatorname{RSA}},F_{\operatorname{RSA}})$

索引采样算法

$I_{\operatorname{RSA}}$ 在输入 $1^n$ 时，首先随机选择两个质数 $P,Q$，满足：

$$2^{n-1}\leq P<Q<2^n$$

然后随机选择一个整数 $e$，使得：

$$\gcd(e,(P-1)(Q-1))=1$$

最后输出 $(N,e)$，其中 $N=P\cdot Q$

为了高效实现这个过程，需要有概率多项式时间算法能够均匀或近似均匀地生成质数。

定义域采样算法

$D_{\operatorname{RSA}}$ 在输入 $(N,e)$ 时，从集合

$$D_{N,e}=\{1,\cdots,N\}$$

中近似均匀地选择一个元素。

在实际实现中，需要通过一系列无偏随机比特来完成从 $N$ 个元素中随机选择一个元素的过程，而这种实现可能带来指数级小的偏差，因此这里是近似均匀。

函数求值算法

$F_{\operatorname{RSA}}$ 在输入 $((N,e),x)$ 时，输出：

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

由于 $e$ 与 $(P-1)(Q-1)$ 互质，该函数在其定义域上是一个置换（Permutation），即每个输出都有唯一原像。因此，RSA 函数族是一个置换集合（Collection of Permutations）。

单向性假设

RSA 函数是否难以反演，与大整数分解问题密切相关。但是，目前并不知道能否将分解 $N$ 的问题归约到反演 $\operatorname{RSA}_{N,e}$ 的问题。

不过，目前已知的反演 $\operatorname{RSA}_{N,e}$ 的最佳算法，通常都显式或隐式地需要分解 $N$。因此，人们广泛相信 RSA 函数族是难以反演的。

换句话说，RSA 函数族是一个重要的候选单向函数族，但其单向性依赖于数论困难性假设，而不是无条件结论。

定义域的另一种选择

前面的定义中，$D_{N,e}$ 对应模 $N$ 的加法群，因此包含 $N$ 个元素。

另一种常见选择是把定义域限制为模 $N$ 的乘法群，即与 $N$ 互质的元素集合。在这种情况下，定义域大小为：

$$\begin{align*} (P-1)(Q-1) &= PQ-P-Q+1\\ &= N-P-Q\\ &\approx N-2\sqrt{N} \\ &\approx N \end{align*}$$

对应的定义域采样算法可以先从 $\{1,\cdots,N\}$ 中选取一个元素，然后丢弃那些与 $N$ 不互质的少数情况。

在模 $N$ 的乘法群上，前面定义的函数映射：

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

仍然诱导出一个置换。

通过这种形式得到的函数族与原来的 RSA 函数族具有相同的反演困难性，具体采用哪一种定义域形式，更多是一种表述偏好。

RSA 映射的置换性证明

置换性

证明：当 $N=P\cdot Q, \gcd(e,(P-1)(Q-1))=1$ 时，映射

$$x\mapsto x^e\bmod N$$

在模 $N$ 的剩余类集合上是一个置换，即每个输出都有唯一原像。

证明思路

置换本质上是从一个集合到自身的双射，也就是每个元素都会被映射到唯一的元素，并且每个输出元素都有唯一的输入来源。

对于有限集合上的函数来说，如果能够构造出一个反向映射，使得先应用原映射、再应用反向映射能够回到原来的元素，那么原映射就不会把两个不同输入映射到同一个输出，也不会遗漏任何输出元素。

因此，下面的证明策略是：不直接逐个证明 RSA 映射是单射和满射，而是构造它的逆映射。

证明

考虑映射 $x\mapsto x^d\bmod N$，证明它是 $x\mapsto x^e\bmod N$ 的逆映射，即证明：

$$(x^e)^d\equiv x\pmod N$$

由于 $N=P\cdot Q$，那么只需要分别证明：

$$x^{ed}\equiv x\pmod P,\quad x^{ed}\equiv x\pmod Q$$

首先考虑模 $P$ 的情况。如果 $x\equiv 0\pmod P$，那么显然有：

$$x^{ed}\equiv 0\equiv x\pmod P$$

如果 $x\not\equiv 0\pmod P$，考虑到 $\gcd(e,(P-1)(Q-1))=1$，那么存在整数 $d$，使得：

$$ed\equiv 1\pmod{(P-1)(Q-1)}$$

即存在整数 $k$，满足：

$$ed=1+k(P-1)(Q-1)$$

即有：

$$ed-1=(P-1)(k(Q-1))$$

所以 $ed-1$ 是 $P-1$ 的倍数，考虑到费马小定理 $x^{P-1}\equiv 1\pmod P$，因此有：

$$x^{ed}=x\cdot x^{ed-1}\equiv x\cdot 1=x\pmod P$$

综合考虑两种情况，无论 $x$ 是否能被 $P$ 整除，都有：

$$x^{ed}\equiv x\pmod P$$

同理，对于模 $Q$ 的情况，可以证明：

$$x^{ed}\equiv x\pmod Q$$

那么，通过中国剩余定理进行合并，即有：

$$x^{ed}\equiv x\pmod {P\cdot Q}$$

也就是：

$$(x^e)^d\equiv x\pmod N$$

因此，映射 $x\mapsto x^e\bmod N$ 存在逆映射 $y\mapsto y^d\bmod N$，所以它是模 $N$ 剩余类集合上的一个置换。

【Rabin 函数族】

函数定义

Rabin 函数族与 RSA 函数族类似，也基于模合数 $N$ 的运算。不同之处在于，RSA 函数是取 $e$ 次幂，而 Rabin 函数是平方运算。

Rabin 函数定义为：

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

这里 $N$ 仍然通常是 $P$、$Q$ 两个质数的乘积。

与 RSA 的区别

Rabin 函数与 RSA 函数的重要区别在于，RSA 函数具有置换性，而 Rabin 函数在模 $N$ 的乘法群通常不是置换。

对于一个平方值：

$$y=x^2 \bmod N$$

如果 $x$ 与 $N$ 互质，那么在模 $P$ 下有两个平方根：

$$x,-x \pmod P$$

在模 $Q$ 下也有两个平方根：

$$x,-x \pmod Q$$

通过中国剩余定理，将模 $P$ 和模 $Q$ 下的选择组合起来，可以得到四种不同的平方根：

$$\pm x \bmod P,\quad \pm x\bmod Q$$

因此，在模 $N$ 的乘法群总，一个二次剩余通常会对应 4 个不同的平方根。即 Rabin 函数不是单射，而是在其像集合上形成一个 4 对 1 映射（4-to-1 Mapping）。

需要注意的是，Rabin 函数并不是把模 $N$ 乘法群满射到自身，而是把元素映射到模 $N$ 的二次剩余集合中。所谓 4 对 1，是指对于像集合中的每个二次剩余，通常有四个原像。

计算等价

Rabin 函数的一个重要特点是：模 $N$ 开平方与分解 $N$ 在计算上等价，即二者可以通过概率多项式时间归约相互转化。

一方面，如果已经知道 $N=P\cdot Q$ 的分解，那么可以分别在模 $P$ 和模 $Q$ 下求平方根，再通过中国剩余定理合并，从而得到模 $N$ 下的平方根。因此，分解 $N$ 可以帮助反演 Rabin 函数。

另一方面，如果存在一个有效算法能够在模 $N$ 下开平方，那么也可以利用它来分解 $N$，即随机选择一个 $z$，计算：

$$y=z^2\bmod N$$

然后调用开平方算法，得到 $y$ 的另一个平方根 $r$。

如果 $r\not\equiv \pm z\pmod N$，那么 $z-r$ 会同时揭示 $P$ 或 $Q$ 的因子，从而可以通过 $\gcd(z-r,N)$ 得到 $N$ 的一个非平凡因子。

因此，模 $N$ 开平方和分解 $N$ 在计算上是等价的。

单向性结论

由于 Rabin 函数的反演问题就是模合数开平方，而模合数开平方与分解 $N$ 等价。

所以，如果大整数分解是困难的，那么 Rabin 函数族就是单向函数族；反过来，如果 Rabin 函数容易反演，那么大整数分解也可以被有效完成。

因此，Rabin 函数的单向性与整数分解困难性直接对应。这一点比 RSA 函数更明确：对于 RSA，目前不知道分解 $N$ 是否可以归约到反演 RSA；而对于 Rabin，反演 Rabin 与分解 $N$ 是等价的。

【因子分解置换与 SQR 函数族】

构造动机

Rabin 函数定义为：

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

当 $N=P\cdot Q$ 是两个质数的乘积时，平方映射在模 $N$ 的乘法群上通常不是置换，而是一个 4 对 1 映射。

因此，如果希望从 Rabin 函数得到一个置换，就不能直接在整个模 $N$ 的乘法群上考虑平方映射，而需要把定义域限制到一个更合适的子集合上。

Blum 整数与二次剩余

为了使平方映射在二次剩余集合上成为置换，需要对 $N$ 作进一步限制。

考虑一类特殊整数，若整数 $N=P\cdot Q$，并且两个质数 $P$ 和 $Q$ 满足：

$$P\equiv Q\equiv 3\pmod 4$$

则 $N$ 称为 Blum 整数（Blum Integer）。

在 Blum 整数的基础上，若存在整数 $x$，使得：

$$r\equiv x^2\pmod N$$

则称 $r$ 是模 Blum 整数 $N$ 的二次剩余（Quadratic Residue）。

二次剩余集合上的置换性

在整个模 $N$ 的乘法群上，平方映射不是置换，因为每个二次剩余通常有 4 个平方根。

但是，当 $N$ 是 Blum 整数时，若只在由模 Blum 整数 $N$ 乘法群中的二次剩余集合 $Q_N$ 内考虑平方映射，情况会发生变化。此时，$Q_N$ 中的每一个元素都有唯一一个平方根仍然落在 $Q_N$ 中。

也就是说，对于任意 $r\in Q_N$，虽然它在整个模 $N$ 的乘法群中可能有 4 个平方根，但这 4 个平方根中只有一个属于 $Q_N$。

因此，平方映射：

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

从 $Q_N$ 到 $Q_N$ 是一一对应的，即它在 $Q_N$ 上诱导出了一个置换。

这就是因子分解置换的核心思想：在 Blum 整数条件下，把 Rabin 平方函数限制到二次剩余集合 $Q_N$ 上，它就成为了置换。

SQR 函数族

基于上述思想，可以定义平方置换函数三元组：

$$\operatorname{SQR}=(I_{\operatorname{BI}},D_{\operatorname{QR}},F_{\operatorname{SQR}})$$

（1）索引采样算法

$I_{\operatorname{BI}}$ 在输入 $1^n$ 时，随机选择两个质数 $P,Q$，满足 $2^{n-1}\leq P<Q<2^n$，并且：

$$P\equiv Q\equiv 3\pmod 4$$

然后输出：

$$N=P\cdot Q$$

因此，索引 $N$ 指定了一个 Blum 整数。

（2）定义域采样算法

$D_{\operatorname{QR}}$ 在输入 $N$ 时，需要从二次剩余集合 $Q_N$ 中均匀选择一个元素。

为了做到这一点，可以先在模 $N$ 的乘法群中均匀选择一个元素 $a$，然后输出：

$$a^2\bmod N$$

这样得到的元素一定属于 $Q_N$，因为它本身就是某个元素的平方。

（3）函数求值算法

$F_{\operatorname{SQR}}$ 与 Rabin 函数中的平方运算相同，即：

$$F_{\operatorname{SQR}}(N,x)=x^2\bmod N$$

由于这里的定义域被限制为 $Q_N$，并且当 $N$ 是 Blum 整数时，平方映射在 $Q_N$ 上是置换，所以 $F_{\operatorname{SQR}}$ 定义的是一个置换集合。

单向性

置换集合的反演问题仍然是模 $N$ 开平方问题，即给定：

$$y=x^2\bmod N$$

要反推出满足条件的 $x\in Q_N$。

而模合数开平方与分解 $N$ 在计算上等价，因此，如果整数分解是困难的，那么这个 SQR 置换集合就是单向的。

【离散对数函数族】

基本思想

除了大整数分解问题之外，另一个被广泛认为困难的数论问题是离散对数问题（Discrete Logarithm Problem）。

在模质数 $P$ 的有限域 $\mathbb{F}_P$​ 中，非零元素构成一个乘法群，记为：

$$\mathbb{F}_P^*=\{1,\cdots,P-1\}$$

该乘法群是循环群，因此存在生成元。

设 $G$ 是 $\mathbb{F}_P^{*}$ 的一个生成元，即本原元（Primitive Element）。离散对数问题可以表述为：给定 $P$、生成元 $G$，以及某个群元素 $y\in \mathbb{F}_P^{*}$，找到一个指数 $x$，使得：

$$y = G^x \bmod P$$

从指数 $x$ 计算 $G^x\bmod P$ 是容易的，可以用快速幂算法在多项式时间内完成；但反过来，在给定 $G$ 和 $y$ 的情况下求出 $x$，通常被认为是困难的，尤其是在 $P$ 足够大时。

因此，可以把指数映射：

$$x\mapsto G^x\bmod P$$

看作一个候选单向函数。

索引、定义域与函数映射

离散对数函数族的单向性正是基于离散对数问题，该函数族的三元组为：

$$(I_{\operatorname{DLP}},D_{\operatorname{DLP}},F_{\operatorname{DLP}})$$

索引采样算法

$I_{\operatorname{DLP}}$ 的目标，是随机生成一个质数 $P$ 以及模 $P$ 乘法群 $\mathbb{F}_P^*$ 的一个生成元 $G$。这样，二元组 $(P,G)$ 就指定了一个具体的离散对数函数。

具体来说，在输入 $1^n$ 时，随机选择一个质数 $P$，满足 $2^{n-1}\leq P<2^n$，然后选择模 $P$ 乘法群 $\mathbb{F}_P^*$ 中的一个本原元 $G$，最后输出

$$(P,G)$$

由于判断一个候选元素 $G\in \mathbb{F}_P^{*}$ 是否为生成元，本质上就是判断它的阶是否为 $P-1$，即本原元就是阶等于 $P-1$ 的元素。

因此，为了高效找到本原元 $G$，通常需要利用 $P-1$ 的质因子分解。在给定 $P-1$ 的素因子分解后，只需要检查对每个素因子 $q\mid P-1$，是否都有：

$$G^{(P-1)/q}\not\equiv 1\pmod P$$

如果上述条件成立，则 $G$ 是本原元。

另一种方式是生成形如：

$$P=2Q+1$$

的质数，其中 $Q$ 也是质数。此时 $P-1=2Q$，因子结构更简单，便于寻找本原元。不过，这种做法需要额外假设这类质数上的离散对数问题仍然困难。

定义域采样算法

$D_{\operatorname{DLP}}$ 在输入 $(P,G)$ 时，均匀选择一个模 $P-1$ 的剩余类，即选择：

$$x\in \mathbb{Z}_{P-1}$$

函数求值算法

$F_{\operatorname{DLP}}$ 在输入 $((P,G),x)$ 时，输出：

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

因此，反演该函数就等价于：给定 $G^x\bmod P$，求出指数 $x$，这正是以 $G$ 为底、模 $P$ 的离散对数问题。

置换性质

对于每个索引 $(P,G)$，由于 $G$ 是模 $P$ 乘法群 $\mathbb{F}_P^{*}$ 的生成元，所以每个非零元素 $y\in \mathbb{F}_P^{*}$ 都可以唯一地写成：

$$y=G^x\bmod P$$

其中，$x\in \mathbb{Z}_{P-1}$

因此，映射：

$$x\mapsto G^x\bmod P$$

给出了从模 $P-1$ 的加法群 $\mathbb{Z}_{P-1}$ 到模 $P$ 的乘法群 $\mathbb{F}_P^{*}$ 的双射，即 $\operatorname{DLP}_{P,G}$ 在指数集合 $\mathbb{Z}_{P-1}$ 和非零剩余类集合 $\mathbb{F}_P^{*}$ 之间诱导出一个置换。

其他群上的指数映射

其他群上的指数映射也可以作为合理的候选单向函数，只要该群上的离散对数问题被认为是困难的。

例如，在椭圆曲线点群中，通常也认为离散对数问题是困难的。因此，椭圆曲线上的标量乘法也可以看作离散对数型候选单向函数的一个重要实例。