# How is the matrix A related to the lattice space L in SIS?

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?

## 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.

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.