2
$\begingroup$

I'm a newer to the lattice theory, so there is a basic notion about "full rank" confusing me.

In some papers focusing on the lattice theory, they always use the full rank lattice (the number of basis vectors $m$ is equal to the dimension $n$ of the space $\mathbb{Z}^n$) as the research target, such as generating a hard lattice with short basis, solving some lattice problems. However, In some lattice problems, including SIS and LWE, they always introduce a random matrix $A$ with $m=poly(n)$ as basis vectors.

Therefore, I am confused that why the matrix $A$ in SIS and LWE is not full rank?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Although the matrix $A$ defines the SIS (or LWE) lattice, it is not a basis of the lattice. A basis $B$ can be derived from $A$, and $B$ will then be square, thus, the lattice will have full rank.

You can check this answer about the SIS problem.

Notice that this is similar to the fact that the public polynomial $h$ defines the NTRU lattice, but $h$ itself is not a basis of the lattice. Instead, $h$ can be used to derive a basis of the lattice.

You can read more about it on the classic A Decade of Lattice Cryptography, by prof. Peikert.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for your answer. However, I am still confused that whether the matrix $A$ in both SIS and LWE problems comes from a full rank matrix $B\in\mathbb{Z}^{m\times m}_q$. In other words, is the matrix $A$ a submatrix of $B$? $\endgroup$
    – X.H. Yue
    Commented Aug 13 at 6:33
  • $\begingroup$ Or is $A$ just a simple random matrix? $\endgroup$
    – X.H. Yue
    Commented Aug 13 at 6:44
  • $\begingroup$ @X.H.Yue $A$ is random. But given $A$, one can derive a basis $B$. $\endgroup$
    – Hilder Vitor Lima Pereira
    Commented Aug 13 at 14:10

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.