An alternative approach towards attacks against fully-split PLWE instances

Technical Summary: An Alternative Approach towards Attacks against Fully-Split PLWE Instances

Problem Statement
The Polynomial Learning With Errors (PLWE) problem is a cornerstone of post-quantum cryptography, often favored for its efficiency over Ring-LWE due to structured algebraic properties. However, this structure introduces potential vulnerabilities. Previous works, notably [5, 6] and generalized in [2], introduced "root-based attacks" that exploit the existence of specific polynomial factors (known as $n$-ideal factors, $x^n - a$) over finite fields. These attacks utilize evaluation homomorphisms and trace operators to distinguish PLWE samples from uniform distributions.

While [2] generalized these attacks to polynomials factorizing over field extensions, a critical open question remained: Could an attacker bypass the lack of vulnerable factors in a "safe" PLWE instance by mapping it via a ring isomorphism to a "vulnerable" instance (one possessing suitable $n$-ideal factors), performing the attack there, and inferring the security of the original instance? This paper investigates whether such a migration strategy via isomorphisms offers a meaningful advantage against fully-split PLWE instances.

Methodology
The authors employ a rigorous algebraic approach to analyze the feasibility of transferring PLWE samples between different polynomial rings. The methodology proceeds in two main phases:

1. Generalization of Arbitrary Factorization: The paper first explores extending root-based attacks to polynomials without $n$-ideal factors. By utilizing Lemma 1, the authors demonstrate that trace operators can be defined over arbitrary irreducible factors. However, they show that the success probability of such attacks is heavily dependent on the number of zero-valued coefficients in the factor, which is typically low for arbitrary polynomials, rendering the attack impractical in the general case.

2. Isomorphism Analysis in Fully-Split Settings: The core of the work focuses on the "isomorphism approach." The authors consider two polynomials, $f(x)$ and $g(x)$, both of degree $N$ and irreducible over $\mathbb{Z}[x]$, which share the same "factorization structure" over $\mathbb{F}_q$ (i.e., they decompose into irreducible factors of the same degrees).

   • Construction: Using the Chinese Remainder Theorem, they construct an explicit isomorphism $\psi$ between the rings $R_q = \mathbb{F}_q[x]/(f(x))$ and $R'_q = \mathbb{F}_q[x]/(g(x))$. In the fully-split case (where both polynomials factor completely into linear terms), this isomorphism is represented by the product of Vandermonde matrices: $\psi = V_g^{-1} \cdot V_f$.
   • Distortion Analysis: The authors analyze the effect of applying this isomorphism to PLWE samples followed by an evaluation at a root $\beta$ of $g(x)$. They prove that the resulting evaluation is mathematically equivalent to evaluating the original sample at a corresponding root $\alpha$ of $f(x)$.
   • Uniqueness Proof: A significant portion of the methodology involves proving that any ring isomorphism between such fully-split polynomial rings must take this specific form (composition of evaluation homomorphisms and the constructed isomorphism). This is established through Lemmas 2, 3, and 4, and Theorem 1.

Key Contributions

• Formal Proof of Isomorphism Invariance: The paper provides a formal proof that for fully-split PLWE instances, any attempt to migrate samples to a vulnerable setting via a ring isomorphism does not yield new vulnerabilities. The noise (error) introduced by the isomorphism distorts the samples such that the resulting distinguishability conditions are identical to those of the original instance.
• Characterization of Ring Isomorphisms: The authors characterize the complete set of isomorphisms between fully-split polynomial rings, showing they are uniquely determined by the mapping of roots. This proves that no "hidden" isomorphism exists that could bypass the noise distortion.
• Extension to Arbitrary Factorization: The work clarifies that while root-based attacks can theoretically be applied to polynomials without $n$-ideal factors, the lack of structural constraints (specifically the number of zero coefficients) severely limits their success probability, effectively closing the door on this generalization as a practical threat.

Results

• Noise Distortion: The application of an isomorphism $\psi$ followed by an evaluation at a root $\beta$ of $g(x)$ results in the expression $b(\beta) = \sum a_j \alpha^j$, where $\alpha$ is the corresponding root of $f(x)$. This demonstrates that the attack on the transformed setting is mathematically identical to the attack on the original setting.
• Failure of the Migration Strategy: The analysis confirms that if a root-based attack fails on the original PLWE instance (due to high noise or lack of distinguishability), it will also fail on any isomorphic instance. The isomorphism does not "clean" the noise; rather, it preserves the underlying difficulty of the problem.
• Specific Root Analysis: The paper analyzes specific cases where the evaluation root $\beta$ is $0$, $1$, or an arbitrary root. In all cases, the resulting evaluation reduces to the evaluation of the original polynomial at a corresponding root, confirming that no advantage is gained.

Significance
The paper concludes that the intuition regarding the security of fully-split PLWE instances is correct: if root-based attacks are unsuccessful against an initial PLWE instance, they will remain unsuccessful even if the samples are transferred to a potentially weaker PLWE setting via ring isomorphisms.

This result provides a source of confidence for the security of fully-split PLWE instances, which are common in cryptographic constructions due to their efficiency (e.g., in Number Theoretic Transforms). The work effectively rules out the "isomorphism migration" as a viable vector for generating new attacks against these specific instances. The authors note that while this analysis is specific to fully-split polynomials, it covers the vast majority of cryptographically relevant PLWE instances. The paper does not claim to solve the security of non-fully-split instances or other attack vectors (such as the Stickelberger ideal attacks mentioned in the introduction), but rather solidifies the understanding of root-based attacks within the fully-split domain.