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算法的解法。