6.1 线性操作¶

• 选择乘数隐藏数问题，顾名思义，它允许我们选择隐藏数问题中的乘数。

  $\mathbb{F}_p$-HNP(CM): 指定一个素数$p$，$f$为定义在$\mathbb{F}_p$上的函数，令未知数$s\in \mathbb{F}_p^*$。从给定的预言机$f_s(x):=f(sx)$恢复$s$。

  我们可以考虑两种访问预言机的方式：在自适应(adaptive)模型中，整个恢复过程都将涉及访问预言机，因此可能不断地调整查询参数。在非自适应(non-adaptive)模型中，在恢复开始之前，只允许对一组特定的参数点发起查询。显然后者的模式比前者更严格。但这种区别无法应用至比特安全中，但我们可以用此来发起侧信道攻击，例如：

• 这是个历史悠远的问题，尽管“隐藏数问题”是由Boneh和Venkatesan在后面提出的。它最初是在RSA的比特安全背景中被研究的，随着隐藏数问题的抽象化，人们也意识到它同样适用于DLP以及其他各类计算问题中。

• 如果$\mathbb{F}_p$-HNP(CM)中函数$f$是一个最低有效位函数，那么它可以通过交换位来解决上述问题。我们可以很容易地将此想法推广至$\log\log(p)$位。因此大部分情况重点针对的是不可信的预言机，其内部的比特函数将复杂很多。Alexi，Chor，Goldreich和Schnorr [3] 首先给出了一种对任何具有猜测概率的预言机其最低有效位函数的结论。基于此工作 [6]。这个结论是自适应的，其使用了一种列表解码(list-decoding)的方法在一个小列表中解出未知数$s$（可能还有其他内容）。Hastad和Naslund提出了一种完备的对于$\mathbb{F}_p$-HNP(CM)中任意的单比特函数和具有猜测概率的预言机的解法 [46]，基于后者的理论，这个解法是自适应的并且还使用了列表解码的方案。更多关于这些年的研究历史可以在 [39] 中进行查阅。

• 其中许多工作都非常复杂，例如内部位，以及需要进行复杂的代数操作例如调整和取消调整位。Akavia，Goldwasser和Safra [2]提议使用一种解决$\mathbb{F}_p$-HNP(CM)的新方法。这种方法有着许多优势：首先它非常简单清晰，它具有更大的通用性，它更像是一种数学方法而非位操作，它适用于更多种类的函数，但是它的解是非适应性的。我们重复一下 [2, 定理 2] 的结论并进行简单证明。

  定理 6.1 对于任意有一个非0$\tau$-重傅立叶系数的函数$f$（在$\mathbb{F}_p$上），将可以在多项式时间$\log(p),\|f\|_\infty,\tau^{-1}$内得到$\mathbb{F}_p$-HNP(CM)的一个(非自适应)解。

  简单证明： 在加群$\mathbb{Z}_p$中运行定理3.9的(非适应性)SFT算法，并在阈值$\tau$的情况对$f$和$f_s$计算分别得到每个函数的$\tau$-重系数列表$L$和$L_s$。如果$\tau$未知我们可以用学习算法（在多项式时间内）进行实验来选择合适的阈值，即对每个$\alpha \in \mathbb{F}_p^*$来缩放属性$\widehat{f}_s(\alpha)=\widehat{f}(\alpha s^{-1})$。此外对每个$\alpha \in L_s$（$\widehat{f}_s(\alpha)$是$\tau$-重）都存在$\beta \in L$满足$\beta = \alpha s^{-1}$。此时$\alpha\beta^{-1}$便是$s$的一个可能值，每个列表的大小最大为$2\|f\|_2^2/\tau$，所以$s$的最大可能值不超过$(2\|f\|_2^2/\tau)^2$。此时我们可以来遍历其中的每一对组合得到所有的可能值。

• 将$1$-维的$\mathbb{F}_p$-HNP(CM)推广至更高维，我们可以得到

  $\mathbb{F}_p$-MVHNP(CM)：给定一个素数$p$和正整数$m$，以及定义在$\mathbb{F}_p^m$上的函数$f$，令未知数$s\in \mathbb{F}_p^m$。从给定的预言机$f_s(\mathbf{x}) := f(\mathbf{s\cdot x})=f(s_1x_1+\cdots+s_mx_m)$。

• 有了多变量属性缩放(引理 3.6)，$\mathbb{F}_p$-MVHNP(CM)将有着与$\mathbb{F}_p$-HNP(CM)类似的解法。

  定理 6.2 对任意有一个非0$\tau$-重傅立叶系数的函数$f$（在$\mathbb{F}_p$上），将可以在多项式时间$\log(p),\|f\|_\infty,\tau^{-1}$内得到$\mathbb{F}_p$-HNP(CM)的一个(非自适应)解。

  证明： 这个证明由命题 3.7和定理 6.1的证明得出，我们重复其主要论点。在加群$\mathbb{Z}_p$（或$\mathbb{Z}_p^m$）中运行定理3.9的(非适应性)SFT算法，并在阈值$\tau$的情况对$f$（或$f_s$）计算得到每个函数的$\tau$-重系数列表$L$（或$L_s$）。

  由命题 3.7，当且仅当存在$\beta \in L$并且对每个$1\le j \le m$有$\alpha_j=\beta s_j$时有$(\alpha_1,\dots,\alpha_m) \in L_s$。此时$(\alpha_1\beta^{-1},\dots,\alpha_m\beta^{-1})$便是$\mathbf{s}$的一个可能解。

• 定理 6.1和定理 6.2对任何具有猜测概率的预言机都是成立的，在这种情况下，我们需要降低SFT算法的阈值，因为一般来说，错误的数值会使函数与小字符集的相关性降低（详情见节 3.4）。与随机乘数不同（上一章介绍），此时解并不需要一组确切的无误差集。该定理特别适用于集中函数（见定义 3.5），由于单比特函数是集中的（见节 3.3.1）且$\|f\|_\infty=1$，我们可以得到以下推论（同理多变量的情况可以由推论 3.8得出）

  推论 6.3 对于任何单比特函数以及具有猜测概率的预言机，存在$\mathbb{F}_p$-MVHNP(CM)和$\mathbb{F}_p$-MVHNP(CM)的（非适应性）多项式时间解。

  备注 6.4 我们可以尝试向预言机查询$(0,\dots,0,x_i,0,\dots,0)$解决$\mathbb{F}_p$-MVHNP(CM)，其中$x_i$是$\mathbb{F}_p$-HNP(CM)的解。如上所述，对这些问题主要关注的是预言机不可靠的情况，一个预言机可能在此类查询时会报错。$\mathbb{F}_p$-MBHNP(CM)的直接解允许足够随机化以应对此情况。