For large values of $q$, we know that there are worst-case lattice problems which reduce to the average-case short integer solution (SIS) problem. Does this means that for $q=2$, the SIS problem is NOT hard-on-average?

  • 3
    $\begingroup$ No, it just means we don't have such theoretical evidence for its hardness. The problem does still appear to be quite hard, though. $\endgroup$ Sep 10, 2017 at 2:29
  • $\begingroup$ please define technical terms like SIS. $\endgroup$
    – kodlu
    Sep 10, 2017 at 2:36
  • $\begingroup$ @ChrisPeikert: Thanks. Is there any constructions based on this version of SIS? If yes, would you please cite some papers which address this issue? $\endgroup$
    – Hamidreza
    Sep 10, 2017 at 8:18
  • 2
    $\begingroup$ With such small moduli, you're better off looking into coding theory. SIS with $q = 2$ looks similar to finding a low-weight codeword in a random linear code. $\endgroup$ Sep 12, 2017 at 0:14


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.