Lattices of interest

Let $L \subset \mathbb R^n$be a lattice. We define the dual of a lattice as the set of all vectors $y \in span(L)$ such that $y \cdot x \in \mathbb Z \$for all vectors $x \in L$:

Note that the vectors in the dual lattice $L^\vee$ are not necessarily in the initial lattice $L$. They are spanned by the basis vectors of the lattice $L$.

$(\mathbb Z^n) ^ \vee = \mathbb Z^n$ because the dot product of all vectors in $\mathbb Z^n$stays in $\mathbb Z^n$

Scaling: $(k \cdot L)^\vee = \dfrac 1 k \cdot L$ Proof: If $y \in (kL)^\vee \Rightarrow y \cdot kx = k(x \cdot y) \in \mathbb{Z} \ \forall \ x \in L \Rightarrow y \in \dfrac 1 k L^\vee$ If $y \in \left (\dfrac 1 kL\right )^\vee \Rightarrow yv \in L^\vee \Rightarrow ky\cdot x = k(x \cdot y) = y \cdot kx \in \mathbb{Z} \ \forall \ x \ \in L \Rightarrow y \in (kL)^\vee$

Plot: $2\mathbb Z ^2$ - green, $\dfrac 1 2 \mathbb Z ^ 2$ - red

Intuition: We can think of the dual lattice $L^\vee$ as some kind of inverse of the initial lattice $L$

We will now focus on the problem of finding the basis $B^\vee$ of the dual lattice $L^\vee$given the lattice $L$ and its basis $B$.

Reminder: We can think of the lattice $L$ as a transformation given by its basis $B \in GL_n(\mathbb R)$on $\mathbb Z^n$.

Therefore $L^\vee = (B^{-1})^T \cdot \mathbb Z^n$so we have found a base for our dual lattice:

${L}_1 \subseteq {L}_2 \iff {L}^\vee_2 \subseteq {L}^\vee_1$

$({L}^\vee)^\vee ={L} =$The dual of the dual is the initial lattice (to prove think of the basis of $L^\vee$)

$\det(L^\vee) = \det(L) ^{-1}$ (to prove think of the basis of $L^\vee$)

For $x \in {L}, y \in {L}^\vee$consider the vector dot product and addition - $x \cdot y \in \mathbb{Z}$ - $x + y$ has no geometric meaning, they are in different spaces

We've seen that we can find the basis of the dual lattice given the basis of the original lattice. Let's look at another interesting quantity: the successive minima of a lattice $L$ and its dual $L^\vee$. Let's see what can we uncover about them.

What is $\lambda_1(2\mathbb Z^2)$? What about $\lambda_1((2\mathbb Z^2)^\vee)$? Can you see some patterns?

Reminder: We defined the successive minima of a lattice $L$as such:

$\lambda_1(L) \leq \sqrt{n} \cdot \det(L)^{1 / n}$ and $\lambda_1(L^\vee) \leq \sqrt{n} \cdot det(L^\vee)^{1 / n} = \dfrac {\sqrt{n}} {\det(L)^{1/n}}$. By multiplying them we get the desired result.

From this result we can deduce that the minima of the $L$ and $L^\vee$have an inverse proportional relationship (If one is big, the other is small).

Let $x∈L$ be such that $\|x\|=λ_1(L)$. Then take any set $(y_1, . . . , y_n)$ of $n$ linearly independent vectors in $L^\vee$. Not all of them are orthogonal to $x$. Hence, there exists an $i$ such that $y_i \cdot x \neq 0$ . By the definition of the dual lattice, we have $y_i \cdot x \in \mathbb Z$ and hence $1 \leq y_i \cdot x \leq \|y_i\| \cdot \|x\| \leq \lambda_1 \cdot \lambda_n^\vee$

We've seen that in cryptography we don't like to work with infinite sets (like $\mathbb Z$) and we limit them to some finite set using the $\bmod$ operation ($\mathbb Z \to \mathbb Z/ q\mathbb{Z}$). We will apply the same principle to the lattices so let us define the concept of a q-ary lattice.

For a number $q \in \mathbb{Z},\ q \geq 3$we call a lattice q-ary if

$q\mathbb{Z^n} \subseteq \mathcal{L}$ is periodic $\bmod \ q$

We use arithmetic $\bmod \ q$

We will now look at 2 more types of lattices that are q-ary. Let $A \in (\mathbb{Z}/q\mathbb Z)^{n \times m}$ be a matrix with $m > n$. Consider the following lattices: $L_q(A) = \{y \in \mathbb Z^m : y = A^Tx \bmod q \in \text{ for some } x \in \mathbb{Z}^n \} \subset \mathbb{Z^m}$ $L^\perp_q(A) = \{y \in \mathbb Z^m : Ay = 0 \bmod q \} \subset \mathbb{Z^m}$

Think of $L_q(A)$ as the image of the matrix $A$, the matrix spanned by the rows of $A$

Think of $L_q^\perp(A)$ as the kernel of $A$ modulo $q$. The set of solutions $Ax = 0$

Remark: If the same matrix $A$ is used ($A$ is fixed ) then $L_q(A) \neq L_q^\perp(A)$

$L_q(A)$ and $L_q^\perp(A)$ are the dual of each other (up to scaling): $L_q(A) = \dfrac 1 q L_q^\perp(A)$

Firstly we will show $L_q^\perp(A) \subseteq q(L_q(A))^\vee$

Let $y \in L_q^\perp(A) \Rightarrow Ay \equiv 0 \bmod q \iff Ay = qz$for some $z \in \mathbb{Z}^m$

Let $y' \in L_q(A)\Rightarrow y' \equiv A^Tx \bmod q \iff y' = A^Tx + qz'$ for some $x \in \mathbb Z^n, \ z' \in \mathbb Z^m$

Then we have:$y \cdot y' = y \cdot (A^Tx + qz') = y\cdot A^Tx + q (y \cdot z') = \underbrace{Ay}_{qz} \cdot x + q(y \cdot z') = qz \cdot x + q(y \cdot z')$

$\Rightarrow \dfrac 1 q y \cdot y' \in \mathbb{Z} \Rightarrow \dfrac 1 q y\in L_q(A)^\vee$

The second part is left as an exercise to the reader :D. Show $L_q^\perp(A) \supseteq q(L_q(A))^\vee$