Hardness of recovering the Ring-LWE error modulo two
A reduction a deployed-style NTRU analysis relies on, and does not have
Motivation
Search Ring-LWE asks, given \((h, hs+e)\), for the error vector \(e\). A natural weakening asks only for \(e \bmod 2\) — the parities of the error coefficients. Recovering \(e\) obviously gives its parities, so one direction is free. The question is whether the weakening is genuinely weaker.
The reason to care is not curiosity about a variant. Duman, Hövelmanns, Kiltz, Lyubashevsky, Seiler and Unruh’s treatment of highly-efficient NTRU instantiations uses the parity problem in its security argument, and the strength of that argument is exactly the strength of the equivalence. The paper is candid about the state of it: “While we do not have a formal reduction from R-LWE to R-LWE\(_2\), based on the state of the art of how Ring-LWE problems are solved, the two are essentially equivalent.”
So this is an assumption doing real work in the analysis of a concrete, performance-oriented scheme, justified by cryptanalytic experience rather than by a reduction. That is a normal situation in lattice cryptography and an unusual one to find stated so plainly.
Provenance and history
From Duman, Hövelmanns, Kiltz, Lyubashevsky, Seiler and Unruh, A Thorough Treatment of Highly-Efficient NTRU Instantiations, ePrint 2021/1352, PKC 2023, pp. 65–94. The parity variant is defined on p. 19 of the ePrint posting, alongside the sentence declining a reduction.
Which version this is, and why it matters here. The ePrint posting has a single revision, received 7 October 2021, and predates the PKC 2023 publication. This site has read only that posting. If the reduction was supplied, or the claim reworded, for the published version, that is not visible here. Anyone acting on this page should check the PKC text first — the gap between preprint and proceedings is exactly where a “we do not have a reduction” remark tends to get revised.
What is actually missing
The paper does not leave a blank; it substitutes two heuristics, and each falls short in a different way.
| heuristic | what it shows | why it is not the reduction |
|---|---|---|
| rerandomisation | more than one bit per coefficient can be extracted | it drifts off the prescribed centred binomial error distribution, so the problem it reduces from is not the one specified |
| first-is-errorless | the parity problem is as hard as a decision variant in which one integer coefficient carries no error | that variant is nonstandard; the argument that it is as hard as Ring-LWE is again “the best-known algorithms do not distinguish them” |
Tracked here as c/0034, which states the missing reduction as a conjecture with explicit polynomial loss.
Two directions, both interesting
A proof removes an assumption from the analysis of a deployed-style scheme — the useful outcome, and the one the paper’s own framing expects.
A refutation would be a separation between two Ring-LWE variants that everybody currently treats as equivalent. That is the more surprising outcome and arguably the more valuable one, because it would say the cryptanalytic intuition the paper leans on is wrong somewhere specific.
Nothing on this page depends on which is true. What it records is that the question is open, that a concrete construction rests on the answer, and that the source says so itself.