1
$\begingroup$

An $m$-dimensional lattice is defined by a basis $A \in \mathbb{R}^{m \times n}$ is the set of points $\{Az : z \in \mathbb{Z}^n\}$. A picture of these points would be like a nice parallelogram kind of structure.

In crypto, we use $q$-ary integer lattices defined by basis $A \in \mathbb{Z}_q^{m \times n}$ and is defined as $\{x \in \mathbb{Z}^m : \exists z \in \mathbb{Z}_q^n, x = Az \mod q\}$. I couldn't imagine how these lattices look like. Do these also have the same kind of parallelogram structure? Why do cryptographers use these lattices?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Actually, the matrix $A$ defines a $q$-ary lattice $L$, but it is not a basis of $L$.

Let $m \ge n$, write $A$ in blocks, as follows: $A = \begin{pmatrix} A_1 \\ A_2 \end{pmatrix}$, where $A_1 \in \mathbb{Z}_q^{n\times n}$ and $A_2 \in \mathbb{Z}_q^{m-n\times n}$. Additionally, let's also write the vectors $x \in L$ as "block" vectors $(x_1 \quad x_2)$.

Now, suppose that $A_1$ is invertible over $\mathbb{Z}_q$.

Then we see that $x \in L \Leftrightarrow x = Az \mod q \Leftrightarrow x_1 = A_1z \mod q \text{ and } x_2 = A_2z \mod q $.

But that means that $A_1^{-1}x_1 = z \mod q$ and $x_2 = A_2(A_1^{-1}x_1) \mod q$.

Therefore, over the integers, there is an $(m-n)$-dimensional vector $u$ such that $x_2 = A_2A_1^{-1}x_1 + qu$.

Thus, it is easy to see that the columns of the following matrix form a basis of $L$:

$$B = \begin{pmatrix} I_n & O \\ A_2A_1^{-1} & qI_{m-n} \end{pmatrix} \in \mathbb{Z}^{m\times m}.$$

If we do $B\begin{pmatrix} x_1 \\ u \end{pmatrix}$ we get exactly $\begin{pmatrix} x_1 \\ A_2A_1^{-1}x_1 + qu \end{pmatrix}$, as expected.

Now, answering your other questions:

Do these also have the same kind of parallelogram structure?

Yes, all lattices have such structure. The parallelogram in this case is defined by the columns of $B$.

Why do cryptographers use these lattices?

Those lattices appear naturally in cryptography because of problems like SIS and LWE.

There is plenty of material about that on the internet, for example, this tutorial on lattice-based crypto.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you very much for that tutorial link $\endgroup$
    – satya
    Jul 20, 2019 at 15:50
  • $\begingroup$ Here's what I understand. When we consider any q-ary lattice with basis $A \in \mathbb{Z}_q^{m \times n}$, it corresponds to an integer lattice with basis $B$ described above. $\endgroup$
    – satya
    Jul 20, 2019 at 16:15
  • $\begingroup$ So, q-ary lattices are a small subset of integer lattices. $\endgroup$
    – satya
    Jul 20, 2019 at 16:24
  • $\begingroup$ It is not correct to say that $A$ is the basis of the $q$-ary lattice. For each $A$, you have a $q$-ary lattice $\Lambda_q(A)$. So, $A$ is defining the lattice, but it is not a basis of it. This lattice is full-rank of dimension $m$, therefore, any basis must have $m$ vectors of dimension $m$. And yes, it is a sublattice of $\mathbb{Z}^m$. But you just need the definition to see that, since it states that the lattice is composed by $x \in \mathbb{Z}^m$ such that $x$ has some property... $\endgroup$
    – Hilder Vitor Lima Pereira
    Jul 20, 2019 at 16:27

Your Answer

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

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