Decision Attacks on Known-Covariance Ring-LWE via Public Gram Determinants

What it is

Anis Bkakria's ePrint 2026/2638 (received 25 October 2026, approved 26 October 2026, preprint) attacks Known-Covariance Ring-LWE (KCov-RLWE), introduced by Micciancio and Suhl for simulation-secure threshold encryption. Its decisional hardness was left open. The paper gives explicit polynomial-time distinguishers between real and uniform KCov samples and says they invalidate the KCov pseudorandomness assumption in the families it quantifies.

How it works

The public sample and the covariance hint together form a bordered Gram matrix. Its determinant exposes a hidden residual that is distributed differently for genuine and uniform samples. After the ring is split into finite-field components, the residual takes one of two forms:

• A product across reciprocal components.
• A Hermitian norm, when a component is preserved by conjugation. The paper calls this case a particularly strong distinguishing signal.

Reduction modulo any divisor preserves the KCov real and random experiments exactly. So any attackable odd prime divisor of a composite modulus carries the distinguisher over with no loss of advantage.

Preconditions / Affected

• Ring rank one, with broad families of prime moduli.
• Composite moduli that have a suitable odd prime divisor.
• The one-sample setting is covered globally in the self-reciprocal regime. In the completely split regime it is covered locally, and only under the coefficient-product Gaussian specialization.
• For odd prime moduli with m≥2, the paper gives a complete classification of how the residual attack behaves.

What to do

The abstract states no patch or parameter fix. Anyone building on KCov-RLWE, including the Ring-PKE sketch that motivated it, should check their modulus against the paper's classification. Prime moduli, and composite moduli with an odd prime factor, fall in the attackable families.

Caveats

• Pure power-of-two moduli are outside the divisor-reduction extension.
• When the relevant residue fields are large enough, the guaranteed advantage in the reciprocal case can become negligible.
• The paper does not show that every parameter choice in the Ring-PKE sketch is insecure.
• It gives no direct IND-CPA break of the full threshold-encryption construction.
• This analysis rests on the abstract and metadata alone. The page text gives no concrete parameters, advantage bounds or running times.