PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Lukasz Olejnik, Bartosz Naskrecki

arXiv:2608.21989v1cs.CR

TL;DR

The paper examines whether CRT-RLWE supports the claimed security and Ring-LWE reduction. It analyzes reduced CRT encoding and shows key recovery, plaintext recovery, and error-distribution mismatch under admissible laws.

  • Problem

    The paper addresses whether the CRT-FHE scheme is secure for its assumed error laws and whether its transformation preserves the Ring-LWE error distribution.

  • Method

    The paper analyzes the reduced CRT encoder, corresponding polynomial maps, residue-confined errors, and the reduction discrepancy across moduli.

  • Results

    Residue-confined errors enable secret recovery by ring inversion and plaintext recovery with chosen-plaintext advantage 1/2, while the proposed reduction fails to preserve error distributions.

  • Takeaways & Limitations

    The CRT-FHE security claim and the claimed same-law reduction are not established for the analyzed admissible error laws.

  • Takeaways & Limitations

    The confinement mechanism is specific to residue-confined errors, while the reduction mismatch applies more broadly.

Abstract

from arXiv · show

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 $p_1p_2$ while its output is used modulo a coprime modulus $q$, so under every zero-preserving section an error in $p_2\R$ encodes to zero. The law $p_2B_1$ is so confined, meets the stated conditions, and decrypts correctly. Confinement is not a weakness of scale: scaling any baseline law by $p_2$ leaves its ordinary Ring-LWE problem exactly equivalent, while the reduced encoder destroys every error it produces. The reduction discrepancy is a multiple of $p_1p_2$ 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 $B_2$ separates the coefficient laws at total variation distance $3/8$, and at the reported dimension that distance between the induced polynomial laws is exponentially close to one.

1 Introduction

The paper argues that Pradhan et al.'s CRT-FHE construction is insecure for permitted error laws and that its claimed Ring-LWE transformation does not preserve errors. Both failures arise because reduced CRT encoding can erase residue-confined errors before ciphertext reduction modulo q.

  • Security failure: Residue-confined errors let an attacker recover the secret exactly when the public multiplier is a unit.For public-key errors in p2R, the public relation becomes b = as.
  • Security failure: Polynomial gcd and CRT decomposition recover the encoded challenge message for every public multiplier, yielding chosen-plaintext advantage 1/2.This attack applies when challenge errors are confined as well.
  • Admissible error law: The law p2B1 is discrete, efficiently samplable, bounded, subgaussian, and supported on p2R, so it satisfies the stated hypotheses while enabling the attack.Its variance proxy is p2.
  • Reduction failure: The same-law transformation fails because the reduced CRT encoder and the scaled-error map can produce different error distributions.The discrepancy has closed form p⌊ke/p2⌋; under the no-wrap premise, the claimed identity holds only for 0 ≤ ke < p2, which becomes e ∈ {0, 1} at the reported parameters.
  • Mechanism: The mechanism precedes algebraic projection: a non-injective encoder is inserted between sampled errors and the ring elements carrying them.For residue-confined laws the resulting failure is exact and is attributed to encoding rather than the ambient number field.

2 CRT encoding and representative lifts

This section distinguishes reduced CRT encoding from an unreduced integer lift when representatives cross from modulus p1p2 to the coprime ciphertext modulus q. The two maps differ by retained multiples of p1p2, and zero-preserving reduced encoding erases errors in p2R.

  • CRT encoding: The CRT function consumes e modulo p2, while ciphertext reduction modulo q occurs only after encoding.The coefficient distribution therefore samples integer-polynomial representatives before the encoding step.
  • CRT encoding: A coefficientwise section reduces representatives modulo p and is zero-preserving when it maps zero to zero.Least-nonnegative and centered representatives are examples of zero-preserving sections.
  • Representative lifts: For m = 0 and e = p2r, every zero-preserving reduced encoder maps the error to zero, whereas the unreduced lift does not.This separates the two encoders under the stated parameter conditions.
  • Representative lifts: The reduced CRT encoder and unreduced integer lift are distinct maps into Rq, although their integer polynomials differ coefficientwise by multiples of p1p2.Because gcd(p, q) = 1, those multiples need not vanish modulo q.
  • Representative lifts: Theorem 4's identity with the integer Δ2e corresponds to the unreduced lift, not the reduced encoder used in KeyGen.The distinction is central because Section 3 analyzes the reduced encoder from Definition 2.1.

3 Consequences of error collapse

Residue-confined errors collapse under the reduced encoder, enabling key recovery for unit public multipliers and plaintext recovery for every multiplier. The paper gives an efficiently samplable law satisfying the stated error conditions while remaining both correctly decryptable and insecure.

  • Errors supported on p2R encode to zero under the reduced, zero-preserving CRT encoder.This collapse makes the public-key equation reduce to b = as.
  • A passive algorithm recovers s = a^-1b whenever the public multiplier a is a unit, in polynomial time.The inverse is computed by linear algebra over Zq, and unit multipliers occur with non-negligible probability under the stated factorization conditions.
  • Theorem 3.2 recovers the challenge plaintext with probability one for every multiplier, yielding chosen-plaintext advantage 1/2.The attack combines residues modulo the factors of F through polynomial CRT and runs in polynomial time.
  • The law p2B1 is discrete, efficiently samplable, supported on p2R, and satisfies the stated subgaussian and tail conditions.Its coefficients are sampled from {-p2, 0, p2} using two fair coin flips per coefficient.
  • Every fresh ciphertext decrypts correctly under the confined-law instantiation, so the construction is simultaneously correct and insecure.With no effective error term, the message encoding remains bounded below q/2 and reduces back to the message.
  • The explicit attack is a uniform deterministic polynomial-time adversary succeeding with probability one at every security parameter.This applies to reduced-CRT instances meeting Theorem 3.2's hypotheses with errors drawn from p2B1.

4 Error-distribution mismatch in the RLWE

The proposed transformation can change the error law because reduced and unreduced CRT encoders are different maps. This mismatch persists under the small-error premise and can become extreme for centered-binomial errors.

  • Encoder mismatch: The reduced CRT encoder and unreduced integer lift induce different elements of Rq, so analyses for one map do not transfer to the other.Their difference is pKσ(m, e), which need not vanish because p is a unit modulo q.
  • Failure under small error: The discrepancy identity holds only when ⌊ke/p2⌋ ≡ 0 (mod q), and under no-wrap conditions this forces ⌊ke/p2⌋ = 0.Thus the relevant condition is stronger than the stated small-error bound.
  • Failure under small error: Theorem 4’s small-error condition does not force the reduction discrepancy to vanish.At reported p1 = 65537 and p2 = 3, e = 2 violates the identity while ||∆2 · 2||∞ = 262148 < q/2.
  • Coefficient push-forwards: Proposition 4.3 shows that coefficient push-forwards differ whenever the original law charges more than p2 integers with distinct residues modulo q.The reduced map has support on at most p2 points, whereas the unreduced map preserves distinct charged residues.
  • Polynomial push-forwards: At n = 8192, the induced polynomial laws are exponentially close to disjoint.The reported bounds follow from coefficient-level identity probabilities of 5/8 and 3/8 for the two sections.

5 Implications for the security formulation

Security for the reduced encoder depends on its push-forward error law rather than the sampled law. That push-forward can degenerate even for bounded, efficiently samplable, subgaussian nonconstant errors.

  • Security formulation: For the reduced CRT encoder, security depends on the push-forward ψ, not directly on the sampled error law χ.The reduced encoder can map the sampled law to a different distribution in Rq.
  • Security formulation: ψ can be a point mass at zero even when χ is nonconstant, bounded, efficiently samplable, and subgaussian.The confined laws of Section 3 exhibit this degeneration.
  • Security formulation: A security statement for the resulting push-forward requires an appropriate hardness assumption.The ordinary RLWE reduction does not automatically supply hardness for ψ because its samples expose as + e rather than e.

6 Conclusion

The reduced CRT encoder erases residue-confined errors, enabling key recovery and plaintext recovery under an admissible law. The same reduction also breaks the claimed error-distribution-preserving transformation from ordinary Ring-LWE.

  • Residue-confined errors: Under every zero-preserving realization, errors in p2R encode to zero, making the reduced CRT encoder erase residue-confined errors.The encoder maps e ∈ p2R to Eσ,q(0,e) = 0.
  • Key and plaintext recovery: When the public multiplier is a unit, a single ring inversion recovers the secret as s = a^-1b.The conclusion states exact secret recovery on the unit event.
  • Key and plaintext recovery: Polynomial gcd and CRT decomposition recover encoded challenge messages for every public multiplier, yielding chosen-plaintext advantage 1/2.The attack applies when challenge errors are confined and the two message encodings differ.
  • Residue-confined errors: The law p2B1 satisfies the stated discreteness, sampling, boundedness, and subgaussian conditions while enabling correct decryption.This law realizes the attack hypotheses within the scheme's assumed error-distribution range.
  • Reduction mismatch: The reduced CRT expression and ordinary-RLWE lift can differ by a multiple of p that need not vanish modulo q.At the reported parameters, e = 2 refutes the claimed identity while satisfying the proof's small-error premise.
  • Reduction mismatch: The same-law transformation fails to preserve error distributions whenever the coefficient law charges more than p2 pairwise distinct residues modulo q.This includes centered binomial Bη when p2 < 2η + 1 ≤ q and an untruncated discrete Gaussian.
  • Reduction mismatch: At the reported parameters, B2 yields coefficient-level total variation distance 3/8, while the induced polynomial distributions are exponentially close to distance one.The corresponding polynomial-law separation is reported at the paper's dimension.
  • Scope: The key-recovery result is specific to residue-confined errors, whereas the reduction mismatch applies more broadly.The paper explicitly distinguishes the scope of these two conclusions.
Loading 2608.21989v1…