0
$\begingroup$

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<m$, we can employ null space algorithms to get a set of basis vectors $B$, then does the short integer solution $x\in Span(B)$?
$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – X.H. Yue
    Commented May 29 at 8:01
  • $\begingroup$ I create a new question about the continuation of this question. $\endgroup$
    – X.H. Yue
    Commented May 29 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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