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.
Let be a lattice. We define the dual of a lattice as the set of all vectors such that for all vectors :
because the dot product of all vectors in stays in
Scaling: Proof: If If
Plot: - green, - red
Intuition: We can think of the dual lattice as some kind of inverse of the initial lattice
We will now focus on the problem of finding the basis of the dual lattice given the lattice and its basis .
We have the following equivalences:
Therefore so we have found a base for our dual lattice:
n = 5 # lattice dimensionB = sage.crypto.gen_lattice(m=n, q=11, seed=42)B_dual = sage.crypto.gen_lattice(m=n, q=11, seed=42, dual=True)B_dual_ = (B.inverse().T * 11).change_ring(ZZ) # Scale up to integersB_dual_.hermite_form() == B_dual.hermite_form() # Reduce form to compare# True
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
The dual of the dual is the initial lattice (to prove think of the basis of )
(to prove think of the basis of )
For consider the vector dot product and addition - - 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 and its dual . Let's see what can we uncover about them.
Proof: By Minkowski's bound we know:
and . By multiplying them we get the desired result.
From this result we can deduce that the minima of the and have an inverse proportional relationship (If one is big, the other is small).
n = 5 # lattice dimensionB = sage.crypto.gen_lattice(m=n, q=11, seed=42)B_dual = sage.crypto.gen_lattice(m = n, q=11, seed=42, dual=True)l1 = IntegerLattice(B).shortest_vector().norm().n()l2 = IntegerLattice(B_dual).shortest_vector().norm().n() / 11print(l1 * l2 < n)# True
Let be such that . Then take any set of linearly independent vectors in . Not all of them are orthogonal to . Hence, there exists an such that . By the definition of the dual lattice, we have and hence
n = 5 # lattice dimensionB = sage.crypto.gen_lattice(m=n, q=11, seed=42)B_dual = sage.crypto.gen_lattice(m = n, q=11, seed=42, dual=True)l1 = IntegerLattice(B).shortest_vector().norm().n()B_dual_lll = B_dual.LLL()lnd = 0for v in B_dual_lll:lv = v.norm()if lv > lnd:lnd = lvlnd = lnd.n() / 11print(lnd * l1 > 1)# True
We've seen that in cryptography we don't like to work with infinite sets (like ) and we limit them to some finite set using the operation (). We will apply the same principle to the lattices so let us define the concept of a q-ary lattice.
For a number we call a lattice q-ary if
We use arithmetic
We will now look at 2 more types of lattices that are q-ary. Let be a matrix with . Consider the following lattices:
Think of as the image of the matrix , the matrix spanned by the rows of
Think of as the kernel of modulo . The set of solutions
and are the dual of each other (up to scaling):
Firstly we will show
Let for some
Let for some
Then we have:
The second part is left as an exercise to the reader :D. Show