【无爪函数族】

基本思想

单向函数族的形式化框架，也可以用来定义一类新的函数族，即无爪函数族（Claw-Free Functions Collection）。

直观来说，一个无爪函数族由若干对函数组成。对于每个索引 $i$，都有两个函数 $f_i^0$ 和 $f_i^1$，这两个函数都容易计算，并且它们的输出分布相同。但是，给定索引 $i$ 后，想要找到一对输入 $(x,y)$，使得两个函数输出相同，即：

$$f_i^0(x)=f_i^1(y)$$

在计算上是困难的。这样的输入对 $(x,y)$ 称为索引 $i$ 对应的一个爪（Claw）。

无爪并不是说这样的 $(x,y)$ 不存在，而是说即使它存在，也不能被高效找到。

形式化定义

设一个函数对族由以下对象组成：

• 一个无限索引集合 $\bar I$

• 对每个 $i\in \bar I$，有两个有限定义域 $D_i^0$ 和 $D_i^1$

• 对每个 $i\in \bar I$，有两个函数：

  $$f_i^0:D_i^0\to R_i,\qquad f_i^1:D_i^1\to R_i$$

若存在三个概率多项式时间算法 $I,D,F$，并满足以下三个条件，则称该函数对族为无爪函数族。

三个条件

容易采样与计算

随机变量 $I(1^n)$ 的取值属于 $\bar I\cap \{0,1\}^n$，对于每个 $i\in \bar I$ 和 $\sigma\in\{0,1\}$，随机变量 $D(\sigma,i)$ 分布在 $D_i^\sigma$ 上，并且对任意 $x\in D_i^\sigma$，都有：

$$F(\sigma,i,x)=f_i^\sigma(x)$$

这说明，索引可以高效生成，定义域中的元素可以高效采样，并且两个函数 $f_i^0$ 和 $f_i^1$ 都可以高效计算。

输出分布相同

对于每个索引 $i\in \bar I$，随机变量 $f_i^0(D(0,i))$ 和 $f_i^1(D(1,i))$ 具有相同的分布。

这表示，虽然两个函数的定义域可以不同，但通过各自的定义域采样算法得到输入后，两个函数诱导出的输出分布是一样的。

换句话说，从输出分布上看，二者落在同一个范围中，并且无法通过分布差异区分输出来自哪一个函数。

难以形成爪

对于索引 $i$，如果一对输入 $(x,y)$ 满足：

$$f_i^0(x)=f_i^1(y)$$

则称 $(x,y)$ 是索引 $i$ 对应的一个爪（Claw）。

记 $C_i$ 为索引 $i$ 对应的所有爪的集合，无爪性要求，对任意概率多项式时间算法 $A’$、任意正多项式 $\mathrm{poly}(\cdot)$，以及所有充分大的 $n$，都有：

$$P[A'(I_n)\in C_{I_n}] < \frac{1}{\mathrm{poly}(n)}$$

其中，$I_n$ 表示算法 $I$ 在输入 $1^n$ 时的输出分布。

这表示，任意高效算法在只给定随机索引 $I_n$ 的情况下，都无法以非可忽略概率找到该索引对应的爪。

定义中的矛盾性要求

无爪函数族的后两个条件具有一种内在张力：一方面，两个函数的输出分布必须相同，因此从分布意义上看，二者具有共同输出，这至少意味着跨函数的共同原像对应该存在；另一方面，无爪性又要求高效算法无法找到这样的原像对。

因此，无爪函数族的核心不是没有碰撞，而是存在跨函数碰撞，但难以找到跨函数碰撞。

如果可以高效反演相关函数，就可以利用反演能力找到两个函数之间的共同输出所对应的两个原像，从而形成爪。所以，无爪函数族可以推出一族强单向函数。

此外，一个特别重要的情形是：两个定义域相同，即：

$$D_i \stackrel{\mathrm{def}}{=} D_i^0=D_i^1$$

并且 $D(\sigma,i)$ 在 $D_i$ 上均匀分布，同时 $f_i^0$ 和 $f_i^1$ 都是 $D_i$ 上的置换。这样的函数族称为无爪置换对族（Collection of Claw-Free Pairs of Permutations）。

与陷门置换类似，定义中的条件也可以放宽：允许算法 $I,D,F$ 以可忽略概率失败。

一个无爪函数族还可能具有额外性质，即索引集合 $\bar I$ 是可以高效识别的，也就是说存在概率多项式时间算法判断一个字符串是否属于 $\bar I$。

【实例】

为了说明无爪函数族并非只是抽象定义，基于离散对数问题的困难性构造一族无爪置换对，并因子分解问题分别构造无爪函数族与无爪置换对族。

基于离散对数问题的无爪置换对族

构造思想

让两个函数的形式只相差一个乘法因子 $Z$，如果能够找到它们之间的爪，那么这个爪就会泄露 $Z$ 关于生成元 $G$ 的离散对数。

因此，找爪的困难性可以归约到离散对数问题的困难性。

索引与定义域

索引集合由三元组组成：

$$(P,G,Z)$$

其中，$P$ 是一个质数，$G$ 是模 $P$ 的本原元，$Z$ 是模 $P$ 的非零剩余元。

索引采样算法按照常见的单向函数族中离散对数函数族中的方式选择 $P$ 和 $G$，并从模 $P$ 的非零剩余元中均匀选择 $Z$，对于索引 $(P,G,Z)$，两个函数的定义域相同，均为：

$$\{1,\cdots,P-1\}$$

定义域采样算法从该集合中均匀采样。

函数映射

对 $\sigma\in\{0,1\}$，定义：

$$f_{P,G,Z}^{\sigma}(x)\stackrel{\mathrm{def}}{=}Z^\sigma\cdot G^x \bmod P$$

即当 $\sigma=0$ 时：

$$f_{P,G,Z}^{0}(x)=G^x \bmod P$$

当 $\sigma=1$ 时：

$$f_{P,G,Z}^{1}(x)=Z\cdot G^x \bmod P$$

由于 $G$ 是模 $P$ 的本原元，$G^x$ 在非零剩余元中形成置换，再乘以非零元素 $Z$ 仍然是置换。因此，$f_{P,G,Z}^{0}$ 和 $f_{P,G,Z}^{1}$ 都是定义域 ${1,\cdots,P-1}$ 上的置换。

特别地，$f_{P,G,Z}^{0}$ 与前面 DLP 函数族中的函数 $DLP_{P,G}$ 一致。

无爪性的证明

如果能够找到索引 $(P,G,Z)$ 对应的一个爪 $(x,y)$，则有：

$$f_{P,G,Z}^{0}(x)=f_{P,G,Z}^{1}(y)$$

代入函数定义，得到：

$$G^x \equiv Z\cdot G^y \pmod P$$

于是：

$$G^{x-y}\equiv Z \pmod P$$

这说明，$x-y$ 就给出了 $Z$ 关于底数 $G$ 的离散对数。

因此，如果存在高效算法能够在非可忽略比例的索引上形成爪，那么就可以利用它反演前面定义的离散对数函数族。换句话说，如果离散对数函数族是单向的，那么由

$$f_{P,G,Z}^{\sigma}(x)=Z^\sigma\cdot G^x \bmod P$$

定义的置换对族就是无爪的。

索引集合的识别问题

上述构造的一个不足是：它不一定具有可高效识别的索引集合。原因在于，目前并不知道如何高效判断一个元素是否是模质数 $P$ 的本原元。

为了解决这一点，可以作出稍强的离散对数困难性假设：即使给定乘法群大小 $P-1$ 的因子分解，离散对数问题仍然是困难的。在这个假设下，可以把 $P-1$ 的因子分解也加入索引描述中。这样就可以通过检查：

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

来判断 $G$ 是否为本原元。其中，$Q$ 遍历 $P-1$ 的素因子。

如果进一步假设离散对数在形如：

$$P=2Q+1$$

且 $Q$ 也是质数的情况下仍然困难，那么识别会更简单。此时只需要计算：

$$G^2\bmod P,\quad G^{(P-1)/2}\bmod P$$

并检查二者是否都不等于 $1$，即可判断 $G$ 是否为本原元。

基于因子分解问题的无爪函数族

Jacobi 符号

Jacobi 符号（Jacobi Symbol）可以看作 Legendre 符号在合数模数上的推广。若 $N=P\cdot Q$ 是两个奇质数的乘积，且 $a$ 与 $N$ 互素，则 $a$ 关于 $N$ 的 Jacobi 符号定义为：

$$\left(\frac{a}{N}\right)=\left(\frac{a}{P}\right)\left(\frac{a}{Q}\right)$$

其中 $\left(\frac{a}{P}\right)$ 和 $\left(\frac{a}{Q}\right)$ 是 Legendre 符号，用于表示 $a$ 分别在模 $P$ 和模 $Q$ 下是否为二次剩余。

当 $N$ 是合数时，$\left(\frac{a}{N}\right)=1$ 并不一定说明 $a$ 是模 $N$ 下的二次剩余，但如果 $a$ 是模 $N$ 下的二次剩余，那么它的 Jacobi 符号一定为 $1$。

因此，Jacobi 符号可以把模 $N$ 乘法群中的元素划分为符号为 $+1$ 和 $-1$ 的两类。

构造思想

该构造基于整数因子分解的困难性。核心思想是：利用 Blum 整数的结构性质构造两个平方函数，使得它们的输出分布相同；如果能够找到这两个函数之间的爪，就能够进一步得到 $N$ 的非平凡因子分解。

对于 Blum 整数 $N$，使用 Jacobi 符号的两个性质：

1. $-1$ 在模 $N$ 下的 Jacobi 符号等于 $1$
2. 每个二次剩余的平方根中，有一半的 Jacobi 符号为 $1$

记 $J_N^{+1}$ 为模 $N$ 乘法群中 Jacobi 符号为 $+1$ 的剩余类集合，记 $J_N^{-1}$ 为模 $N$ 乘法群中 Jacobi 符号为 $-1$ 的剩余类集合。

索引、定义域与函数映射

该函数族的索引集合由所有 Blum 整数组成，并且这些 Blum 整数由两个长度相同的质数相乘得到。

索引选择算法在输入 $1^n$ 后，均匀选择两个 $n$ 比特质数，要求它们都满足：

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

然后输出它们的乘积：

$$N=P\cdot Q$$

对于索引 $N$，两个函数 $f_N^0$ 和 $f_N^1$ 都是模 $N$ 平方函数，但它们的定义域是互不相交的。具体来说，函数 $f_N^\sigma$ 的定义域为：

$$J_N^{(-1)^\sigma}$$

即 $f_N^0$ 的定义域是 $J_N^{+1}$，而 $f_N^1$ 的定义域是 $J_N^{-1}$。

两个函数都定义为：

$$f_N^\sigma(x)=x^2\bmod N$$

定义域采样算法 $D$ 在输入 $(\sigma,N)$ 后，均匀选择若干个模 $N$ 的剩余类，并输出第一个 Jacobi 符号为 $(-1)^\sigma$ 的元素，这样可以从对应定义域中自然地均匀采样。

输出分布

由于 Blum 整数的结构性质，$f_N^0(D(0,N))$ 和 $f_N^1(D(1,N))$ 都在模 $N$ 的二次剩余集合上均匀分布。

因此，虽然两个函数的定义域不同，一个来自 $J_N^{+1}$，另一个来自 $J_N^{-1}$，但它们平方后的输出分布是相同的。

无爪性的证明

如果能够找到一个爪 $(x,y)$，则 $x\in J_N^{+1}$，$y\in J_N^{-1}$，并且：

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

那么，有：

$$(x-y)(x+y)\equiv 0 \pmod N$$

由于 $-1\in J_N^{+1}$，且 $J_N^{+1}$ 是乘法子群，如果 $y\equiv x \pmod N$ 或 $y\equiv -x \pmod N$，那么 $y$ 的 Jacobi 符号也应为 $+1$，这与 $y\in J_N^{-1}$ 矛盾。因此，$y$ 不可能等于 $\pm x \pmod N$。

这意味着 $x-y$ 和 $x+y$ 都不是模 $N$ 下的平凡因子，但它们的乘积却被 $N$ 整除。因此，可以通过计算 $\gcd(y-x,N)$ 或 $\gcd(y+x,N)$，得到 $N$ 的非平凡因子分解。

所以，如果能够高效形成爪，就能够高效分解 $N$。在因子分解困难的假设下，这个函数族就是无爪的。

基于因子分解的无爪置换对族

从函数对到置换对

上面的构造得到的是一族函数对，但其中每个函数是 $2$ 对 $1$ 的，并且两个函数定义在互不相交的定义域上。为了得到一族无爪置换对，需要对构造稍作修改。

新的索引集合由特殊的 Blum 整数组成。设：

$$N=P\cdot Q$$

其中，$P$ 和 $Q$ 是长度相同的质数，并满足：

$$P\equiv 3 \pmod 8,\qquad Q\equiv 7 \pmod 8$$

对于这样的合数 $N$，$2$ 和 $-2$ 都不是模 $N$ 的二次剩余，并且：

$$\pm 2\in J_N^{-1}$$

记 $Q_N$ 为模 $N$ 下的二次剩余集合。两个函数都定义在 $Q_N$ 上：

$$f_N^\sigma(x)\stackrel{\mathrm{def}}{=}4^\sigma\cdot x^2\bmod N$$

其中，$\sigma\in\{0,1\}$。

也就是说：

$$f_N^0(x)=x^2\bmod N,\quad f_N^1(x)=4x^2\bmod N$$

在该定义下，$f_N^0$ 和 $f_N^1$ 都是 $Q_N$ 上的置换。

无爪性的证明思路

如果能够找到一个爪 $(x,y)$，其中 $x,y\in Q_N$，则有：

$$f_N^0(x)=f_N^1(y)$$

即：

$$x^2\equiv 4y^2 \pmod N$$

由于 $y\in Q_N$，因此 $y$ 在模 $N$ 的乘法群中可逆，于是：

$$(x/y)^2\equiv 4 \pmod N$$

即：

$$\left(2-\frac{x}{y}\right)\left(2+\frac{x}{y}\right)\equiv 0 \pmod N$$

因为 $x,y\in Q_N$，且 $Q_N$ 是乘法子群，所以：

$$x/y\in Q_N$$

但由于 $\pm 2\notin Q_N$，因此：

$$x/y\not\equiv \pm 2 \pmod N$$

于是，可以通过计算 $\gcd(2+x\cdot y^{-1}\bmod N,N)$ 或 $\gcd(2-x\cdot y^{-1}\bmod N,N)$ 得到 $N$ 的非平凡因子分解。

因此，如果存在高效算法可以形成该置换对族的爪，那么就可以高效分解 $N$。

在因子分解困难的假设下，该置换对族是无爪的。

索引集合的识别问题

上述基于因子分解的构造也不一定具有可高效识别的索引集合。

但目前不知道如何高效区分两个质数的乘积和多于两个质数的乘积。因此，这类构造虽然能够在因子分解困难假设下给出无爪函数族或无爪置换对族，但其索引集合未必是高效可识别的。