3
$\begingroup$

Is the matrix $A= (b_1|,...,|b_m)$ where B=$(b_1,...,b_m)$ is the basis of the lattice space, $L$(B)? Not sure if the answer is trivial however I'm having trouble seeing how SIS is a lattice hard problem when it's definition doesn't seem to include a lattice.

Following this, the restriction on the the vector $x$ $\leq \beta$. Where does $\beta$ come from? I understand by restricting the value of $\beta$ you increase the hardness of the problem but at what point do you is it defined?

$\endgroup$
3
$\begingroup$

About the basis

As stated in the other answer, the lattice directly related to SIS is actually the $q$-ary lattice defined as

$$\mathcal{L}_q^\bot(A) := \{ u \in \mathbb{Z}^n : Au = 0 \mod q \}.$$

And its basis is not the matrix $A$. To construct a basis to this lattice, one usually suppose that $A$ has $n$ linearly independent columns (let's say, the first $n$) and write $A = [A_1 \quad A_2]$ with $A_1$ being an $n\times n$ matrix invertible over $\mathbb{Z}_q$, then the following matrix $B$ is a basis:

$$ B = \begin{pmatrix} ~q\cdot I_n~ & -A_1^{-1}A_2 \\ ~\vec 0~ & I_{m-n} \end{pmatrix} \in \mathbb{Z}^{m \times m} $$

About the hardness

Actually, it could be a hard problem regardless its connections with lattice problems. But it is connect to lattices in several ways. First, it is obvious that finding short vectors in $\mathcal{L}_q^\bot(A)$ gives us solutions to SIS. Moreover, it has been proved that if one can solve SIS in polynomial time in average, then one can solve hard lattice problems.

Roughly speaking: if you had an algorithm to solve SIS with non-negligible probability (for instance, your algorithm could work one time out of one million), then you would have an algorithm to solve approximate versions of GapSVP and SIVP).

About the value $\beta$

The value $\beta$ is a parameter of the problem. It is easy to find $u$ such that $Au = 0 \mod q$ (just use Gaussian elimination), what may be hard is to find a short vector satisfying this equation. But how do you define short? Using $\beta$ as an upper bound to the length.

These are standard facts: if $\beta \ge q$, then $u = (q, 0, 0,..., 0)$ is a valid solution, therefore, SIS is trivial for such values of $\beta$. If $\beta$ is too small, then maybe there is no valid solution. If $\beta \ge \sqrt{m}$ and $m \ge n\log q$, then it is guarantee that there exist at least one valid solution.

I wrote some notes about SIS weeks ago. If you want, check it here. At least the section References therein will be useful.

$\endgroup$
3
$\begingroup$

If you are solving a SIS instance $As = 0$ over $\mathbb{Z}_q$ then this can be seen as finding a short non-zero vector from the lattice $\{z \in \mathbb{Z}^m \ \mid Az = 0 \in \mathbb{Z}_q^n\} \supset q \mathbb{Z}^m$. Thus it is not the same as your $L(B)$.

On the other hand, showing that SIS is as hard as certain lattice problems is not obvious and follows from this work and a long sequence of works establishing progressively stronger results about the hardness of the SIS. You can find some general information in this survey.

$\endgroup$

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.