1
$\begingroup$

(I am sure this question might have been asked before). I know that $\mathrm{LLL}$ algorithm can find a short, not necessarily the shortest, basis in polynomial time. My question is: if we construct a lattice from $\textbf{A}$ and then run $\mathrm{LLL}$ on the lattice, would it help in finding the solution or clue to find the solution to $\mathrm{SIS}$ problem? specially for small dimension matrices.

$\mathbb{Z}^{n}_{q} = n$ dimensional vectors modulo $q$ (for simplicity say, $q$ is prime and $n = m$)

$\textbf{Goal}$: find nontrivial short vector $z \in \mathbb{Z}^m$ such that:

$\begin{pmatrix}\\ \dots \text{A} \dots \\ \\\end{pmatrix} \times \begin{pmatrix}\\z\\\\\end{pmatrix} = 0 \in \mathbb{Z}^{n}_{q}$

Note that $\textbf{A}$ is a $n\times m$ matrix and $z$ is a $m \times 1$ matrix or vector.

I understand that $\mathrm{LLL}$ solves Merkle–Hellman knapsack cryptosystem. But it is different from $\mathrm{SIS}$ problem.

$\endgroup$
  • $\begingroup$ $L=\{ {\bf x}\in {\bf Z}_q^{n} : A{\bf }{\bf x}={\bf 0} \}$ is a lattice. Finding a basis and applying LLL provides you $\it{small}$ vectors. $\endgroup$ – 111 Jan 6 '17 at 17:47
  • $\begingroup$ An important property of SIS is that the matrix $\mathbf{A}$ is uniformly distributed. Among other things, this implies that with non-negligible probability $\mathbf{A}$ has $n$ linearly independent columns. Therefore, using $n = m$ implies that with overwhelming probability, the only vector $\mathbf{z}$ satisfying the equation $\mathbf{A}\mathbf{z} = 0 \mod q$ is the the zero vector (i.e. your instance of SIS has no valid solution). $\endgroup$ – Hilder Vítor Lima Pereira Dec 12 '18 at 7:40
  • 1
    $\begingroup$ When the parameters are set appropriately (e.g., when $n$ is large enough and the SIS norm bound $\beta$ is substantially smaller than $q$), applying LLL or stronger forms like BKZ (with reasonable block size) only yields a vector $z$ whose norm is slightly less than $q$, but not less than $\beta$. BKZ with a very large block size may eventually find a short enough vector, but the runtime will be enormous. $\endgroup$ – Chris Peikert Jan 11 at 19:26
2
$\begingroup$

As mentioned by 111 in the comments, solving SIS comes down to finding a short vector in the underlying lattice of some prescribed norm $\beta$ or less. Lattice basis reduction methods like LLL help in the sense that they can reduce a basis with long lattice vectors to a basis with shorter, more orthogonal lattice vectors.

If the reduction is strong enough (LLL, or BKZ with large enough block size) then you expect that the first basis vector of the reduced basis is a solution to SIS. (How strong your basis reduction should be to find a solution depends on $n, m, q$ and on the required length of the short lattice vector, $\beta$.)

So to answer your overall question: LLL can solve the easiest SIS instances (with large $\beta$), and can assist in solving harder SIS instances (with small $\beta$) by finding a shorter basis, which makes finding even shorter lattice vectors a bit easier.

$\endgroup$
  • $\begingroup$ I think this answer is not precise... There is no mention to the parameter $\beta$, which controls the length of the accepted solutions (and of course, is never set to a value exponential in $n$, which already rules out LLL). And what are the easiest instances of SIS since it is defined using uniformly random matrices? $\endgroup$ – Hilder Vítor Lima Pereira Dec 12 '18 at 7:51
  • $\begingroup$ @HilderVítorLimaPereira Both the question and answer do not mention any parameter $\beta$ - can you elaborate? And by easy I mean instances where the parameters $n, m, q$ may not be set appropriately, so that even LLL suffices to find a solution. (If the parameters are set properly, LLL of course won't solve SIS, but it may be useful as a first step towards heavier machinery such as BKZ.) $\endgroup$ – TMM Dec 19 '18 at 15:26
  • $\begingroup$ Well, what I meant is that we can't even talk about a solution to SIS without talking about $\beta$, since this is the parameter that defines the length of the vectors that are considered to be solutions. The question is also not formally defined since it just asks for "short vectors". $\endgroup$ – Hilder Vítor Lima Pereira Jan 7 at 18:31
  • $\begingroup$ @Hilder I've edited the answer to cover the parameter $\beta$ as well. $\endgroup$ – TMM Jan 8 at 11:59

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.