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}$ ?
$\begingroup$
$\endgroup$
5
-
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$– pg1989Jul 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$– user27950Jul 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$– Chris PeikertJul 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$– user27950Jul 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$– Chris PeikertJul 11, 2016 at 14:19
Add a comment
|