Assume we have a lattice SIS problem $A x = 0$, with $\Vert x \Vert < \beta$ and we are given $k$ solutions $x_1, \dots, x_k$ by, say an oracle.
Is it then hard or easy to construct from there a further solution $x_{k+1}$ ?

  • 1
    $\begingroup$ Just spitballing, but maybe take some linear combination of the existing solutions? The only problem is that the new $x_{k+1}$ might not be short enough. $\endgroup$
    – pg1989
    Jul 2, 2016 at 18:38
  • $\begingroup$ Finding a solution without the size restriction is indeed simple. Therefore, I ask for a solution respecting the size constraint. $\endgroup$
    – user27950
    Jul 2, 2016 at 19:41
  • 1
    $\begingroup$ It's not known how to do this without sacrificing the norm constraint by a little (e.g., a small constant factor). $\endgroup$ Jul 6, 2016 at 21:30
  • $\begingroup$ @Chris: You say, "it is not known". Does this mean that it is conjectured as a hard problem? $\endgroup$
    – user27950
    Jul 11, 2016 at 14:15
  • 2
    $\begingroup$ I haven't ever seen it conjectured as a hard problem, although it looks similar to some problems that have appeared before. E.g., k-SIS: given k SIS solutions, find a solution not in the subspace spawned by them. This has been proved as hard as SIS with some loss in parameters, by Boneh-Freeman and follow ups on k-LWE. $\endgroup$ Jul 11, 2016 at 14:19


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.