1
$\begingroup$

I know that the $\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 the $\mathrm{SIS}$ problem (especially 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.

Improve this question
$\endgroup$
3
  • $\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, 2017 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 Vitor Lima Pereira
    Dec 12, 2018 at 7:40
  • 2
    $\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, 2019 at 19:26

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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 Vitor Lima Pereira
    Dec 12, 2018 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, 2018 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 Vitor Lima Pereira
    Jan 7, 2019 at 18:31
  • $\begingroup$ @Hilder I've edited the answer to cover the parameter $\beta$ as well. $\endgroup$
    – TMM
    Jan 8, 2019 at 11:59

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.

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