# Questions about SIS hard problem

The definition of $$\mathrm{SIS}_{q,n,m,\beta}$$ problem is as below.

Let $$A\in\mathbb{Z}_q^{n\times m}$$ be an $$n\times m$$ matrix with entries in $$\mathbb{Z}_q$$ that consists of $$m$$ uniformly random vectors $$\boldsymbol{a_i}\in\mathbb{Z}_q^n{:}A=[\boldsymbol{a_1}|\cdots|\boldsymbol{a_m}]$$. Find a nonzero vector $$\boldsymbol{x}\in\mathbb{Z}^m$$ such that for some norm $$\|\cdot\|:$$ \begin{aligned}&\bullet0<\|\boldsymbol{x}\|\leq\beta, \bullet f_A(\boldsymbol{x}):=A\boldsymbol{x}=\boldsymbol{0}\in\mathbb{Z}_q^n.\end{aligned}.

My questions are:

• If $$n=m$$, the full rank matrix $$A$$ does not have null space, then $$x$$ is identity zero vector. In such case, is the SIS problem nonsense?
• If $$n, we can employ null space algorithms to get a set of basis vectors $$B$$, then does the short integer solution $$x\in Span(B)$$?

## 1 Answer

full rank matrix

$$A$$ is not full rank automatically. It is only full rank with high probability. This is easiest to see by considering $$n = m = q = 2$$. Fully half of the matrices of the form

$$\begin{pmatrix}a & b\\ c & d\end{pmatrix}$$ for $$a,b,c,d\in\{0,1\}$$ are singular. For larger $$n,m,q$$ the probability a uniformly random (square) matrix is singular becomes very small, but it is not 0 for any choice of parameters.

we can employ null space algorithms to get a set of basis vectors $$B$$, then does the short integer solution $$x\in\mathsf{span}(B)$$?

Your question is not entirely clear. $$x \in \ker A$$ by construction. It appears if you are asking if $$B$$ is a basis for the subspace $$\ker A$$, then is $$x\in\ker A$$ in $$\mathsf{span}(B)$$? The answer is trivially yes, but this has nothing to do with SIS, and is instead just a basic linear-algebraic fact.

• Thank you for your response. I am new to lattice-based cryptography, so there may be errors in my questions. Restating the first question: If $A$ is a full rank square matrix, does the SIS problem become irrelevant in such a condition? Commented May 29 at 8:01
• I create a new question about the continuation of this question. Commented May 29 at 10:11