I am working on an LWE instance where q is a power of 2 and I'm wondering if there is any literature about attacks in this context, especially if there are any attacks which work significantly better. I know about the general attacks (combinatorial, lattice based, algebraic) found in Concrete Hardness of LWE for example, but I don't know if they get better for this special q. I would be grateful in fact for any LWE literature at all which talks about this context.

The q used in the Frodo key exchange (based on LWE) are powers of 2, and this is one of the alternate candidates for key exchange in the NIST PQ competition, so power of 2 q's seem to work OK.

  • 2
    $\begingroup$ If there is a modulus $q$ that admits particularly efficient attacks, couldn't you just modulus-switch your LWE samples to exploit this? In most situations this will introduces some additional "rounding" error of course. $\endgroup$ – Mark Jan 12 at 20:56
  • $\begingroup$ @Mark That's a good point, and the additional rounding error is quite small anyway. $\endgroup$ – Partha Jan 12 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.