Key Recovery from Residue-Confined Errors in Pradhan CRT-RLWE

Key Recovery from Residue-Confined Errors in the Pradhan CRT-RLWE Construction

arXiv:2608.21989v1 [cs.CR] 22 Aug 2026

Lukasz Olejnik1,2* and Bartosz Naskrecki3,4 1*

Department of War Studies, King’s College London, London, United Kingdom. 2 Independent Researcher. 3 Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznan, Poland. 4 Centre for Credible AI, Warsaw University of Technology, Warsaw, Poland. *Corresponding author(s). E-mail(s): me@lukaszolejnik.com; Contributing authors: bartnas@amu.edu.pl; Abstract We show that the CRT-FHE scheme of Pradhan et al. is insecure for laws within its assumed error distribution range. The secret key follows from the public key by a single ring inversion whenever the public multiplier is a unit. The plaintext is recovered from any ciphertext under such a law without the secret key, for every multiplier, giving chosen-plaintext advantage 1/2. We further show that the transformation from ordinary Ring-LWE to CRT-RLWE does not preserve the error distribution, so it does not establish that CRT-RLWE is at least as hard as Ring-LWE. One mechanism underlies both. The Chinese remainder theorem (CRT) function is reduced modulo p1 p2 while its output is used modulo a coprime modulus q, so under every zero-preserving section an error in p2 R encodes to zero. The law p2 B1 is so confined, meets the stated conditions, and decrypts correctly. Confinement is not a weakness of scale: scaling any baseline law by p2 leaves its ordinary Ring-LWE problem exactly equivalent, while the reduced encoder destroys every error it produces. The reduction discrepancy is a multiple of p1 p2 and not of q, so the small-error premise of the proof cannot remove it, and at the reported parameters a single error coefficient refutes the identity while satisfying that premise. The centered binomial B2 separates the coefficient laws at total

1

variation distance 3/8, and at the reported dimension that distance between the induced polynomial laws is exponentially close to one. Keywords: Chinese remainder theorem, ring learning with errors, homomorphic encryption, error distributions, CRT encoding, cryptanalysis

1 Introduction Ring learning with errors (RLWE) is a family of problems whose security depends on the ring, modulus, representation, and error distribution [5, 6]. Hardness theorems apply to specified distributions. They do not imply that every narrow or algebraically structured error law is secure. A transformation of the error must therefore be accounted for in the definition of the error distribution and in the security reduction that accompanies it. Pradhan, Dutta, Jangir, and Das propose a homomorphic-encryption construction based on a Chinese remainder theorem (CRT) variant of the RLWE distribution [7]. Definition 1 gives the CRT function by a formula reduced modulo p1 p2 , KeyGen and

Enc then insert its output into a ring modulo a coprime ciphertext modulus q . This cross-modulus use requires a representative, because equality modulo p1 p2 need not be equality modulo q . The representative choice is immaterial for the zero CRT class: every zero-preserving convention sends it to 0, and that single fact drives the results below. We use the definition and theorem numbering of [7]. Our contributions are the following. 1. Residue confinement collapses the reduced CRT error. If the public-key error lies in

p2 R, then b = as and the secret is recovered exactly on the unit event (Theorem 3.1). If the challenge errors are confined as well, a polynomial gcd and CRT decomposition recovers the encoded challenge message for every public multiplier, with chosen-plaintext advantage 1/2 (Theorem 3.2).

2

2. A concrete efficiently samplable subgaussian law realizes those hypotheses. The coefficient law p2 B1 , built from the centered Bernoulli difference B1 , is discrete, bounded by p2 , supported on p2 R, and subgaussian with variance proxy p22 /2 (Proposition 3.5). 3. The same-law RLWE transformation does not preserve the error distribution. For the least-nonnegative representative, the discrepancy between the two maps has the closed form p⌊ke/p2 ⌋, so under the proof’s no-wrap premise the identity used in Theorem 4 holds on 0 ≤ ke < p2 (Lemma 4.1), and at the reported parameters that is e ∈ {0, 1}. Distributionally, scaling induces (e 7→ ∆2 e)# χ while the reduced encoder induces ψ = (e 7→ Eσ,q (0, e))# χ, and these differ whenever the coefficient law charges more integers, pairwise distinct modulo q , than the small CRT factor

p2 (Proposition 4.3 and Corollary 4.4). The results of Section 3 concern residue-confined errors, whereas the distributional results of Section 4 apply more generally, including to centered-binomial and untruncated discrete-Gaussian coefficient laws. The relation to the conditional security theorem of [7] is discussed in Section 4.1. Evaluation and subfield attacks exploit RLWE or PLWE instances whose errors become distinguishable under algebraic projections [2–4]. In that line of work the error law is fixed by the problem statement, and the attack applies a projection under which an already narrow law becomes statistically visible. The mechanism here is different and prior to any projection: the construction interposes an additional encoder between the sampled error and the ring element that carries it, and that encoder is not injective on the sampled error. For the residue-confined laws of Section 3 the resulting failure is exact, and in both sections it is a property of the encoding step, not of the ambient number field. Peikert studies the sensitivity of Ring-LWE security to the choice and representation of the error distribution, and separates the narrow laws that admit attacks from those supported by worst-case hardness results [6]. Theorem 4.8 establishes an

3

exact equivalence between the corresponding ordinary-RLWE distributions. Castryck, Iliashenko, and Vercauteren analyze how transformations between error distributions in ring-based LWE affect the resulting problem [1]. The push-forward computed in Section 4 is such a transformation, imposed here by the construction itself.

2 CRT encoding and representative lifts Let

R = Z[X ]/(X n + 1),

Rt = R/tR,

where n is a power of two. Let p1 , p2 be coprime, set p = p1 p2 , and assume p < q/2 and gcd(p, q ) = 1, as required by the parameter conditions of [7]. Denote the class-valued CRT isomorphism by CRT : Rp1 × Rp2 −→ Rp . All lifts below act coefficientwise in the power basis. Choose integers ∆1 = p2 [p−1 2 ]p1 ,

∆2 = p1 [p−1 1 ]p2 ,

where the inverses are represented in the indicated least-nonnegative ranges. Thus ∆1 has residues (1, 0) and ∆2 has residues (0, 1) modulo (p1 , p2 ). Throughout, the error distribution χ samples integer-polynomial representatives. This is the type required to make the encoder well defined: the CRT function consumes

e mod p2 , while the ciphertext lives modulo the coprime modulus q , so reduction modulo q occurs after the encoding step and not before it. Where a coefficient law is needed we write ν for a distribution on Z and take χ to sample the n coefficients independently from ν , as the centered binomial and discrete Gaussian instantiations do.

Definition 2.1 (Reduced CRT encoder) A coefficientwise section is a public map σ : Rp → R whose reduction modulo p is the identity. It is zero-preserving if σ(0) = 0. The associated

4

encoder is
Eσ,q (m, e) = σ CRT(m, e mod p2 ) mod q. The least-nonnegative and centered coefficient representatives are zero-preserving sections.

Definition 2.2 (Unreduced integer lift) For a fixed integer representative m e of the message,

define

Eraw,q (m, e) = ∆1 m e + ∆2 e

(mod q).

Here the sampled integer representative e is used before reduction modulo p2 .

Lemma 2.3 (Carry relation between the two lifts) For every m and e, there is an integer polynomial Kσ (m, e) ∈ R such that
∆1 m e + ∆2 e = σ CRT(m, e mod p2 ) + pKσ (m, e).

Consequently, the two encoders differ in Rq by pKσ (m, e), which need not vanish because p is a unit modulo q.

Proof The two integer polynomials have the same coefficient residues modulo p1 and modulo p2 , hence their difference is coefficientwise divisible by p = p1 p2 . Reduction modulo q gives the last statement.



The separation is immediate for m = 0 and e = p2 r. The reduced encoder, realized by any zero-preserving section, gives

Eσ,q (0, p2 r) = σ (0) = 0,

whereas the unreduced lift gives

Eraw,q (0, p2 r) = ∆2 p2 r 5

(mod q ),

which is not the zero map under the stated parameter conditions. Multiples of the CRT modulus are retained in the integer-level correctness analysis of [7] as well. In its Section 4.1, where p = pr1 p2 , Equation (8) writes the centered decryption value as

v (c) = p k (c) + CRTpr1 ,p2 (m(c), η (c)) = p k (c) + ∆1 m(c) + ∆2 η (c)

with a coarse integer component k (c), and Equation (9) retains p k (c) in the global error

E (c) = ∆2 η (c) + p k (c). Their k (c) is distinct from the representative carry Kσ (m, e) of Lemma 2.3; in particular, Equation (13) specializes fresh encryption to k (c) = 0. Equations (8)–(9) nevertheless show that the integer-level correctness analysis of [7] retains integral multiples of the applicable CRT modulus. Lemma 2.3 therefore establishes three facts used below. The reduced CRT encoder and the unreduced integer lift are distinct maps into Rq . The results of Section 3 concern the reduced encoder of Definition 2.1, which is a representative-level realization of the reduced CRT function of Definition 1 of [7], used in KeyGen through the term CRTp1 ,p2 (0, e). The algebraic identity used in Theorem 4, which identifies that term with the integer ∆2 e, corresponds instead to Definition 2.2.

3 Consequences of error collapse Call a distribution on integer polynomials p2 -confined if its support is contained in

p2 R. Under the reduced encoder, consider the public-key and encryption equations

b = as + Eσ,q (0, epk ), c0 = bu + Eσ,q (m, e0 ), c1 = −au + Eσ,q (0, e1 ) 6

in Rq . Write M (m) = Eσ,q (m, 0) for the encoding of a message carrying no error.

Theorem 3.1 (Error collapse and key recovery) Let σ be an efficiently computable zeropreserving section. If epk is sampled from a p2 -confined law, then Eσ,q (0, epk ) = 0,

b = as.

A passive algorithm recovers s = a−1 b whenever a ∈ R× q , in time polynomial in n and log q.

Proof Confinement gives epk mod p2 = 0, so CRT(0, epk mod p2 ) = 0, and zero preservation gives σ(0) = 0. The public-key equation reduces to b = as. For the inverse, note that multiplication by a is a Zq -linear endomorphism of Rq , and a is a unit if and only if that endomorphism is invertible. The inverse a−1 is then obtained by linear algebra over Zq in time polynomial in n and log q. When q is prime the extended Euclidean algorithm in Fq [X]/(X n + 1) is the standard alternative.



The unit event is not rare. When q is prime and F = X n + 1 =

Q

ki i fi over Fq with

distinct monic irreducibles fi of degrees di , a uniform a ∈ Rq is a unit with probability

Pr[a ∈ R× q ]=

Y

(1 − q −di ) ≥ 1 −

i

n , q

the bound following from the union bound over at most n factors. For a completely split F the probability is exactly (1 − q −1 )n . The next result removes the conditioning entirely. We use the standard chosen-plaintext experiment: the adversary submits m0 , m1 , receives an encryption of mβ for a uniform bit β , and outputs β ′ , with advantage Adv = Pr[β ′ = β ] − 12 . A success probability Pr[β ′ = β ] = 1 therefore corresponds to advantage 1/2, the maximum.

7

Theorem 3.2 (Perfect challenge-message recovery) Let σ be an efficiently computable zeropreserving section, let q be prime, and let F = X n + 1 be squarefree over Fq . Suppose epk , e0 , and e1 are sampled from p2 -confined laws, and that two efficiently chosen messages m0 , m1 satisfy M (m0 ) 6= M (m1 ). Then a deterministic polynomial-time adversary recovers M (mβ ) for every a ∈ Rq , unit or not, and outputs β ′ = β with probability one. Its chosen-plaintext advantage is 1/2.

Proof Confinement and zero preservation give Eσ,q (0, epk ) = Eσ,q (0, e1 ) = 0,

Eσ,q (m, e0 ) = M (m),

so b = as, c0 = bu + M (mβ ), and c1 = −au. Let e a ∈ Fq [X] be the degree-< n representative of a, and put d = gcd(e a, F ),

h = F/d.

Squarefreeness gives gcd(d, h) = 1. Modulo d, both a and b = as vanish, so c0 ≡ M (mβ ). Modulo h, the class of a is a unit, hence u ≡ −a−1 c1

(mod h),

M (mβ ) ≡ c0 − bu

(mod h).

Polynomial CRT reconstructs M (mβ ) modulo F from its residues modulo d and h. The degenerate cases d = 1 and d = F are included. Comparing the reconstructed value with M (m0 ) and M (m1 ), which differ by hypothesis, determines β. Polynomial gcd, extended Euclidean computation, and polynomial CRT run in time polynomial in n and log q.



Remark 3.3 (Squarefreeness is automatic) The hypothesis on F = X n +1 is not an additional restriction in the setting of [7]: there n is a power of two and q is an odd prime, so q ∤ n and n is invertible in Fq . Since F (0) = 1, the variable X does not divide F , and gcd(F, F ′ ) = gcd(F, nX n−1 ) = 1. Hence F is squarefree over Fq for every admissible parameter choice.

8

Corollary 3.4 (An explicit challenge pair) Let σ be the least-nonnegative or the centered section and assume p < q/2. Then M (0) = 0 and M (1) 6= 0 in Rq , so the messages m0 = 0 and m1 = 1 satisfy the separation hypothesis of Theorem 3.2.

Proof The class CRT(0, 0) is zero and σ is zero-preserving, so M (0) = 0. The class CRT(1, 0) has residues (1, 0) modulo (p1 , p2 ), hence equals ∆1 modulo p, and ∆1 6≡ 0 modulo p because [p−1 2 ]p1 6= 0. Let c = σ applied to that class. The least-nonnegative section gives c ∈ [0, p) and the centered section gives c ∈ (−p/2, p/2], so in both cases 0 < |c| < p, the strict lower bound because c 6≡ 0 (mod p). Since p < q/2 we get 0 < |c| < q, hence c 6≡ 0 (mod q) and M (1) 6= 0 = M (0). The restriction to these two sections is needed: an arbitrary section may send the class to ∆1 + jp for any integer j, and such a representative can be divisible by q.



3.1 A residue-confined subgaussian error distribution Let U, V be independent uniform bits and let B1 = U − V , so that B1 takes the values −1, 0, 1 with probabilities 1/4, 1/2, 1/4. Sample the coefficients of the error independently from p2 B1 .

Proposition 3.5 The law p2 B1 is discrete, efficiently samplable, supported on p2 R, and √ bounded coefficientwise by p2 , hence deterministically kek2 ≤ p2 n for every sample. It is subgaussian with variance proxy p22 /2: for every real t, h i 2 2 E etp2 B1 ≤ et p2 /4 , 2

2

whence Pr [|p2 B1 | ≥ u] ≤ 2e−u /p2 for every u > 0, and for independent coefficients x = (x1 , . . . , xn ) and every y ∈ Rn , h i 2 2 2 E ethx,yi ≤ et p2 kyk2 /4 .

9

2

Equivalently, in the normalization used in [7], which requires Pr[|hα, ei| > tσkαk2 ] ≤ 2e−πt , the law satisfies that condition with √ σ = p2 π. The law therefore satisfies the discreteness, efficient-sampling, boundedness, and subgaussian tail conditions imposed on the error distribution in the Setup and Section 3.2 of [7].

Proof Support, boundedness, discreteness, and sampling cost follow from the support {−p2 , 0, p2 } and two fair coin flips per coefficient. For the tail, independence of U and V gives h i 2 1 + cosh t 1 + et 1 + e−t · = = cosh2 (t/2) ≤ et /4 , E etB1 = 2 2 2 2

using cosh x ≤ ex /2 . Replacing t by tp2 gives the stated moment generating function bound, that is, a subgaussian variance proxy s2 = p22 /2. The Chernoff bound Pr[X ≥ u] ≤ exp(−u2 /2s2 ) and symmetry of B1 give the two-sided tail bound. For a linear form, independence of the coefficients multiplies the individual bounds, producing the exponent P t2 p22 j yj2 /4. For the stated normalization, substituting u = tσkαk2 into the two-sided bound √ gives exponent −t2 σ 2 /p22 , which equals −πt2 exactly when σ = p2 π. 

The law p2 B1 is distinct from the unit-step centered-binomial family Bη used elsewhere in [7]. Proposition 3.5 therefore gives an explicit efficiently samplable error law to which Theorems 3.1 and 3.2 apply, in a form that is checkable against the stated distributional conditions. The construction draws the secret, the public-key error, the encryption multiplier, and the encryption errors from a single distribution χ. Taking that distribution to be the coefficientwise law p2 B1 at every occurrence in KeyGen and Enc gives a complete instantiation of the family to which the two theorems apply.

Corollary 3.6 (The insecure instantiation is correct) Let σ be the least-nonnegative or the centered section, let p < q/2, and let all encoder errors be p2 -confined. Then every fresh ciphertext decrypts to its message.

10

Proof Collapse gives b = as, c0 = bu+M (m) = asu+M (m) and c1 = −au, so the decryption phase is exactly c0 + c1 s = asu + M (m) − aus = M (m), with no error term at all. Both named sections give kM (m)k∞ < p < q/2, so centering modulo q returns the integer polynomial M (m) itself, and reduction modulo p1 returns m.



Thus the confined-law instantiation is simultaneously correct and insecure.

Corollary 3.7 (Uniform asymptotic adversary) Let a polynomial-time parameter generator output reduced-CRT instances satisfying the hypotheses of Theorem 3.2, with efficiently computable distinct message encodings and errors drawn from p2 B1 . Then the algorithm of Theorem 3.2 is a single uniform deterministic polynomial-time chosen-plaintext adversary that succeeds with probability one at every security parameter.

4 Error-distribution mismatch in the RLWE transformation Theorem 4 of [7] transforms an ordinary RLWE sample (a, as + e) with e ← χ by scaling with ∆2 , and identifies the resulting error ∆2 e with CRTp1 ,p2 (0, e). For the reduced encoder these are different maps, and the difference is visible at the level of distributions. Both maps act coefficientwise, so it is enough to compare them on a single coefficient. Write, for an integer x,

τ (x) = ∆2 x mod q,

γ (x) = σ CRT(0, x mod p2 ) mod q,

and let T and C denote the corresponding coefficientwise maps on integer polynomials, so that C (e) = Eσ,q (0, e). The transformation of Theorem 4 produces the error law

T# χ, while the reduced encoder produces C# χ. The same-law conclusion can hold only if these two push-forwards coincide. 11

For the least-nonnegative representative of the reduced CRT expression, the discrepancy admits a closed form. The push-forward analysis below continues to allow an arbitrary section.

Lemma 4.1 (Exact discrepancy for the least-nonnegative representative) Write k = [p−1 1 ]p2 , so that ∆2 = p1 k, and let γ0 (e) = ∆2 (e mod p2 ) mod p be the integer returned by the reduced CRT function on (0, e). Then, for every integer e, 

 ke ∆2 e − γ0 (e) = p . p2 Consequently the identity ∆2 e ≡ CRTp1 ,p2 (0, e) in Rq holds if and only if ⌊ke/p2 ⌋ ≡ 0 (mod q). Under the no-wrap condition |∆2 e| < q/2 used in the proof of Theorem 4, this is equivalent to 0 ≤ ke < p2 .

Proof Write e = p2 t + y with y = e mod p2 ∈ {0, . . . , p2 − 1}. Then γ0 (e) = ∆2 y − p⌊∆2 y/p⌋ and ∆2 e = ∆2 p2 t + ∆2 y, so ∆2 e − γ0 (e) = ∆2 p2 t + p



 ∆2 y . p

Now ∆2 p2 = p1 kp2 = pk and ∆2 y/p = ky/p2 , whence the right-hand side is p(kt+⌊ky/p2⌋) = p⌊k(p2 t+y)/p2⌋ = p⌊ke/p2 ⌋. Since gcd(p, q) = 1, this vanishes in Rq exactly when ⌊ke/p2 ⌋ ≡ 0 (mod q). Under the no-wrap condition, q |∆2 e| ke < . = p2 p 2p Since p > 1, this implies |⌊ke/p2 ⌋| < q. The congruence then forces ⌊ke/p2 ⌋ = 0, which is equivalent to 0 ≤ ke < p2 .



The lemma isolates the mechanism. The proof of Theorem 4 invokes the smallerror condition k∆2 ek < q/2, but that condition does not force ⌊ke/p2 ⌋ to vanish, as the next example shows.

12

Example 4.2 (A single integer refutes the identity) At the reported p1 = 65537 and p2 = 3 we have k = 2 and ∆2 = 131074. Among coefficients satisfying the no-wrap premise, the identity modulo q therefore holds exactly for 0 ≤ 2e < 3, that is, for e ∈ {0, 1}. Already e = 2 fails: ∆2 · 2 = 262148,

CRTp1 ,p2 (0, 2) = 65537,

which differ by p = 196611, while k∆2 · 2k∞ = 262148 < q/2 for either reported ciphertext prime. The small-error premise of Theorem 4 is therefore satisfied and its conclusion still fails, on a single coefficient.

Proposition 4.3 (Coefficient push-forward mismatch) Let q be prime with p < q/2, let σ be any section, and let ν be a distribution on Z. If ν charges more than p2 integers that are pairwise distinct modulo q, then τ# ν 6= γ# ν.

Proof The map γ factors through x mod p2 , and there are exactly p2 residue classes modulo p2 , so γ takes at most p2 values and γ# ν is supported on at most p2 points. For τ , write ∆2 = p1 k with k = [p−1 1 ]p2 . Then 1 ≤ k < p2 ≤ p < q and gcd(p1 , q) = 1, so both factors are units modulo the prime q and ∆2 is a unit. Hence τ (x) = τ (x′ ) forces x ≡ x′ (mod q), so τ induces a bijection from the residues modulo q charged by ν onto the support of τ# ν. By hypothesis that support has more than p2 points. Two distributions with different support cardinalities are distinct.



Corollary 4.4 (Polynomial push-forward mismatch) Assume the hypotheses of Proposition 4.3 and let χ sample the n coefficients of e independently from ν. Then T# χ 6= C# χ.

Proof Both T and C act coefficientwise, so T# χ = (τ# ν)⊗n and C# χ = (γ# ν)⊗n . A product measure is determined by its marginals, and the marginals differ by Proposition 4.3.



The hypothesis is mild. A centered binomial Bη charges 2η +1 consecutive integers, pairwise distinct modulo q when 2η + 1 ≤ q , so the result applies whenever p2 < 13

2η + 1 ≤ q . An untruncated discrete Gaussian assigns positive mass to every integer and therefore charges more than p2 residues, since q > p2 . Collapse of the kind studied in Section 3 is the opposite extreme, in which γ# ν degenerates to a point mass.

Example 4.5 (Separation at the parameters of [7]) Take p1 = 65537 and p2 = 3 as reported, and let q = 35175245135873, one of the two reported ciphertext primes, so that ∆2 = 131074 and p = 196611 < q/2. Let ν be the centered binomial B2 , taking −2, −1, 0, 1, 2 with probabilities 1/16, 4/16, 6/16, 4/16, 1/16. Since ν charges five integers that are pairwise distinct modulo q and 5 > 3 = p2 , Proposition 4.3 applies. Concretely, γ collapses {−2, 1} onto one point and {−1, 2} onto another, so under the least-nonnegative section γ# ν :

6 0 7→ 16 ,

5 131074 7→ 16 ,

5 65537 7→ 16 ,

whereas τ# ν retains all five atoms with the binomial weights. The total variation distance between these coefficient laws is 3/8. Under the centered section it is 5/8. The example satisfies the small-error premise used in the proof of Theorem 4, namely |∆2 e| < q/2, and does so for every sample. At the reported n = 8192, every coefficient of e is bounded by 2, so k∆2 ek∞ ≤ 2∆2 = 262148,

√ k∆2 ek2 ≤ 2∆2 n < 2.38 × 107 ,

against q/2 = 17587622567936.5. The counterexample therefore lies inside the regime the transformation assumes.

Corollary 4.6 (Near-disjointness at the reported dimension) Under the hypotheses of Example 4.5, with χ = ν ⊗n , TV(T# χ, C# χ) ≥ 1 −

5
n 8

for the least-nonnegative section, and 1 − (3/8)n for the centered section. At n = 8192 the first bound exceeds 1 − 10−1672 and the second exceeds 1 − 10−3489 .

14

Proof Let S be the support of γ# ν, so that C# χ is supported on S n . From the table above, τ (x) ∈ S only for x ∈ {0, 1} under the least-nonnegative section, of total mass 6/16 + 4/16 = 5/8, which by Lemma 4.1 is exactly the probability that a coefficient satisfies the identity of Theorem 4, and only for x = 0 under the centered section, of mass 6/16 = 3/8. By independence, T# χ(S n ) is (5/8)n and (3/8)n respectively. Taking A to be the complement of S n gives C# χ(A) = 0 and TV ≥ T# χ(A) − C# χ(A). The numerical bounds follow from the exact integer inequalities 101672 58192 < 88192 ,

103489 38192 < 88192 . 

At the reported dimension their total variation distance is therefore exponentially close to one.

Remark 4.7 (A smaller illustration) The same phenomenon is visible at toy parameters. For p1 = 3, p2 = 2, q = 17 and ν uniform on {−1, 1}, both sections send the CRT class with residues (0, 1) to the integer 3, so γ# ν is the point mass at 3 while τ# ν is uniform on {14, 3} ⊂ Z17 , at total variation distance 1/2. This law has only p2 points modulo q, so it does not satisfy the hypothesis of Proposition 4.3: the condition is sufficient, not necessary.

The law that the reduced encoder actually induces is the push-forward

ψ = (e 7→ Eσ,q (0, e))# χ.

This identity determines ψ , but it does not by itself offer a reduction from ordinary RLWE. An ordinary RLWE sample exposes as + e, not e, so the encoder cannot be applied to the sample. Establishing hardness for ψ requires an argument that does not presuppose access to the error term. If the unreduced lift of Definition 2.2 is used instead, then Eraw,q (0, e) = ∆2 e. Under the prime-modulus condition ∆2 is a unit modulo q , so scaling both components 15

of an ordinary RLWE sample by ∆2 is algebraically consistent with that map and preserves uniformity of the first component. The two encoders thus behave differently with respect to the transformation, which is why the choice between them belongs to the definition of the construction. Scaling by p2 gives an exact equivalence for ordinary RLWE.

Theorem 4.8 (Scaling equivalence and error collapse under the reduced encoder) Let χ0 be any distribution on integer polynomials and let χ = (x 7→ p2 x)# χ0 . Assume p2 is a unit modulo q.

1. With the secret drawn uniformly from Rq , ordinary RLWE with error law χ is exactly and efficiently equivalent to ordinary RLWE with error law χ0 . 2. The same holds when a small secret is scaled alongside the error, that is when s = p2 s0 and e = p2 e0 with s0 , e0 ← χ0 . 3. Every sample of χ lies in p2 R, so under any zero-preserving section the reduced CRT encoder maps it to zero. The confinement hypotheses of Theorems 3.1 and 3.2 are therefore satisfied, and their conclusions hold whenever the remaining hypotheses of each are met.

Proof For the first part, let b = as + p2 e0 with s uniform. The public map (a, b) 7→ −1 −1 (p−1 2 a, p2 b) gives second component (p2 a)s+e0 , leaves the first component uniform because

p2 is a unit, and is inverted by multiplication of both components by p2 . For the second part, b = as + e = p2 (as0 + e0 ), so (a, b) 7→ (a, p−1 2 b) returns (a, as0 + e0 ) exactly and leaves the first component untouched. Both maps are bijections on samples, carry the uniform comparison ensemble to itself, and therefore preserve advantage in both directions. The third part is the computation of Theorem 3.1 applied to a law supported on p2 R.



The invertible scaling by p2 preserves the ordinary-RLWE problem, whereas the reduced CRT encoder erases the resulting errors. 16

4.1 Relation to the conditional security theorem Theorem 5 of [7] is conditional on decisional CRT-RLWE hardness for the selected error law. For p2 B1 under the reduced encoder, the CRT-RLWE error is identically zero, so that premise is false. Theorem 3.2 therefore exhibits an insecure instantiation satisfying the stated distributional conditions rather than a contradiction of the conditional implication itself. Theorem 4 is intended to transfer ordinary-RLWE hardness to the CRT-RLWE distribution, but Proposition 4.3 shows that its transformation does not preserve the error law. Thus the hardness premise of Theorem 5 is neither automatic for the permitted distributions nor established by Theorem 4.

5 Implications for the security formulation The reduced CRT encoder and the unreduced integer lift induce different elements of Rq , by Lemma 2.3, and the difference pKσ (m, e) need not vanish because p is a unit modulo q . A correctness or security analysis carried out for one of the two maps therefore does not transfer to the other, and the embedding of the CRT output into

Rq is part of the mathematical definition of the construction. For the reduced encoder, the error distribution relevant to security in Rq is the push-forward ψ , not the sampled law χ. Security depends on ψ , and ψ can degenerate even when χ is nonconstant, bounded, efficiently samplable, and subgaussian: the confined laws of Section 3 give ψ equal to the point mass at zero. Excluding support contained in p2 R removes this exact collapse; a security statement for the resulting push-forward requires an appropriate hardness assumption.

6 Conclusion Under every zero-preserving realization in Rq , the reduced CRT function erases errors supported on p2 R: e ∈ p2 R gives Eσ,q (0, e) = 0. The public key then satisfies b = 17

as, which yields exact secret recovery s = a−1 b on the unit event and, when the challenge errors are confined and the two message encodings differ, recovery of the encoded challenge message for every public multiplier by polynomial gcd and CRT decomposition, with chosen-plaintext advantage 1/2. The coefficient law p2 B1 realizes these hypotheses while meeting the discreteness, efficient-sampling, boundedness, and subgaussian conditions imposed on the error distribution. For the least-nonnegative representative, the discrepancy between the reduced CRT encoder and the scaled ordinary-RLWE error is exactly p⌊ke/p2 ⌋, a multiple of p that need not vanish modulo q . Under the no-wrap premise invoked in the proof of Theorem 4, equality modulo q holds exactly when 0 ≤ ke < p2 ; at the parameters of [7], the coefficient e = 2 already refutes the identity while satisfying that premise. More generally, the two maps induce different error laws whenever the coefficient distribution charges more than p2 integers that are pairwise distinct modulo q , including a centered binomial Bη whenever p2 < 2η + 1 ≤ q , and an untruncated discrete Gaussian. At the reported parameters, B2 gives coefficient-level total variation distance 3/8 for the leastnonnegative section and 5/8 for the centered section, while at the reported dimension the corresponding polynomial distributions have total variation distance exponentially close to one. Theorem 4 therefore does not establish the same-law reduction; the reduced encoder instead induces the push-forward law ψ . The key-recovery result is specific to residue-confined errors, whereas the reduction mismatch applies more generally.

Acknowledgements AI tools were used in manuscript editing, development and stress-testing of the analysis, exploratory proof checking, verification of algebraic and numerical calculations, and drafting auxiliary code. AI suggestions were treated as exploratory. The authors 18

independently verified all mathematical claims, calculations, and conclusions and take full responsibility for the article.

References [1] Castryck W, Iliashenko I, Vercauteren F (2016) On error distributions in ringbased LWE. LMS Journal of Computation and Mathematics 19(A):130–145. https://doi.org/10.1112/S1461157016000280 [2] Chen H, Lauter KE, Stange KE (2017) Attacks on the search RLWE problem with small errors. SIAM Journal on Applied Algebra and Geometry 1(1):665–682. https://doi.org/10.1137/16M1096566 [3] Eisentraeger K, Hallgren S, Lauter K (2014) Weak instances of PLWE. In: Selected Areas in Cryptography – SAC 2014, Lecture Notes in Computer Science, vol 8781. Springer, Cham, pp 183–194, https://doi.org/10.1007/978-3-319-13051-4 11 [4] Elias Y, Lauter KE, Ozman E, Stange KE (2015) Provably weak instances of ring-LWE. In: Advances in Cryptology – CRYPTO 2015, Lecture Notes in Computer Science, vol 9215. Springer, Berlin, Heidelberg, pp 63–92, https://doi.org/10.1007/978-3-662-47989-6 4 [5] Lyubashevsky V,

Peikert C, Regev

O

(2013) On ideal lattices

and

learning with errors over rings. Journal of the ACM 60(6):43:1–43:35. https://doi.org/10.1145/2535925 [6] Peikert C (2016) How (not) to instantiate ring-LWE. In: Security and Cryptography for Networks – SCN 2016, Lecture Notes in Computer Science, vol 9841. Springer, Cham, pp 411–430, https://doi.org/10.1007/978-3-319-44618-9 22 19

[7] Pradhan AK, Dutta A, Jangir H, Das D (2026) A new CRT-based fully homomorphic encryption. IACR Communications in Cryptology 3(2):39. https://doi.org/10.62056/akdk5w4e-, URL https://cic.iacr.org/p/3/2/39

20

Related documents

• XMSS: eXtended Merkle Signature Scheme#139244
• NIST SP 800-56Cr2: Recommendation for Key-Derivation Methods in Key-Establishment Schemes#3020
• An Erroneous Argument for Error Theory#108220
• Figure 2.42 [2nd ed.]/Figure 2.39 [1st ed.]: Phase 1 of the Quine-McCluskey algorithm to determine the function for g. Part 2.#451635
• Figure 2.36 [2nd ed.]/Figure 2.33 [1st ed.]: Phase 2 of the Quine-McCluskey algorithm: (a) Initial table; (b) Table with essential prime implicants circled and rows and columns crossed out.#451629