6.3 非线形操作

• Fp-HNP(CM) 和 Fp-MVHNP(CM) 的解决方案是基于加群中的傅里叶分析，并利用傅里叶变换的缩放特性来计算函数$f_s(x):=f(sx)$ 和$f_x(\mathbf{x}):= f(s_1x_1+\dots+s_mx_m)$。换句话说，这些函数是 f 与线性映射的组合。

• 我们要考虑这种方法是否可以用于其他代数群（如椭圆曲线和代数环）。这些情况下的隐数问题涉及到$\mathbb{Z}_p$ 上的有理操作，而不是线性操作。自然的方法是在加法群$(\mathbb{Z}_p,+)$ 中仍然使用傅里叶分析，但不是用线性映射进行组合，而是用有理函数进行组合。

• 如果能开发出这样的工具，我们就可能有办法解决某些模型中椭圆曲线点群中 Diffie-Hellman 密钥交换的比特安全问题。还有其他问题可以用一般群上的傅里叶分析来处理。例如，[15] 的作者提出了是否有可能将这些结果应用于模反隐藏数问题的问题。我们在下一章中介绍所有这些问题。

• 不幸的是，将 SFT 算法应用于这类问题有一个重大障碍。令$f:G\rightarrow\mathbb{C}$ 为一个函数，令$f_s(x) = f\circ \varphi_s(x)$，其中$\varphi_s:G\rightarrow G$ 是一个可有效计算的函数（取决于值$s$）。要概括定理 6.1 的证明，需要以下三个条件。

  1. 对于一个不可忽略的$\tau$，函数$f$ 有一个（非零）$\tau$ 重的系数。

  2. 对于一个不可忽略的$\tau$，函数$f_s$ 有一个（非零）$\tau$ 重的系数。

  3. 在$f$ 和$f_s$ 的（$\tau$ 重）系数之间存在一种关系，可以确定$s$（或者至少是$s$ 的候选小集合）。

• 由于单比特函数是集中的，如节 3.3.1 所示，在命题 3.25 的条件下，函数$f_s=f\circ \varphi_s$ 没有不可忽略的$\tau$ 重合系数。椭圆曲线加法定律和代数环的部分群定律，以及模反隐藏数问题中的操作，都满足命题 3.25 中关于$\varphi$ 的条件。因此，相应的隐藏数问题中的函数$f_s$ 没有重系数，所以不能使用涉及 SFT 算法的解法。