CryptoBook
Search…
Lattices of interest
Needs review.

Introduction

In this chapter we will study some specific types of lattices that appear in cryptography. These will help us understand how certain problems we base our algorithms on reduce to other hard problems. They will also give insight about the geometry of lattices.
Intuitively, if we have a problem (1) in some lattice space we can reduce it to a hard problem (2) in another related lattice space. Then if we can prove that if solving problem (1) implies solving problem (2) then we can conclude that problem (1) is as hard as problem (2)
Understanding this chapter will strengthen the intuition for the fututre when we will study what breaking a lattice problem means and how to link it to another hard lattice problem.

Dual lattice

Let
LRnL \subset \mathbb R^n
be a lattice. We define the dual of a lattice as the set of all vectors
yspan(L)y \in span(L)
such that
yxZ y \cdot x \in \mathbb Z \
for all vectors
xLx \in L
:
L={yspan(L):yxZ  xL}L^\vee = \{y \in span(L) : y \cdot x \in \mathbb{Z} \ \forall \ x \in L\}
Note that the vectors in the dual lattice
LL^\vee
are not necessarily in the initial lattice
LL
. They are spanned by the basis vectors of the lattice
LL
.
Examples:
    1.
    (Zn)=Zn(\mathbb Z^n) ^ \vee = \mathbb Z^n
    because the dot product of all vectors in
    Zn\mathbb Z^n
    stays in
    Zn\mathbb Z^n
    2.
    Scaling:
    (kL)=1kL(k \cdot L)^\vee = \dfrac 1 k \cdot L
    Proof: If
    y(kL)ykx=k(xy)Z  xLy1kLy \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(1kL)yvLkyx=k(xy)=ykxZ  x Ly(kL)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:
2Z22\mathbb Z ^2
- green,
12Z2\dfrac 1 2 \mathbb Z ^ 2
- red
Intuition: We can think of the dual lattice
LL^\vee
as some kind of inverse of the initial lattice
LL

Basis of the dual lattice

We will now focus on the problem of finding the basis
BB^\vee
of the dual lattice
LL^\vee
given the lattice
LL
and its basis
BB
.
Reminder: We can think of the lattice
LL
as a transformation given by its basis
BGLn(R)B \in GL_n(\mathbb R)
on
Zn\mathbb Z^n
.
We have the following equivalences:
yL    yxZ  xL    BTyZn    y(B1)TZn\begin{align*} y \in L^\vee & \iff y \cdot x \in \mathbb Z \ \forall\ x \in L \\ & \iff B^Ty \in \mathbb{Z}^n \\ & \iff y \in (B^{-1})^T \cdot \mathbb Z^n \end{align*}
Therefore
L=(B1)TZnL^\vee = (B^{-1})^T \cdot \mathbb Z^n
so we have found a base for our dual lattice:
B=(B1)TGLn(R)B^\vee = (B^{-1})^T \in GL_n(\mathbb{R})
1
n = 5 # lattice dimension
2
3
B = sage.crypto.gen_lattice(m=n, q=11, seed=42)
4
B_dual = sage.crypto.gen_lattice(m=n, q=11, seed=42, dual=True)
5
6
B_dual_ = (B.inverse().T * 11).change_ring(ZZ) # Scale up to integers
7
B_dual_.hermite_form() == B_dual.hermite_form() # Reduce form to compare
8
# True
Copied!
Let's look at some plots. With green I will denote the original lattice and with red the dual. The scripts for the plots can be found in in the interactive fun section

Properties

    1.
    L1L2    L2L1{L}_1 \subseteq {L}_2 \iff {L}^\vee_2 \subseteq {L}^\vee_1
    2.
    (L)=L=({L}^\vee)^\vee ={L} =
    The dual of the dual is the initial lattice (to prove think of the basis of
    LL^\vee
    )
    3.
    det(L)=det(L)1\det(L^\vee) = \det(L) ^{-1}
    (to prove think of the basis of
    LL^\vee
    )
    4.
    For
    xL,yLx \in {L}, y \in {L}^\vee
    consider the vector dot product and addition -
    xyZx \cdot y \in \mathbb{Z}
    -
    x+yx + y
    has no geometric meaning, they are in different spaces

Successive minima

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
LL
and its dual
LL^\vee
. Let's see what can we uncover about them.
We recommend to try and think about the problem for a few minutes before reading the conclusions.
What is
λ1(2Z2)\lambda_1(2\mathbb Z^2)
? What about
λ1((2Z2))\lambda_1((2\mathbb Z^2)^\vee)
? Can you see some patterns?
Reminder: We defined the successive minima of a lattice
LL
as such:
λi(L)=min(max1ji(vj):vjL are linearly independent)\lambda_i(L)=\min\left(\max_{1\leq j\leq i}\left(\left\lVert v_j\right\rVert\right):v_j\in L\text{ are linearly independent}\right)
Claim 1:
λ1(L)λ1(L)n\lambda_1(L) \cdot \lambda_1(L^\vee) \leq n
Proof: By Minkowski's bound we know:
λ1(L)ndet(L)1/n\lambda_1(L) \leq \sqrt{n} \cdot \det(L)^{1 / n}
and
λ1(L)ndet(L)1/n=ndet(L)1/n\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
LL
and
LL^\vee
have an inverse proportional relationship (If one is big, the other is small).
1
n = 5 # lattice dimension
2
3
B = sage.crypto.gen_lattice(m=n, q=11, seed=42)
4
B_dual = sage.crypto.gen_lattice(m = n, q=11, seed=42, dual=True)
5
6
l1 = IntegerLattice(B).shortest_vector().norm().n()
7
l2 = IntegerLattice(B_dual).shortest_vector().norm().n() / 11
8
9
print(l1 * l2 < n)
10
# True
Copied!
Claim 2:
λ1(L)λn(L)1\lambda_1(L) \cdot \lambda_n(L^\vee) \geq 1
Proof:
Let
xLx∈L
be such that
x=λ1(L)\|x\|=λ_1(L)
. Then take any set
(y1,...,yn)(y_1, . . . , y_n)
of
nn
linearly independent vectors in
LL^\vee
. Not all of them are orthogonal to
xx
. Hence, there exists an
ii
such that
yix0y_i \cdot x \neq 0
. By the definition of the dual lattice, we have
yixZy_i \cdot x \in \mathbb Z
and hence
1yixyixλ1λn1 \leq y_i \cdot x \leq \|y_i\| \cdot \|x\| \leq \lambda_1 \cdot \lambda_n^\vee
1
n = 5 # lattice dimension
2
3
B = sage.crypto.gen_lattice(m=n, q=11, seed=42)
4
B_dual = sage.crypto.gen_lattice(m = n, q=11, seed=42, dual=True)
5
6
l1 = IntegerLattice(B).shortest_vector().norm().n()
7
8
B_dual_lll = B_dual.LLL()
9
lnd = 0
10
for v in B_dual_lll:
11
lv = v.norm()
12
if lv > lnd:
13
lnd = lv
14
lnd = lnd.n() / 11
15
16
print(lnd * l1 > 1)
17
# True
Copied!

Geometry + Partitioning

// TODO

Q-ary lattices

We've seen that in cryptography we don't like to work with infinite sets (like
Z\mathbb Z
) and we limit them to some finite set using the
mod\bmod
operation (
ZZ/qZ\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.
Definition:
For a number
qZ, q3q \in \mathbb{Z},\ q \geq 3
we call a lattice q-ary if
qZnLZnq\mathbb{Z}^n \subseteq {L} \subseteq \mathbb{Z}^n
Intuition:
    qZnLq\mathbb{Z^n} \subseteq \mathcal{L}
    is periodic
    mod q\bmod \ q
    We use arithmetic
    mod q\bmod \ q
We will now look at 2 more types of lattices that are q-ary. Let
A(Z/qZ)n×mA \in (\mathbb{Z}/q\mathbb Z)^{n \times m}
be a matrix with
m>nm > n
. Consider the following lattices:
Lq(A)={yZm:y=ATxmodq for some xZn}ZmL_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}
Lq(A)={yZm:Ay=0modq}ZmL^\perp_q(A) = \{y \in \mathbb Z^m : Ay = 0 \bmod q \} \subset \mathbb{Z^m}
Intuition:
    Think of
    Lq(A)L_q(A)
    as the image of the matrix
    AA
    , the matrix spanned by the rows of
    AA
    Think of
    Lq(A)L_q^\perp(A)
    as the kernel of
    AA
    modulo
    qq
    . The set of solutions
    Ax=0Ax = 0
Remark: If the same matrix
AA
is used (
AA
is fixed ) then
Lq(A)Lq(A)L_q(A) \neq L_q^\perp(A)
Claim:
Lq(A)L_q(A)
and
Lq(A)L_q^\perp(A)
are the dual of each other (up to scaling):
Lq(A)=1qLq(A)L_q(A) = \dfrac 1 q L_q^\perp(A)
Proof:
Firstly we will show
Lq(A)q(Lq(A))L_q^\perp(A) \subseteq q(L_q(A))^\vee
    Let
    yLq(A)Ay0modq    Ay=qzy \in L_q^\perp(A) \Rightarrow Ay \equiv 0 \bmod q \iff Ay = qz
    for some
    zZmz \in \mathbb{Z}^m
    Let
    yLq(A)yATxmodq    y=ATx+qzy' \in L_q(A)\Rightarrow y' \equiv A^Tx \bmod q \iff y' = A^Tx + qz'
    for some
    xZn, zZmx \in \mathbb Z^n, \ z' \in \mathbb Z^m
Then we have:
yy=y(ATx+qz)=yATx+q(yz)=Ayqzx+q(yz)=qzx+q(yz)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')
1qyyZ1qyLq(A)\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
Lq(A)q(Lq(A))L_q^\perp(A) \supseteq q(L_q(A))^\vee

Resources

Last modified 5mo ago