An alternative approach towards attacks against fully-split PLWE instances Iván Blanco Chacón 1 , Raúl Durán Díaz 2 , and Rodrigo Martín Sánchez-Ledesma 3,4 Departamento de Física y Matemáticas, Universidad de Alcalá, Spain [email protected] 2 Departamento de Automática, Universidad de Alcalá, Spain [email protected] 3 Departamento de Álgebra, Universidad Complutense de Madrid, Spain [email protected] 4 Indra Sistemas de Comunicaciones Seguras, Spain [email protected]
arXiv:2607.01340v1 [cs.CR] 1 Jul 2026
1
Abstract. In the present work we address some key questions regarding the generalization of root-based attacks presented in [2]. In particular, we analyze potential root-based attacks extensions via the construction of explicit isomorphisms from vulnerable instances, and provide a formal proof that this approach will not yield any new vulnerabilities under a fully-split setting. To do so, we first construct an explicit isomorphism between fully-split polynomial rings and polynomial rings where previous attacks apply and show that the application of such an isomorphism will always distort the samples in a way that the resulting samples cannot be used to distinguish. Then, we prove that any isomorphism between fully-split polynomial rings must be of the form of the constructed isomorphism.
Keywords: PLWE · Root-based attacks · Isomorphisms
1
Introduction
The Ring Learning With Errors problem (RLWE) and the Polynomial Learning With Errors problem (PLWE) have become the most important paradigms in the quest of achieving postquantum security. Some of the strongest theoretical clues pointing in this direction are the worst case-average case reductions from an approximate version of the Shortest Vector Problem on ideal lattices to the RLWE problem, established in [7], and to the PLWE problem over power-of-two cyclotomic polynomials, established in [10]. An important debate in cryptography in general, and post-quantum cryptography in particular, is the one contrasting efficiency with security. Cryptographic schemes must obviously be secure, but they need also be practical and usable. This dichotomy is not a stranger to lattice-based cryptography, of which both PLWE and RLWE are representatives. Within lattices, this dilemma is represented by the definition of both unstructured and structured schemes. By structured, it is meant that additional algebraic structure is added to the scheme, whereas unstructured schemes normally rely on lighter mathematical constructions. The definition of these structured paradigms permits cryptographic schemes employing such structures to enjoy a number of privileges, most notably related to better performances and smaller cryptographic sizes. But the cost of doing so is the addition of the aforementioned heavy algebraic structure, which could potentially turn out to be the source of new attacks, and gives rise to some important questions: are there attacks that can effectively target this additional structure? Do they improve the best known attacks against LWE? It was precisely this line of thought that the works of [5,6] explored. In them, the authors introduce a general framework to exploit the algebraic structure of PLWE schemes in order to mount decisional attacks. In particular, evaluation homomorphisms are constructed from a chosen root α ∈ Fq of the polynomial f (x) that is at the heart of the PLWE instance. Then, this map is applied to every sample given and a number of distinguishability conditions giving rise to different attacks do appear. Each distinguishing condition defines a specific attack. The work of [8] studied the likelihood of some of the attacks presented in [5]. A statistical analysis showed that the distribution of the setting potentially vulnerable to the attacks under consideration represented a negligible share of the total instances, thus seemingly closing the door to this approach. However, it is worth noting that this analysis did not include the attack referred to as Unbounded Small Values Attack [2], which newer analysis have found to be the most likely to
2
I. Blanco Chacón, R. Durán Díaz, R. Martín Sánchez-Ledesma
be applicable. The latter work further included new techniques for decisional attacks against the algebraic structure. In particular, [2] provides two advances: first, a deeper analysis of the previously defined attacks by both refining the given success probabilities and introducing another analysis in terms of a posteriori probabilities. The refined bounds on the success probabilities of the attacks require introducing new techniques on them, to make them useful. Second, their work generalized the attacks so that they become applicable to polynomials whose factorization is defined only over extensions of Fq . In other words, the proposed attacks work for any root belonging to a finite extension E of Fq of degree k, for any k ≥ 1. The key ingredient is the trace operator defined over a field extension, in order to complement the evaluation homomorphism. The latter allows the transfer of the setting to Fq but remark that so does the former: actually the trace operator is affine over any extension E of Fq , i.e., it respects the sum of elements in E and the product by elements of the base field Fq . The definition of higher degree extension is done under a special kind of factorization, named k-ideal factors (see Definition 2). They represent polynomials that have factors of the form xk − a, where a ∈ Fq . While the limitation to roots of ideal factors is indeed an applicability restriction, it is important to note that, in practice, most cryptographically relevant PLWE schemes follow this type of factorization. This is due to the fact that ideal factors are preferred for efficiency purposes, specially related to polynomial multiplications (consider, for example, the well-known Number Theoretic Transform whose applicability relies precisely on the existence of such ideal factors). This framework provides an initial guess to the questions previously asked: Are there attacks effectively targeting this additional structure? The answer is Yes, since these attacks are built precisely from the algebraic structure of the PLWE paradigm, and cannot be migrated to purely LWE settings. The next pending question was Do they improve the best known attacks against LWE? Really, most of the attacks defined poses almost no threat to cryptographically relevant PLWE instances, either due to the likelihood of the attacks being applicable (e.g. Bounded Small Values Attack ), or the negligible success probability of them (e.g. Small Errors Attack ). However, in [1,3] comparative analysis between maximal real and cyclotomic polynomials showed that, while still negligible, the Unbounded Small Value Attack has a much more meaningful impact radius, when compared with the other attacks. More so, this attack was the only one to be prone to positive attack results. These findings could give an initial suggestion that there is not a meaningful advantage in trying to target the additional algebraic structure, at least through this approach. There are other more recent attacks targeting the RLWE that circumvent the RLWE/PLWEequivalence. The most prominent one is [4], which drastically reduces the γ-approximation factor for the underlying SVP keeping polynomial quantum complexity. This attack only applies to the ring of integers of cyclotomic number fields (or sub-lattices therein) and uses a number of relations of the so called Stickelberger ideal. It is a much interesting question whether this attack can be applied to arbitrary Abelian sub-extensions of cyclotomic rings. 1.1
Our contributions
The present work, pursuing the same research line, intends to answer two related questions that remain still open. The first one concerns the applicability of these attacks to polynomials with factorizations beyond plain k-ideal factors. In Section 3, it will be shown that, in theory, the attacks defined in [2] can indeed be transferred to this more general framework. However, in practice, this generalization to arbitrary factorization impacts negatively the applicability of the attacks and the resulting success probabilities. The second and more important question, comes from the idea of migrating to settings that might have more favorable conditions. Formally, the notion behind this idea is to employ isomorphisms of finite fields to migrate from the target PLWE to a vulnerable setting, apply a distinguishability attack there, and infer the distribution of the original PLWE scheme from that attack. The drawback that one could think of when considering this idea is the fact that such transference of samples from one setting to another might potentially increase the noise of the samples so as to spoil completely the distinguishability in the favorable PLWE setting.
An alternative approach towards attacks against fully-split PLWE instances
3
This work investigates a natural way to perform such an attach and thus backs up this intuition: Section 4 will show precisely that no isomorphism between PLWE instances provides any meaningful advantage over attacking the original PLWE instance. In order to pursue this idea, a specific isomorphism between PLWE distributions will be constructed and it will be proven that the generated noise increase is given by the powers of the roots of the original PLWE setting. Moreover, it will be proven that this specific type of isomorphism is the only possible one between PLWE settings. While this analysis is only done for PLWE polynomials which are fully split (i.e. they factor completely in Fq ), this remains the case for most cryptographically relevant PLWE instances. These results will be presented in Appendix A. In conclusion, our work clearly backs up the intuition that if any root-based attack against the initial PLWE instance is unsuccessful, so will also be any other attack even when the samples are transferred to a new (potentially weaker) PLWE setting: actually, the noise increase will be high enough so as to render useless attacks otherwise known to be successful under such setting.
2
Preliminaries
This section provides an overview of the PLWE problem, and the essentials about root-based attacks needed to comprehend the following sections. We begin with the definition of the PLWE distribution. Definition 1 (PLWE distribution). Let q be a rational prime, f (x) ∈ Z[x] a monic irreducible polynomial and Of the associated quotient ring Z[x]/(f (x)). Let χ be a discrete random distribution with values in Of /qOf . For s ∈ Of /qOf , we define the PLWE distribution Bs,χ as the distribution over Of /qOf × Of /qOf obtained by sampling an element a in Of /qOf uniformly at random, sampling an element e from χ, and returning the pair (a, a · s + e) ∈ (Of /qOf × Of /qOf ). Next the definition of what will be referred to as a n-ideal factor: Definition 2. Let q be a rational prime. Let f (x) ∈ Z[x] be a monic irreducible polynomial of degree N . Suppose that a ∈ Fq has small multiplicative order in F∗q and that there exists 1 ≤ n < N such that the (irreducible) polynomial xn − a ∈ Fq [x] divides f (x) mod q. We call xn − a a n-ideal factor of f (x) mod q. The following setting will be assumed for the introduction of root-based attacks: Let q be a prime and let f (x) ∈ Z[x] a polynomial over Z[x] of degree N satisfying Definition 2 above. Denote Rq the ring Rq := Fq [x]/(f (x)) and Rq,0 ⊆ Rq the sub-ring Rq,0 := {p(x) ∈ Rq : p(α) ∈ Fq }, where α is a root of f (x) in a certain field extension, to be defined in the next paragraphs. For the PLWE distribution, we assume a Gaussian distribution of mean 0 and a certain variance σ 2 . Define p0 as the probability of any random Gaussian variable with the above distribution to lie inside [−2σ, 2σ]. The value p0 is known to be 0.954499, up to 5 digits of precision. The general framework of root-based distinguishability attacks of [2] can be summarized as follows: 1. Let f (x) be a polynomial satisfying the conditions in Definition 2 and let α be a root of such polynomial f (x). 2. Assume we have a linear map Φα : Rq → Fq . 3. Given samples (ai (x), bi (x) = s(x) · ai (x) + ei (x)), consider them as elements of Rq . Since Φα is linear, the following equality holds Φα (ei (x)) = Φα (bi (x) − s(x) · ai (x)) = Φα (bi (x)) − Φα (s(x) · ai (x)). 4. Accordingly, fixing a guess for s(x), compute the value Φα (ei (x)) associated to each sample (ai (x), bi (x)). 5. Perform certain distinguishability actions over the tentative evaluated errors to get a distinguishability feature.
4
I. Blanco Chacón, R. Durán Díaz, R. Martín Sánchez-Ledesma
The established conditions regarding f (x) ensure that xn − a defines a field extension E of degree n ≥ 1 over Fq . This extension defines the trace operator TrE|Fq : E → Fq of E. Moreover, any root α of xn − a defines an evaluation ring homomorphism ϕα : Rq → E. Composing the maps described, we define Φα as 1 Φα := Tr ◦ϕα , n which is certainly linear since the trace operator is additive. Note that even in the case n = 1, the map is still well defined, as the trace operator becomes the identity over Fq . The particular feature used to distinguish the tentative evaluated errors will define each of the attacks. Three different attacks will be specified: 1. Small Set Attack : Analyze the set of values resulting from the application of the map Φα to the set of all possible error values when this set has small cardinality. 2. Bounded Small Values Attack : Analyze the smallness of the set of values resulting from the application of the map Φα to a distribution of error values constrained to a certain interval. 3. Unbounded Small Values Attack : Analyze the smallness of the set of values resulting from the application of the map Φα to a distribution of error values not constrained to any particular interval. 2.1
Small Set Attack
The Small Set Attack sub process is defined as follows: A set of samples C = {(ai (x), bi (x))}M i=1 ∈ Rq,0 × Rq A look-up table Σ of values appearing in n1 Tr(b(α) − a(α) · s) with probability ≥ pr0 Output: PLWE, or NOT PLWE, or NOT ENOUGH SAMPLES Input:
– G := ∅ – for g ∈ Fq do • for (ai (x), bi (x)) ∈ C do / Σ then next g ∗ if n1 (Tr(bi (α)) − ai (α)g) ∈ • G := G ∪ {g} – if G = ∅ then return NOT PLWE – if |G| = 1 then return PLWE – if |G| > 1 then return NOT ENOUGH SAMPLES Algorithm 1. Attack based on the size of the set of possibilities for the evaluated errors
However, due to the limit in the success probabilities of this algorithm, given in [2, §4.2, §4.3], the following algorithm was defined, which we will refer to as Extended Small Set Attack : A collection of samples S = {(ai (x), bi (x))}M i=1 ∈ Rq,0 × Rq A choice M0 for the number of samples of the sub-process Output: A guess for the distribution of the samples, either PLWE or UNIFORM Input:
0r – T := ⌈⌊M/M0 ⌋ · pM ⌉ 0 – C := 0 – for j ∈ {0, . . . , ⌊M/M0 ⌋ − 1} do
(j+1)·M
0 • result := SmallSetAttack Sj := {(ai (x), bi (x))}i=j·M0 +1 ∗ if result ̸= NOT PLWE then · C := C + 1 – if C < T then return UNIFORM – else return PLWE
Algorithm 2. Algorithm for Extended Small Set Attack
An alternative approach towards attacks against fully-split PLWE instances
5
Proposition 1. [2] Assume |Σ| < q, and let M be the number of samples given, M0 the number of samples employ for each sub process, T the threshold of the attack and r the order of the term a of the ideal factor xn − a. Then, we have that 1. If the samples are PLWE, Algorithm 2 guesses correctly the distribution of the samples with probability at least 0r 1 − F (T − 1, ⌊M/M0 ⌋ , pM ) 0 2. If the samples are uniform, Algorithm 2 guesses correctly the distribution of the samples with probability at least M F (T − 1, ⌊M/M0 ⌋ , 1 − (|Σ|/q) 0 ) where F is defined as the Cumulative Binomial Function 2.2
Bounded Small Values Attack
The Bounded Small Values Attack sub process is defined in Algorithm 3: Input: A collection of samples C = {(ai (x), bi (x))}M i=1 ⊆ Rq,0 × Rq Output: A guess g ∈ Fq for Tr(s(α)), or NOT PLWE, or NOT ENOUGH SAMPLES – G := ∅ – for g ∈ Fq do • for (ai (x), bi (x)) ∈ C do ∗ if n1 (Tr(bi (α)) − ai (α)g) ∈ / [− 4q , 4q ) then next g • G := G ∪ {g} – if G = ∅ then return NOT PLWE – if G = {g} then return g – if |G| > 1 then return NOT ENOUGH SAMPLES Algorithm 3. Attack based on the size of error values
However, due to the limit in the success probabilities of this algorithm, given in [2, §5.2, §5.3], the following algorithm was defined, which we will refer to as Extended Small Values Attack : A collection of samples S = {(ai (x), bi (x))}M i=1 ∈ Rq,0 × Rq A choice M0 for the number of samples of the sub-process Output: A guess for the distribution of the samples, either PLWE or UNIFORM Input:
0 – T := ⌈⌊M/M0 ⌋ · pM 0 ⌉ – C := 0 – for j ∈ {0, . . . , ⌊M/M0 ⌋ − 1} do
(j+1)·M
0 • result := SmallValueAttack Sj := {(ai (x), bi (x))}i=j·M0 +1 ∗ if result ̸= NOT PLWE then · C := C + 1 – if C < T then return UNIFORM – else return PLWE
Algorithm 4. Algorithm for Extended Small Value Attack
Proposition 2. [2] Assume 2σ < 4q , let M be the number of samples given, M0 the number of samples employ for each sub process, and T the threshold of the attack. Then, we have that 1. If the samples are PLWE, Algorithm 4 guesses correctly the distribution of the samples with probability at least 0 1 − F (T − 1, ⌊M/M0 ⌋ , pM 0 )
6
I. Blanco Chacón, R. Durán Díaz, R. Martín Sánchez-Ledesma
2. If the samples are uniform, Algorithm 4 guesses correctly the distribution of the samples with probability at least 1 1 F (T − 1, ⌊M/M0 ⌋ , 1 − ( ± )M0 ) 2 2q 1 is defined as estabwhere F is defined as the Cumulative Binomial Function and the term 21 ± 2q lished in [2, Lemma 1].
2.3
Unbounded Small Values Attack
The Unbounded Small Values Attack is defined in Algorithm 5: A collection of samples S := {(ai (x), bi (x))}ℓi=1 ⊆ Rq,0 × Rq according to a certain distribution. A value δ > 0. Output: A guess into the distribution of the samples, either PLWE or UNIFORM. Input:
l m – T := 12 ℓ · q + 2ℓ · δ ± ℓ · 1 − 1q – C := 0 – for g ∈ Fq do • for (ai (x), bi (x)) ∈ S do ∗ if n1 (Tr(bi (α)) − ai (α)g) ∈ [− 4q , 4q ) then · C =C +1 – if C < T then return UNIFORM – else return PLWE Algorithm 5. Unbounded Small Values Attack
Proposition 3. [2] Assume 2σ ≥ 4q , let M be the number of samples given, M0 the number of samples employ for each sub process and T the threshold of the attack. Then, we have that 1. If the samples are PLWE, Algorithm 5 guesses correctly the distribution of the samples with probability equal to ℓ X 1 1 1 1 − F T − i − 1, ℓ · (q − 1), ± · P B ℓ, + δ = i 2 2q 2 i=0 2. If the samples are uniform, Algorithm 5 guesses correctly the distribution of the samples with probability equal to 1 1 F T − 1, ℓ · q, ± 2 2q where F is defined as the Cumulative Binomial Function, B is the Binomial Distribution and the 1 term 12 ± 2q is defined as established in [2, Lemma 1].
3
Generalization to arbitrary factorization of the polynomial
3.1
Overview
The results presented in [5], [6] and later [2] have allowed to present versions of attacks against the decision version of PLWE, in which information about a root α of an n-degree polynomial f (x) ∈ Fq [x] was exploited, regardless of the finite field extension of Fq in which the root lived. But, as laid out in Section 2, all of the attacks had a common requirement: for an N -degree polynomial f (x) to have a n-ideal factor, i.e., for f (x) to have xn − a, a ∈ Fq , as a factor in Fq [x]. In the sequel we present two attempts to completely generalize the root-based attack setting, with the aim of applying it (if proved successful) to any arbitrary polynomial factorization. This approach could render this attack applicable to any and every single PLWE instance, thus representing a practical constraint when considering the deployment of PLWE constructions. In other words, this generalization would force every parametrization of PLWE to consider these attacks, and check that for no root of f (x), any of the attacks laid out in this work is successful. In particular, we will study two approaches, with the following contributing results:
An alternative approach towards attacks against fully-split PLWE instances
7
1. First, a note on how to further expand the attacks presented in [2], via lifting the restriction of working only with n-ideal factors, thus allowing any suitable factor to be considered for the distinguisher. 2. More importantly, an analysis of the isomorphism approach, which intuitively hopes to transform samples from a safe setting onto a (hopefully more) favorable one in order to mount the distinguisher attacks over the latter. This approach is of great significance as, if achievable, it would create a new source of attacks to settings considered otherwise safe so far. (Un)fortunately, we will prove that any attempt at migrating the setting will yield unsuccessful results, providing an additional source of confidence to, at least, fully-split PLWE instances. We deal now both cases in turn. 3.2
Consideration of arbitrary factorization
In previous works, such as [2], it is assumed that every polynomial f (x) has an n-ideal factor, with 0 < n < N. In the finite field extension case this factor was actually not necessary for the attacks to succeed (except for n = 1, where it is indeed needed in order to ensure the selected root belonged to Fq ). It was merely a device to maximize the distinguishability features of the attack in order to increase the chances of its success. In the sequel, we provide a high-level overview of how the proposed attacks would work, should the polynomial f (x) have no n-ideal factors modulo q. To begin with, consider the following Lemma 1. Let g(x) = xn − an−1 xn−1 − · · · − a0 be irreducible over Fq , and α ∈ Fqn be a root of g. Let f (x) ∈ Fq [x] of degree N and irreducible over Z[x] be a polynomial such that g(x) is a factor of f (x) over Fq [x]. For each j < N , let βj = Tr(αj ) ∈ Fq . Then 0 ≤ j < n, Tr(αj ), βj = P n−1 k=0 ak βj−n+k , n ≤ j < N. Proof. The recurrence formula is extracted directly from g(x), under multiplication by powers of α. ⊔ ⊓ The PLWE problem is defined over the ring Rq := Fq [x]/(f (x)). Given an error polynomial PN −1 e(x) = i=0 ei xi in Rq , we can compute the trace of such a polynomial evaluated at the root α with the help of Lemma 1 as follows Tr(e(α)) =
N −1 X
ei Tr(αi ) =
i=0
N −1 X
e i βi .
i=0
Now, the PLWE problem demands that each coefficient ei be sampled from a discretized Gaussian random variable reduced modulo q of mean 0 and variance σ 2 . Observe that, once α is fixed, the traces of its powers, which live in Fq , are fixed as well, so that Tr(e(α)) can be seen as a Gaussian random variable of mean 0 and variance σ̄ 2 =
N −1 X
σ 2 βi2 .
i=0
Therefore, all the attacks presented in Section 2 should succeed in the same manner, just considering this new expression for the distinguishability features. It is important to note that, though indeed not needing a n-ideal factor for the execution of the attack, the success probability of each of them is closely tied to the number of 0-valued coefficients the n-degree factor of f has. Informally, the higher this number, the greater the chances of a successful attack.
4
An (unsuccessful) way of avoiding the problem: isomorphism of rings
4.1
Reduction from arbitrary factorization to an n-ideal factor
Despite the efforts to provide a totally generalized result, in which every polynomial could have the possibility of being affected by these attacks, it is important to remark that the chances that a polynomial f (x) without an n-ideal factor undergoes a successful attack are indeed slim.
8
I. Blanco Chacón, R. Durán Díaz, R. Martín Sánchez-Ledesma
This is due to the fact that, as noted above, the number of non-zero coefficients of the selected factor of f (x) has a huge impact upon the success probability of an attack against an (f, q, σ)-PLWE instance. In order to increase the efficiency of the evaluation-at-α homomorphism we propose yet another transformation allowing us to migrate to a more favorable setting in which we can find vulnerable n-ideal factors. To this end, we propose the concept of factorization structure according to the following Definition 3. Two N -degree separable polynomials, f (x) and g(x) are said to have the same Qℓ2 Qℓ1 gi (x), fi (x), and g(x) = i=1 factorization structure in Fq [x] if their factorizations, f (x) = i=1 with each fi (x), gi (x) irreducible over Fq [x], are such that ℓ1 = ℓ2 = ℓ, and for any i ∈ {1, . . . , ℓ}, there exists j ∈ {1, . . . , ℓ} such that fi (x) and gj (x) have the same degree (and the other way around). In other words, there exists a one-to-one correspondence between the irreducible factors of f (x) and g(x) of the same degree. We can then proceed to the following Proposition 4. Let f (x), g(x) ∈ Z[x] be monic polynomials of degree N irreducible in Z[x] having the same factorization structure in Fq [x]. Then, there exists an isomorphism between the rings Rq := Fq [x]/(f (x)) and Rq′ := Fq [x]/(g(x)). Proof. By the Chinese Remainder Theorem and the fact that fi (x), gi (x) are irreducible over Fq , Qℓ Rq = Fq [x]/( i=1 fi (x)) ≃ ⊕ℓi=1 Fq [x]/(fi (x)) ≃ ⊕ℓi=1 Fqdeg(fi (x)) Qℓ Rq′ = Fq [x]/( i=1 gi (x)) ≃ ⊕ℓi=1 Fq [x]/(gi (x)) ≃ ⊕ℓi=1 Fqdeg(gi (x)) and, since the polynomials have the same factorization structure, both will give rise to a direct product of ℓ finite fields of the same degree. Since all finite fields with the same number of elements are isomorphic, the result follows. ⊔ ⊓ 4.2
Transferring the setting of the attacks
Considering the previous results, we describe a new setting for the attacks. Let f (x) be a monic polynomial of degree N irreducible over Z[x], q a prime, and G a Gaussian distribution of mean 0 and variance σ 2 . With these elements we have our (f, q, σ)-PLWE instance. Now, let g(x) be also a monic polynomial of degree N irreducible over Z[x] that has an n-ideal factor in Fq (with an independent term of small multiplicative order) having the same factorization structure as f (x). Then, we apply the following steps: – First, every (f, q, σ)-PLWE sample is transformed into a (g, q, σ)-PLWE sample via the existing isomorphism between Rq := Fq [x]/(f (x)) and Rq′ := Fq [x]/(g(x)) by virtue of Proposition 4. This transformation should not affect the distinguishability of the induced distribution in the sense that if the distinguisher succeeds in the first setting, so will it succeed in the second, which is critical to the applicability of the presented transformation. – Then, we use the homomorphism derived from the evaluation at root α of the n-ideal factor xn − a of g(x) to migrate our samples into Fqn . – From that point on, we are entitled to apply any of the attacks referenced in Section 2 in order to create a successful decisional attack, by resorting either to the Fq attacks, or applying the trace over Fqn for n > 1. In short, we could transfer the attacks to a more favorable setting, namely, a (g, q, σ)-PLWE instance in which the polynomial g(x) has a suitable n-ideal factor if it happens to exist. It is noticeable that the existence of such polynomials g(x) depends only upon the parameters (f, q), so that they could be precomputed (in case they exist) and stored in advance. 4.3
The fully-split setting and a generalization beyond it
However nice and promising as it may sound, we will show in the sequel that the previous results lead us again to a blind alley regarding the possibility of achieving new, more powerful attacks. To begin with, we consider the fully-split setting, namely, a setting where both f (x) and g(x) decompose into linear factors over Fq and the roots, say (α1 , . . . , αN ), (β1 , . . . , βN ), respectively,
An alternative approach towards attacks against fully-split PLWE instances
9
are distinct. For this case, we give in Appendix A a very detailed account about how to construct an explicit family of isomorphisms, between Rq and Rq′ that, moreover, happen to be unique. The result laid out in the Appendix just referred to shows that the application of an isomorphism, when composed with a subsequent evaluation at a certain root β, yields precisely the evaluation of the original samples at the corresponding root α (which will depend on the choice of β and the isomorphism). In other words, the attacks over the transferred setting reduce to the original setting and so no advantage is gained with the transference. Therefore, in spite of all nice (possibly of independent interest) results supplied therein, Section A.1 and Section A.2 give us sufficient evidence that, in the fully-split setting, the use of isomorphisms of rings do not provide us with new ways for mounting successful attacks against PLWE instances via the use of roots of (fully-split) polynomials. However this is not the end of the story: We can go a step further by analyzing how the combination of such morphisms look like. We need a number of lemmas, beginning with a simple result regarding the composition of homomorphisms: Lemma 2. Let A, B and C be rings. If there exists a ring isomorphism ψ : A → B, then every ring homomorphism η : A → C arises as the composition of ψ and a certain ring homomorphism ξ : B → C. Proof. Choose a homomorphism η : A → C. Then, since ψ : A → B, ψ −1 exists and is a ring isomorphism B → A. Then, η ◦ ψ −1 is a ring homomorphism ξ : B → C. Therefore, η = ξ ◦ ψ. ⊔ ⊓ The next result states that the only homomorphisms from polynomial rings are the evaluation homomorphisms: Lemma 3. Let q be a prime and f (x) ∈ Fq [x] a polynomial which factors over Fq [x]. Then, the only ring homomorphisms ϕ : Fq [x]/(f (x)) → Fkq are the evaluation homomorphisms evαi , where k denotes the degree of the irreducible polynomial in Fq [x] which has αi as a root (i.e. the degree of the extension defined by αi over Fq ). Proof. Any ring homomorphism satisfies ϕ(1) = 1 hence ϕ|Fq = Id. Further, as ϕ is linear and PN −1 i compatible with multiplications, we have that for any polynomial class g(x) = i=0 gi x ∈ Fq [x]/(f (x)) N −1 X ϕ(g(x)) = gi ϕ(x)i = g(ϕ(x)), i=0
so that ϕ is determined by its image on the class x. But since f (x) = 0, necessarily ϕ(f (x)) = f (ϕ(x)) = 0 and hence ϕ(x) = αi for some i among the roots of degree k of f (x). ⊓ ⊔ The next lemma states that the composition of any ring isomorphism between polynomial rings and an evaluation homomorphism yields an evaluation homomorphism. Lemma 4. Let f (x) and g(x) be two polynomials with the same factorization structure. Let ψ be a ring isomorphism ψ : Fq [x]/(f (x)) → Fq [x]/(g(x)) and ϕ := evβi be an evaluation homomorphism ϕ : Fq [x]/(
QN
k i=1 (x − βi )) → Fq
for a root βi of g(x) of degree k over Fq . Then, φ := evβi ◦ψ is an evaluation homomorphism QN φ : Fq [x]/( i=1 (x − αi )) → Fkq over a certain root αji of f (x) of degree k over Fq . Proof. It is a direct consequence of Lemmas 2 and 3.
⊔ ⊓
Together, we have the following corollary: Corollary 1. The equality evαji = evβi ◦ψ holds for any ring isomorphism ψ between polynomial rings and αji and βi roots of f (x) and g(x) with the same degree over Fq , respectively.
10
I. Blanco Chacón, R. Durán Díaz, R. Martín Sánchez-Ledesma
Observe that Corollary 1 applies to any ring and not just to Fq . Moreover, the root-based attack on k > 1 uses a map that is the composition of the evaluation at a certain root (which is now a homomorphism to the finite extension Fqk ) and the trace operator defined over such extension. Thus, (Tr ◦ evβi ) ◦ ψ = Tr ◦(evβi ◦ψ) = Tr ◦ evαji (1) and one falls back precisely to the original root-based attack. Note that this result captures in full generality the nature of the proposed attack extension: the application of the isomorphism to the samples in the original (allegedly robust) setting plus the evaluation at roots of the vulnerable PLWE instance. And the proof shows that this is precisely the same as evaluating the original samples at the corresponding root of the original instance. In conclusion, this result allows us to generalize the analysis to instances beyond fully-split ones, completely characterizing the behavior when k > 1, and, in particular, corroborates the intuition that using isomorphisms in order to transfer to another (potentially weaker) setting cannot provide new, more powerful attacks over any type of PLWE instances, whether fully-split ones or beyond.
References 1. Ahola, J., Blanco-Chacón, I., Bolaños, W., Haavikko, A., Hollanti, C., Sánchez-Ledesma, R.M.: Fast multiplication and the PLWE-RLWE equivalence for an infinite family of maximal real subfields of cyclotomic fields. Designs, Codes and Cryptography 93(8), 2947–2969 (2025). https://doi.org/10. 1007/s10623-025-01601-3 2. Blanco-Chacón, I., Durán-Díaz, R., Martín Sánchez-Ledesma, R.: A Generalized Approach to Rootbased Attacks against PLWE. Cryptography and Communications. Special Issue: Quantum-Resistant Cryptography (QuRCry) pp. 1–45 (2025). https://doi.org/10.1007/s12095-025-00849-9 3. Bolaños, W., Haavikko, A., Martín Sánchez-Ledesma, R.: A fast multiplication algorithm and RLWEPLWE equivalence for the maximal real subfield of the 2r ps -th cyclotomic field. Advances in Mathematics of Communications 21, 212–238 (2026). https://doi.org/10.3934/amc.2025051 4. Cramer, R., Ducas, L., Wesolowski, B.: Short Stickelberger Class Relations and Application to IdealSVP. In: Coron, J., Nielsen, J.B. (eds.) Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part I. Lecture Notes in Computer Science, vol. 10210, pp. 324–348 (2017). https://doi.org/10.1007/978-3-319-56620-7_12 5. Elias, Y., Lauter, K.E., Ozman, E., Stange, K.E.: Provably Weak Instances of Ring-LWE. In: Gennaro, R., Robshaw, M. (eds.) Advances in Cryptology – CRYPTO 2015. pp. 63–92. No. 9215 in Lecture Notes in Computer Science, Springer Berlin Heidelberg, Berlin, Heidelberg (2015). https://doi.org/ 10.1007/978-3-662-47989-6_4 6. Elias, Y., Lauter, K.E., Ozman, E., Stange, K.E.: Ring-LWE Cryptography for the Number Theorist. In: Eischen, E.E., Long, L., Pries, R., Stange, K.E. (eds.) Directions in Number Theory. Association for Women in Mathematics Series, vol. 3, pp. 271–290. Springer International Publishing, Cham (2016). https://doi.org/10.1007/978-3-319-30976-7_9 7. Lyubashevsky, V., Peikert, C., Regev, O.: On Ideal Lattices and Learning with Errors over Rings. Journal of the ACM 60(6), 43:1–43:35 (November 2013). https://doi.org/10.1145/2535925 8. Peikert, C.: How (Not) to Instantiate Ring-LWE. In: Zikas, V., De Prisco, R. (eds.) Security and Cryptography for Networks. Lecture Notes in Computer Science, vol. 9841, pp. 411–430. Springer International Publishing, Cham (2016). https://doi.org/10.1007/978-3-319-44618-9_22 9. Rawashdeh, E.A.: A simple method for finding the inverse matrix of Vandermonde matrix. Matematički Vesnik 71(3), 207–213 (2019), http://www.vesnik.math.rs/landing.php?p=mv193.cap&name= mv19303 10. Stehlé, D., Steinfeld, R., Tanaka, K., Xagawa, K.: Efficient Public Key Encryption Based on Ideal Lattices. In: Matsui, M. (ed.) Advances in Cryptology – ASIACRYPT 2009. pp. 617–635. Springer Berlin Heidelberg, Berlin, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_36
A
The fully-split case
A.1
The fully-split case: Construction of an explicit isomorphism
Suppose that both f (x) and g(x) decompose into linear factors over Fq and the roots, (α1 , . . . , αN ), (β1 , . . . , βN ), respectively, are distinct. Then, we are able to construct an explicit family of isomorphisms between Rq and Rq′ . The particular family of isomorphisms constructed can be defined in three conceptual phases: – The isomorphism ϕ1 , derived from the CRT, ϕ1 : Rq → ⊕N i=1 Fq .
An alternative approach towards attacks against fully-split PLWE instances
11
– The coordinate change representation of elements in ⊕N i=1 Fq in terms of powers of the roots αi of f (x) to powers of the roots βi of g(x). Note that, since each coordinate is an element of Fq , it can be viewed as either an element of the powers of αi or βi , and therefore this map is just the identity. – The inverse isomorphism, ϕ−1 2 derived also from the CRT, ϕ2 : Rq′ → ⊕N i=1 Fq . Given a(x) ∈ Rq , then ϕ1 (a(x)) = (a(α1 ), . . . , a(αN )) that can be naturally described by means of the Vandermonde matrix of the roots of f (x) in Fq : Defining the vector a = (a0 , . . . , aN −1 ), we have ϕ1 (a(x)) = Vf · a, where 1 α1 · · · α1N −1 Vf = ... ... . . . ... , N −1 1 αN · · · αN
and, analogously, Vg for the Vandermonde matrix of the roots of g(x). Observe that by hypothesis, all the roots are distinct, so that both Vf and Vg are invertible over the field Fq . Therefore the identity I can be generated simply as I = Vg · Vg−1 . For the third step, we can consider now that ϕ2 can be described by means of Vg , so that the complete isomorphism can be eventually written as −1 −1 ϕ = ϕ−1 · Vf 2 ◦ I ◦ ϕ1 = ϕ2 ◦ ϕ1 = Vg
Before we continue, we provide two important properties of Vandermonde matrices. Proposition 5. Let Va and Vb be two invertible Vandermonde matrices. Then, the matrix Va−1 Vb has an identity vector as first column, namely, all coefficients are zero except the first one Proof. Let V a Vandermonde matrix. By definition, 1 1 1 0 .. = V · .. . . 1 If V is invertible, one has
0
1 1 1 0 V −1 · . = . .. .. 1
0
This means that the sum of each row of the inverse of a Vandermonde matrix is 0, except for the first row, which is 1. Then, the right product with another Vandermonde matrix (which has an all-1 first column), generates the desired result. ⊔ ⊓ Before proceeding let us recall the following Definition 4. The j-elementary symmetric polynomial in n variables is defined as X Ej (X1 , . . . , Xn ) = Xa1 Xa2 · · · Xaj , 1≤a1 <a2 <···<aj ≤n
with E0 (X1 , . . . , Xn ) = 1. We recall now a simple, yet useful lemma regarding elementary symmetric polynomials: Lemma 5. The sum of the elementary symmetric polynomials over variables X1 , . . . , Xn weighted by λ is equal to the evaluation at λ of the monic polynomial of roots X1 , . . . , Xn . In other words, n X
n−i
(−1)
i
· λ · En−i (X1 , . . . , Xn ) =
i=0
n Y
(λ − Xi ),
i=1
with E0 = 1 for any number of variables. Proof. Expanding the product of monomials of the polynomial P (t) = (t − X1 ) · · · (t − Xn ) and evaluating at λ yields the desired result. ⊔ ⊓
12
I. Blanco Chacón, R. Durán Díaz, R. Martín Sánchez-Ledesma
Based upon Definition 4, we denote Ej,k (X1 , . . . , Xn ) as the j-th elementary polynomial over the set of variables {X1 , . . . , Xn } \ {Xk }, namely, Ej,k (X1 , . . . , Xn ) := Ej (X1 , . . . , Xk−1 , Xk+1 , . . . , Xn ). Let us define now the polynomial Gk (λ; X1 , . . . , Xn ) := following
Qn
i=1,i̸=k (λ − Xi ). Then, we have the
Lemma 6. With the notations above, the following holds: n X
(−1)n−i · λi−1 · En−i,k (X1 , . . . , Xn ) = Gk (λ; X1 , . . . , Xn ),
i=1
for any k ∈ {1, . . . , n}. Proof. It suffices to expand the polynomial defined by Gk and apply Lemma 5, remembering the definition of Ej,k . ⊔ ⊓ Proposition 6. The inverse of a Vandermonde matrix 1 ξ1 · · · ξ1n−1 V = ... ... . . . ... ,
1 ξn · · · ξnn−1 is (when invertible) of the form En−i,j (ξ1 , . . . , ξn ) Qn l=1 (ξj − ξl ) · l=j+1 (ξl − ξj )
−1 Vi,j = (−1)i+j · Qj−1
= (−1)i+j ·
En−i,j (ξ1 , . . . , ξn ) Qn , l = j or k = j, l<k (ξk − ξl )
where, as defined above, Ei,j (ξ1 , . . . , ξn ) represents the i-th elementary symmetric polynomial over the set {ξ1 , . . . , ξn } \ {ξj }. Proof. See [9], for example.
⊔ ⊓
For the sake of brevity, we will define Qj (ξ1 , . . . , ξn ) as Qj (ξ1 , . . . , ξn ) :=
j−1 Y
n Y
l=1
l=j+1
(ξj − ξl ) ·
(ξl − ξj ).
(2)
Observe that for the Vandermonde matrix V to be invertible all of the ξ1 , . . . , ξn must be distinct. Since by hypothesis, it is the case that all of the β1 , . . . , βN , the roots of g(x), are indeed distinct, then it follows that Vg−1 does exist. The idea of this attack is to choose a polynomial g(x) with roots {β1 , . . . , βN } such that the resulting samples, via the isomorphism between Fq [x]/(f (x)) and Fq [x]/(g(x)), can be efficiently distinguished by resorting to the original attacks of [5] and [6]. The difficulty lies in the fact that the constructed isomorphisms will likely distort the samples so as to render the attacks unpractical or unfeasible. On the positive side, this attack has two configurable elements that will hold the key to their applicability: – The root βi to use for the evaluation of the resulting samples via the isomorphism will be chosen so as to maximize the success possibility. In other words, since we can choose it as we like, this value will either be {0, 1, −1} or an element of, at most, order 3. – The remaining roots, which are not relevant to the distinguisher construction, but will be critical in order to build an isomorphism that does not distort the samples too much.
An alternative approach towards attacks against fully-split PLWE instances
13
Attack with evaluating root β = 0. As a starting point, we will consider whether the easiest possible configuration can be applied, i.e., the use of βi = 0 as the evaluating root. It is a direct consequence of the last proposition that, if βi = 0, then the first row of the inverse matrix Vg−1 has all its entries 0 but for the i-th column, which is 1. And, this means that the first row of the isomorphism matrix Vg−1 · Vf is, in turn, 1 α1 · · · α1N −1 0 · · · 0 1 0 · · · 0 · ... ... . . . ... = 1 αi · · · αiN −1 .
N −1 1 αN · · · αN
Now, if we are given a sample seen a as a vector, a = (a0 , . . . , aN −1 ), and the transformed sample via the isomorphism, b = (b0 , . . . , bN −1 ) and we evaluate the latter at the root β = 0, the only non-zero term is 1 N −1 αi X b0 = a0 · · · aN −1 · .. = aj · αij . . j=0
αiN −1
But then we have reduced the problem to the original setting under evaluation on αi . Since we assume the latter (or any other root of f (x) for that matter) to be unsuccessful, so the isomorphism provides no advantage for the attack. Therefore, we can claim that applying the isomorphism and evaluating over a (potential) root β = 0 will not yield a successful attack regardless of the polynomial g(x) chosen. This does not mean however that a polynomial with 0 as root will always be unsuccessful (which is not necessarily true), it only means that evaluation under β = 0 will be. Attack with evaluating root β = 1. We turn now to the next interesting root to be analyzed, namely, β = 1. If we denote the isomorphism matrix M := Vg−1 · Vf , as given by
1 x1,2 · · · x1,N 0 x2,2 · · · x2,N M =. . . , . . ... .. .. 0 xN,2 · · · xN,N then we can write the transformation in matrix notation as b = M · a, namely, b0 = a0 +
N −1 X
x1,j+1 · aj ,
j=1
bi =
N −1 X
xi,j+1 · aj ,
2 ≤ i ≤ N,
j=1
so that the transformed sample in polynomial representation becomes b(y) = a0 +
N X i=1
y i−1
N −1 X
xi,j+1 · aj .
(3)
j=1
The evaluation of the latter at the root β = 1 yields b(1) = a0 +
N −1 X j=1
aj ·
N X i=1
xi,j+1 = a0 +
N −1 X
aj · Sj+1 (M ),
(4)
j=1
PN where Sj (M ) = i=1 xi,j is precisely the sum of all the entries in the j-th column of the matrix M . Put more bluntly, each of the terms of the original sample a (but for a0 ) becomes “multiplicatively perturbed” by the sum of the entries in the corresponding column of the isomorphism matrix. In this way, we are able to deduce the first condition in order to achieve a practical attack when β = 1 is selected as the evaluation root, namely, select a polynomial g(x) (or, rather, its roots) so
14
I. Blanco Chacón, R. Durán Díaz, R. Martín Sánchez-Ledesma
that the sum of the entries of each column of the isomorphism matrix yields (almost) the same values. More precisely, keep | {Sj (M ) : 1 ≤ j ≤ N } | ≤ T, where T represents a threshold value not overpassing 3. Moreover, not only the number of distinct elements in the set above but also their value itself will impact on the success probability of the attack (depending on the attack chosen). The most desirable values are, obviously, 0, 1, or −1. Moreover, we have the next Lemma 7. The following equation holds: Qj (β1 , . . . , βn ) = (−1)N +j Gj (βj ; β1 , . . . , βN ). Proof. The result follows from the definition of Qj (see Equation (2)) and Gj , which are identical but for a number of inversions in Qj , which is precisely N − j. But recalling that −1 has order 2 in Z∗ , it is clear that N − j ≡ N + j mod 2 and the result follows. ⊔ ⊓ Equipped with these tools, let us now provide a more in-depth description of the xi,j in the isomorphism matrix M and how the sums Sj (M ) look like, a critical step towards analyzing the likelihood of solving the generated system. Each of the entries of the isomorphism matrix can be represented as N X αkj−1 EN −i,k (β1 , . . . , βN ), (5) xi,j = (−1)i+k Qk (β1 , . . . , βN ) k=1
where Qk (β1 , . . . , βN ) follows its definition in Equation 2. In other words, the [i, j] entry of the matrix is the sum of the (N − i)-th elementary polynomial over all possible subsets of N − 1 roots of g(x), each one weighted by the term αkj−1 /Qk . Thus, the sum Sj (M ) can be expressed as Sj (M ) =
N N X X
(−1)i+k
i=1 k=1
=
N X k=1
αkj−1 EN −i,k (β1 , . . . , βN ) Qk (β1 , . . . , βN )
N X αkj−1 (−1)i+k EN −i,k (β1 , . . . , βN ). Qk (β1 , . . . , βN ) i=1
Informally, the j-th column sum, Sj (M ), is the sum of all symmetric polynomials on each of the N subsets, each sum being weighted by the term αkj−1 /Qk . From the previous characterization, we extract two observations: 1. Observe that for the attack to be applicable, we need most of the elements Sj (M ) to be equal and it is clear from the computations above that all of them are influenced by the common factor, N X SEk := (−1)i+k EN −i,k (β1 , . . . , βN ), i=1
for k ∈ {1, . . . , N }, which represent the sum of the symmetric polynomials on each of the subsets. Thus, a clear initial path can be choosing the roots of g(x) is a way that these sums are all 0. 2. Since this common term appears on every Sj (M ) weighted with distinct values that do depend on j, it would be most likely not possible for the elements in the set {Sj (M )} to be almost equal over a 0-characteristic base field. But, since we are working in a positive characteristic base field, it is still possible. Remark that taking advantage of Lemma 6, we can simplify the term SEk . Actually, evaluating at λ = 1, we have N X Gk (1; β1 , . . . , βN ) = (−1)N −i EN −i,k (β1 , . . . , βN ), i=1
whence we deduce (−1)N +k Gk (1; β1 , . . . , βN ) =
N X (−1)i+k EN −i,k (β1 , . . . , βN ) = SEk , i=1
An alternative approach towards attacks against fully-split PLWE instances
15
recalling again that −1 has order 2 in Z∗ and N + k + N − i ≡ i + k mod 2. Accordingly Sj (M ) =
N X
(−1)N +k
k=1
αkj−1 Gk (1; β1 , . . . , βN ). Qk (β1 , . . . , βN )
Remember we are assuming that one of the β roots has value 1, say βi = 1. Then, by its definition, Gk (1; β1 , . . . , βN ) = 0 for all k ̸= i. Hence Sj (M ) = (−1)N +i
αij−1 Gi (1; β1 , . . . , βN ), Qi (β1 , . . . , βN )
βi = 1.
But from Lemma 7 it follows directly that Qi (β1 , . . . , βn ) = (−1)N +i Gi (1; β1 , . . . , βN ), hence Sj (M ) = αij−1 . Remark that by hypothesis, all of the roots β1 , . . . , βN are distinct, so Gi (1; β1 , . . . , βN ) cannot be zero for any i. Now we are in a position for rewriting Equation (4) as N −1 X
b(1) =
aj · αij ,
j=0
which, as discussed before, is not subject to any of the attacks, since the original polynomial f (x) is not. It is curious though how the exact same term keeps appearing in all our approaches. This raises the question Will it also appear on the general case? Anyway, this analysis shows that choosing β = 1 as the evaluation root will not yield a satisfactory result, regardless of the polynomial g(x). As with β = 0, it does not mean, however, that g(x) cannot have β = 1 as root, it only means that it cannot be selected as the evaluating term, although if selected, we already know how the sum of the columns will look like, and we will probably feel uneasy should such value happens to occur. Attack with arbitrary evaluating root. We now choose, in general, any root ξ, hoping to avoid the recurrent term of the sum of roots of f (x). Once we migrate into this setting (a root of order > 1), we need to truly consider the impact of the evaluation root in the overall term. In the general case, following Equation (3), we end up with evaluation terms of the form b(ξ) = a0 +
N X
ξ
i−1
i=1
N −1 X
xi,j+1 · aj = a0 +
j=1
N −1 X
aj · Sj+1,ξ (M ),
j=1
which combined with Equation (5), yields Sj,ξ (M ) =
N X
ξ i−1 · xi,j =
N X i=1
i=1
=
N X k=1
ξ i−1
N X
(−1)i+k
k=1
αkj−1 EN −i,k (β1 , . . . , βN ) Qk (β1 , . . . , βN )
N X αkj−1 (−1)i+k ξ i−1 EN −i,k (β1 , . . . , βN ). Qk (β1 , . . . , βN ) i=1
Following again Lemma 6 and reasoning as above, we have (−1)N +k Gk (ξ; β1 , . . . , βN ) =
N X
(−1)i+k ξ i−1 EN −i,k (β1 , . . . , βN ).
i=1
The root ξ is any arbitrary root of g(x), say ξ = βℓ . By its definition, Gk (βℓ ; β1 , . . . , βN ) = 0 for all k ̸= ℓ so, keeping in mind Lemma 7, we finally have Sj,βℓ (M ) = (−1)N +ℓ
αℓj−1 Gℓ (βℓ ; β1 , . . . , βN ) = αℓj−1 . Qℓ (β1 , . . . , βN )
Thus, for any arbitrary root of g(x), βℓ , we get the general evaluated term b(βℓ ) =
N −1 X j=0
aj · αℓj .
16
I. Blanco Chacón, R. Durán Díaz, R. Martín Sánchez-Ledesma
It is interesting to note that the evaluation of b(βℓ ) does not depend on the value of the particular root selected but only on the corresponding root (in this case αℓ ) and the coefficients of the polynomial f (x). As discussed before, it is not subject to any of the attacks, since the original polynomial f (x) is not. Therefore, we have proven that fully-split polynomials are secure, even in the face of constructing isomorphisms to other vulnerable settings. This result would be of additional interest if one could show that every isomorphism between the quotient polynomial fields of Fq generated by f (x) and g(x) is of the form Vg−1 ·Vf , which would prove that this settings are not vulnerable to further exploits of these attacks. This is precisely what we attempt to do in the coming sections. A.2
The fully-split case: Uniqueness of isomorphism between the rings
In this section we prove that any isomorphism between our initial ring and the target ring is given by the product of the inverse Vandermonde matrix of the target polynomial and the Vandermonde matrix of the initial polynomial. This settles once and for all the question that isomorphisms of polynomial rings will not yield any successful advantage towards attacking polynomial rings. We state the main result as the following Theorem 1. Let q be a prime and f (x), g(x) be irreducible polynomials over Z[x] such that they N factor completely over Fq [x] with {αi }N i=1 the set of roots of f (x) in Fq [x], and {βi }i=1 the set of roots of g(x) in Fq [x]. Then, any ring isomorphism QN QN ψ : Fq [x]/( i=1 (x − αi )) → Fq [x]/( i=1 (x − βi )) is of the form Vg−1 · Vf , where Vf , Vg represent the Vandermonde matrices of the roots of the (fully-split) polynomials f (x) and g(x) over Fq [x]. In order to prove Theorem 1 we need the following Lemma ensuring that every resulting homomorphism evαji is distinct. Lemma 8. For every two roots β1 ̸= β2 , the corresponding roots αj1 and αj2 of the resulting evaluation homomorphisms evαji := evβi ◦ψ are distinct. QN Proof. Given p(y) ∈ Fq [y]/ i=1 (y − βi ), we have that evβ1 (p(y)) ̸= evβ2 (p(y)). Since ψ is an isoQN morphism of polynomial rings, p(y) is the image of a unique r(x) ∈ Fq [x]/ i=1 (x − αi ). Therefore, evβ1 (ψ(r(x))) ̸= evβ2 (ψ(r(x))). And, by Lemma 4, evβi ◦ψ = evαji . Therefore, evαj1 (r(x)) ̸= evαj2 (r(x)) and this means that αj1 ̸= αj2 .
⊔ ⊓
With this auxiliary Lemma, we can complete now the proof of Theorem 1: Proof (Theorem 1). Now we want to explicitly compute how ψ looks like. Given a certain p(x) ∈ QN QN Fq [x]/ i=1 (x − αi ), the image ψ(p(x)) ∈ Fq [y]/ i=1 (y − βi ) can be expressed in terms of the coefficients of the resulting polynomial. Therefore, we view ψ(p(x)) as (ψ0 (p(x)), · · · , ψN −1 (p(x))), which is the coefficient representaPN −1 tion of the polynomial h(p(x)) := k=0 ψk (p(x)) · y k . Now, by Corollary 1, we have evβi (ψ(p(x))) = evβi (h(p(x))) =
N −1 X k=0
ψk (p(x)) · βik =
N −1 X
pk αjki = evαji (p(x))
k=0
∀i ∈ {1, · · · N }. Thus, putting together this representation for every i, we have: ψ0 (p(x)) p0 N −1 1 α · · · α 1 β1 · · · β1N −1 j 1 j1 .. .. . . . ψ1 (p(x)) = .. .. . . .. · p1 . . . . .. . . .. · . . .. . N −1 N −1 1 βN · · · βN 1 αjN · · · αjN ψN −1 (p(x)) pN −1
An alternative approach towards attacks against fully-split PLWE instances
17
Since the roots {βi }i are all distinct, we can invert the matrix and have: p0 ψ0 (p(x)) N −1 N −1 −1 1 α · · · α 1 β · · · β j 1 1 j 1 1 ψ1 (p(x)) .. .. . . .. · .. .. . . .. · p1 =. . .. . . . . . . . .. . N −1 N −1 1 βN · · · βN 1 αjN · · · αjN pN −1 ψN −1 (p(x)) and, by Lemma 8, we have that the roots {αji }i are all distinct. Therefore, the above matrices represent exactly the Vandermonde matrices of the polynomials f (x) and g(x), arriving to the desired result. ⊔ ⊓ A.3
A simple example
In the sequel we will present a simple example following the lines of Proposition 4. The setting is Fq with q = 31. We select the following 7-degree polynomial, which is irreducible over Z[x]: f (x) = x7 + 25 x6 + 9 x5 + 11 x4 + 19 x3 + 8 x2 + 21 x + 29, but factors over Fq as f1 (x) = x3 + 19 + 17 x + 11 x2 , f2 (x) = x4 + 26 + 17 x + 24 x2 + 14 x3 . with f1 (x), f2 (x) ∈ Fq [x]. Then we have that Rq = Fq [x]/ (f1 (x)f2 (x)) ≃ Fq [x]/(f1 (x)) × Fq [x]/(f2 (x)). Now we choose another polynomial, g(x), featuring the same factorization structure as f (x), and irreducible over Z[x]: g(x) = x7 + 29 x6 + 8 x5 + 9 x4 + x3 + 22 x2 + 23 x + 14, which factors over Fq as g1 (x) = x3 − 5 g2 (x) = x4 + 22 + 14 x + 8 x2 + 29 x3 , with g1 (x), g2 (x) ∈ Fq [x]. Then we have Rq′ = Fq [x]/ (g1 (x)g2 (x)) ≃ Fq [x]/(g1 (x)) × Fq [x]/(g2 (x))). Observe that g1 (x) is a 3-ideal factor and, moreover, the order of 5 in Fq is just 3, as required for the successful application of the suitable attacks. Now, using the polynomial basis, we compute the isomorphism ψ from Rq to R′ . Since this is a toy example, the simplest algorithm is just exhaustive search that eventually provides us with the following matrix over the polynomial basis: 1 7 23 14 0 25 14 0 0 28 18 12 0 20 0 3 26 30 24 15 29 ψ= 0 26 12 17 15 0 17 . 0 6 25 29 3 14 5 0 17 23 17 1 17 26 0 20 9 28 22 13 25 Besides, it is very easy to compute its inverse in GL(Fq ), which turns out to be 1 2 13 15 1 10 19 0 1 20 5 5 24 26 0 19 10 25 17 21 19 ψ −1 = 0 19 7 21 28 15 28 . 0 5 10 11 19 19 29 0 0 25 12 9 4 4 0 20 14 17 14 17 30
18
I. Blanco Chacón, R. Durán Díaz, R. Martín Sánchez-Ledesma
Thus, if we take a random element in Rq , such as f s(x) = 28 x6 + 19 x5 + 10 x4 + 2 x3 + 15 x2 + 14 x + 18, it is easy to compute gs(x) = ψ(f s(x)) ∈ Rq′ , which yields gs(x) = 26 x6 + 4 x5 + 23 x4 + 26 x3 + 20 x + 23. Now let α be a root of f1 (x), which obviously is also a root of f (x). We can consider the evaluation mapping evα : Rq → Fq3 . Applying evα on f s(x), we get evα (f s(x)) = f s(α) = α2 + 18 α + 3, which is an element living in Fq3 , and represented in a polynomial basis. In the same line, let β be a root of g1 (x), also a root of g(x), and consider the corresponding evaluation mapping evβ . Now if we apply such mapping to gs(x), we get evβ (gs(x)) = gs(β) = 20 β 2 + 11 β + 28, again represented in a polynomial basis. Now we are interested in checking Equation (1) in Corollary 1, so we face the task of computing the traces of f s(α) and gs(β) over Fq3 . The simplest way is to compute the matrices associated to the endomorphisms “multiply by f s(α)” and “multiply by gs(β)” and obtain their traces, keeping in all the computations Fq as the base field. By so doing, we get that first matrix is 3 12 22 End(f s(α)) = 18 17 17 , 1 7 2 whereas the second is
28 7 24 End(gs(β)) = 11 28 7 , 20 11 28
and a simple computation shows that Tr(f s(α)) = tr (End(f s(α))) = tr (End(gs(β))) = Tr(gs(β)) = 22. Remembering that gs(x) = ψ(f s(x)), we check for this particular case that Tr ◦ evα = Tr ◦ evβ ◦ ψ, as desired.