An alternative approach towards attacks against fully-split PLWE instances

技术摘要：针对全分裂 PLWE 实例攻击的一种替代方法

问题陈述
多项式学习误差（PLWE）问题是后量子密码学的基石，由于其结构化的代数特性，通常被认为比环学习误差（Ring-LWE）更具效率。然而，这种结构也引入了潜在的脆弱性。以往的研究，特别是 [5, 6] 以及在 [2] 中的推广，引入了“基于根的攻击”（root-based attacks），这些攻击利用了有限域上特定多项式因子（称为 $n$-理想因子，$x^n - a$）的存在。这些攻击通过利用求值同态和迹算子（trace operators）来区分 PLWE 样本与均匀分布。

虽然 [2] 将这些攻击推广到了在域扩张上分解的多项式，但一个关键的开放性问题仍然存在：攻击者是否可以通过将一个“安全”的 PLWE 实例通过环同构映射到一个“脆弱”的实例（即拥有合适的 $n$-理想因子的实例），然后在该实例上执行攻击，并由此推断出原始实例的安全性，从而绕过缺乏脆弱因子的限制？本文研究了通过同构进行这种迁移策略是否能对全分裂 PLsWE 实例产生实质性的优势。

方法论
作者采用严谨的代数方法来分析在不同多项式环之间转移 PLWE 样本的可行性。该方法论分为两个主要阶段：

1. 任意分解的泛化： 本文首先探讨了将基于根的攻击扩展到不具备 $n$-理想因子的多项式上的可能性。通过利用引理 1，作者证明了可以在任意不可约因子上定义迹算子。然而，他们表明此类攻击的成功概率高度依赖于因子中零系数的数量，而对于任意多项式而言，该数量通常很低，这使得此类攻击在一般情况下难以实现。

2. 全分裂设置下的同构分析： 核心工作集中在“同构方法”上。作者考虑了两个多项式 $f(x)$ 和 $g(x)$，两者在 $\mathbb{Z}[x]$ 上均为 $N$ 次不可约多项式，且共享相同的“分解结构”（即它们在 $\mathbb{F}_q$ 上分解为相同次数的不可约因子）。

   • 构造： 利用中国剩余定理，他们在环 $R_q = \mathbb{F}_q[x]/(f(x))$ 和 $R'_q = \mathbb{F}_q[x]/(g(x))$ 之间构造了一个显式的同构 $\psi$。在全分裂情况下（即两个多项式都完全分解为线性项），该同构由范德蒙德矩阵的乘积表示：$\psi = V_g^{-1} \cdot V_f$。
   • 失真分析： 作者分析了将 PLWE 样本应用此同构并在 $g(x)$ 的一个根 $\beta$ 处进行求值所产生的影响。他们证明，这种求值在数学上等价于在 $f(x)$ 对应的根 $\alpha$ 处对原始样本进行求值。
   • 唯一性证明： 方法论的重要部分在于证明：在这些全分裂多项式环之间，任何环同构都必须采取这种特定形式（即求值同态与构造的同构的复合）。这一结论是通过引理 2、3、4 以及定理 1 建立的。

核心贡献

• 同构不变性的形式化证明： 本文提供了一个形式化证明，证明对于全分裂 PLWE 实例，任何试图通过环同构将样本迁移到脆弱设置的尝试都不会产生新的漏洞。由同构引入的噪声（误差）会扭曲样本，使得最终的区分条件与原始实例的条件完全一致。
• 环同构的特征化： 作者对全分裂多项式环之间的所有同构进行了特征化，表明它们由根的映射唯一确定。这证明了不存在可以绕过噪声扭曲的“隐藏”同构。
• 任意分解的扩展： 本研究阐明，虽然基于根的攻击在理论上可以应用于不具备 $n$-理想因子的多项式，但由于缺乏结构约束（特别是零系数的数量），严重限制了其成功概率，从而有效地关闭了将其作为实际威胁进行泛化的路径。

结果

• 噪声扭曲： 应用同构 $\psi$ 并在 $g(x)$ 的根 $\beta$ 处求值，会导致表达式 $b(\beta) = \sum a_j \alpha^j$，其中 $\alpha$ 是 $f(x)$ 对应的根。这表明在转换后的设置上进行的攻击在数学上与在原始设置上的攻击是完全相同的。
• 迁移策略的失效： 分析确认，如果基于根的攻击在原始 PLWE 实例上由于高噪声或缺乏可区分性而失败，那么它在任何同构实例上也同样会失败。同构并不会“净化”噪声；相反，它保留了问题的底层难度。
• 特定根分析： 本文分析了求值根 $\beta$ 为 $0$、$1$ 或任意根的具体情况。在所有情况下，求值过程都简化为在对应的根处对原始多项式进行求值，从而证实没有获得任何优势。

意义
本文的结论是，关于全分裂 PLWE 实例安全性的直觉是正确的：如果基于根的攻击对初始 PLWE 实例无效，那么即使通过环同构将样本转移到潜在较弱的 PLWE 设置中，攻击依然会失效。

这一结果为全分裂 PLWE 实例的安全性提供了信心来源，这类实例因其效率（例如在数论变换 NTT 中）在密码学构建中非常常见。这项工作有效地排除了“同构迁移”作为针对这些特定实例生成新攻击手段的可行路径。作者指出，虽然该分析针对的是全分裂多项式，但它涵盖了绝大多数具有密码学相关性的 PLWE 实例。本文并不声称解决了非全分裂实例的安全性或其他攻击向量（如引言中提到的 Stickelberger 理想攻击）的问题，而是巩固了对全分裂领域内基于根的攻击的理解。