# Construct new SIS solutions from given ones

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}$ ?

• 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. Jul 2, 2016 at 18:38
• Finding a solution without the size restriction is indeed simple. Therefore, I ask for a solution respecting the size constraint.
– user27950
Jul 2, 2016 at 19:41
• It's not known how to do this without sacrificing the norm constraint by a little (e.g., a small constant factor). Jul 6, 2016 at 21:30
• @Chris: You say, "it is not known". Does this mean that it is conjectured as a hard problem?
– user27950
Jul 11, 2016 at 14:15
• 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. Jul 11, 2016 at 14:19