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?

$\endgroup$
1
$\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$
  • $\begingroup$ Thank you very much for that tutorial link $\endgroup$ – satya Jul 20 '19 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 '19 at 16:15
  • $\begingroup$ So, q-ary lattices are a small subset of integer lattices. $\endgroup$ – satya Jul 20 '19 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 '19 at 16:27
  • $\begingroup$ I think you are misinterpreting something... A $q$-ary lattice does not correspond to an integer lattice, it is an integer lattice. Try to draw an example with $m = 2$ and maybe you will see things clearer (: $\endgroup$ – Hilder Vitor Lima Pereira Jul 20 '19 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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