Answers are grounded in this paper and cite their sources.
We revisit polynomial-memory Grover-type quantum attacks on fixed-composition ternary Learning with Errors (LWE) instances, where the numbers of +1, −1, and zero coordinates are prescribed. Our focus is the search variant described in Section 7 of van Hoof, Kirshanova, and May; we do not reassess the full quantum-walk time–memory tradeoff developed in that work. We compare their representation-based polynomial-memory variant, which applies amplitude amplification to decompositions of the secret, against direct amplitude amplification over the fixed-composition ternary secret space. In the standard oracle-exponent model, and under an explicit indexed encoding of fixed-composition ternary vectors, the direct search gives a smaller dominant oracle-call exponent for all concrete and asymptotic parameter regimes considered here. The main reason is formalized by a counting obstruction: in a representation-only Grover search over decompositions, the multiplicity of representations gives only a square-root gain, whereas the search space is enlarged to a Cartesian product. Thus, in the pure polynomial-memory representation-Grover model considered here, direct amplitude amplification gives the sharper quantum baseline for ternary-LWE key search.
No takes yet. Share an insight, caveat, or question.
Kalam et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: