CryptoBook
  • CryptoBook
  • Book Plan
  • Style Guide
    • Sample Page
  • Contributors
  • Fundamentals
    • Mathematical Notation
    • Division and Greatest common divisor
      • Euclidean Algorithm
    • Modular Arithmetic
      • Theorems of Wilson, Euler, and Fermat
        • Fermat's Little Theorem in Detail
        • Euler's Theorem in Detail
      • Quadratic Residues
    • Continued Fractions
  • Number Theory
  • Ideals
  • Polynomials With Shared Roots
  • Integer Factorization
    • Pollard rho
    • Sieves
  • Abstract algebra
    • Groups
      • Another take on groups
      • Discrete Log Problem
    • Rings
    • Fields
    • Polynomials
  • Elliptic Curves
    • Untitled
  • Lattices
    • Introduction
    • LLL reduction
      • Gram-Schmidt Orthogonalization
      • Lagrange's algorithm
      • LLL reduction
    • Lattice reduction
      • Minkowski reduced
      • HKZ reduced
      • LLL reduced
    • Applications
      • Coppersmith algorithm
      • Extensions of Coppersmith algorithm
    • Hard lattice problems
    • Lattices of interest
    • Cryptographic lattice problems
      • Short integer solutions (SIS)
      • Learning with errors (LWE)
      • Ring-LWE
      • NTRU
    • Interactive fun
    • Resources and notations
  • Asymmetric Cryptography
  • RSA
    • Proof of correctness
    • RSA application
    • Low Private Component Attacks
      • Wiener's Attack
      • Boneh-Durfee Attack
    • Common Modulus Attack
    • Recovering the Modulus
  • Diffie-Hellman
    • MITM
  • Elliptic Curve Cryptography
  • Symmetric Cryptography
    • Encryption
    • The One Time Pad
    • AES
      • Rijndael Finite Field
      • Round Transformations
  • Hashes
    • Introduction / overview
    • The Birthday paradox / attack
  • Isogeny Based Cryptography
    • Introduction to Isogeny Cryptography
    • Isogenies
    • Isogeny and Ramanujan Graphs
  • Appendices
    • Sets and Functions
    • Probability Theory
Powered by GitBook
On this page
  • Introduction
  • Dual lattice
  • Basis of the dual lattice
  • Properties
  • Successive minima
  • Geometry + Partitioning
  • Q-ary lattices
  • Resources

Was this helpful?

Export as PDF
  1. Lattices

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 L⊂RnL \subset \mathbb R^nL⊂Rnbe a lattice. We define the dual of a lattice as the set of all vectors y∈span(L)y \in span(L)y∈span(L) such that y⋅x∈Z y \cdot x \in \mathbb Z \ y⋅x∈Z for all vectors x∈Lx \in Lx∈L:

L∨={y∈span(L):y⋅x∈Z ∀ x∈L}L^\vee = \{y \in span(L) : y \cdot x \in \mathbb{Z} \ \forall \ x \in L\}L∨={y∈span(L):y⋅x∈Z ∀ x∈L}

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

Examples:

  1. (Zn)∨=Zn(\mathbb Z^n) ^ \vee = \mathbb Z^n(Zn)∨=Zn because the dot product of all vectors in Zn\mathbb Z^nZnstays in Zn\mathbb Z^nZn

  2. Scaling: (k⋅L)∨=1k⋅L(k \cdot L)^\vee = \dfrac 1 k \cdot L(k⋅L)∨=k1​⋅L Proof: If y∈(kL)∨⇒y⋅kx=k(x⋅y)∈Z ∀ x∈L⇒y∈1kL∨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^\veey∈(kL)∨⇒y⋅kx=k(x⋅y)∈Z ∀ x∈L⇒y∈k1​L∨ If y∈(1kL)∨⇒yv∈L∨⇒ky⋅x=k(x⋅y)=y⋅kx∈Z ∀ x ∈L⇒y∈(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)^\veey∈(k1​L)∨⇒yv∈L∨⇒ky⋅x=k(x⋅y)=y⋅kx∈Z ∀ x ∈L⇒y∈(kL)∨

Plot: 2Z22\mathbb Z ^22Z2 - green, 12Z2\dfrac 1 2 \mathbb Z ^ 221​Z2 - red

Intuition: We can think of the dual lattice L∨L^\veeL∨ as some kind of inverse of the initial lattice LLL

Basis of the dual lattice

We will now focus on the problem of finding the basis B∨B^\veeB∨ of the dual lattice L∨L^\veeL∨given the lattice LLL and its basis BBB.

Reminder: We can think of the lattice LLL as a transformation given by its basis B∈GLn(R)B \in GL_n(\mathbb R)B∈GLn​(R)on Zn\mathbb Z^nZn.

We have the following equivalences:

y∈L∨  ⟺  y⋅x∈Z ∀ x∈L  ⟺  BTy∈Zn  ⟺  y∈(B−1)T⋅Zn\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*}y∈L∨​⟺y⋅x∈Z ∀ x∈L⟺BTy∈Zn⟺y∈(B−1)T⋅Zn​

Therefore L∨=(B−1)T⋅ZnL^\vee = (B^{-1})^T \cdot \mathbb Z^nL∨=(B−1)T⋅Znso we have found a base for our dual lattice:

B∨=(B−1)T∈GLn(R)B^\vee = (B^{-1})^T \in GL_n(\mathbb{R})B∨=(B−1)T∈GLn​(R)
n = 5 # lattice dimension

B = 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 integers
B_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

Properties

  1. L1⊆L2  ⟺  L2∨⊆L1∨{L}_1 \subseteq {L}_2 \iff {L}^\vee_2 \subseteq {L}^\vee_1L1​⊆L2​⟺L2∨​⊆L1∨​

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

  3. det⁡(L∨)=det⁡(L)−1\det(L^\vee) = \det(L) ^{-1}det(L∨)=det(L)−1 (to prove think of the basis of L∨L^\veeL∨)

  4. For x∈L,y∈L∨x \in {L}, y \in {L}^\veex∈L,y∈L∨consider the vector dot product and addition - x⋅y∈Zx \cdot y \in \mathbb{Z}x⋅y∈Z - x+yx + 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 LLL and its dual L∨L^\veeL∨. 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)λ1​(2Z2)? What about λ1((2Z2)∨)\lambda_1((2\mathbb Z^2)^\vee)λ1​((2Z2)∨)? Can you see some patterns?

Reminder: We defined the successive minima of a lattice LLLas such:

λi(L)=min⁡(max⁡1≤j≤i(∥vj∥):vj∈L 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)λi​(L)=min(1≤j≤imax​(∥vj​∥):vj​∈L are linearly independent)

Claim 1:

λ1(L)⋅λ1(L∨)≤n\lambda_1(L) \cdot \lambda_1(L^\vee) \leq nλ1​(L)⋅λ1​(L∨)≤n

Proof: By Minkowski's bound we know:

λ1(L)≤n⋅det⁡(L)1/n\lambda_1(L) \leq \sqrt{n} \cdot \det(L)^{1 / n}λ1​(L)≤n​⋅det(L)1/n and λ1(L∨)≤n⋅det(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}}λ1​(L∨)≤n​⋅det(L∨)1/n=det(L)1/nn​​. By multiplying them we get the desired result.

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

n = 5 # lattice dimension

B = 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() / 11

print(l1 * l2 < n)
# True

Claim 2:

λ1(L)⋅λn(L∨)≥1\lambda_1(L) \cdot \lambda_n(L^\vee) \geq 1λ1​(L)⋅λn​(L∨)≥1

Proof:

Let x∈Lx∈Lx∈L be such that ∥x∥=λ1(L)\|x\|=λ_1(L)∥x∥=λ1​(L). Then take any set (y1,...,yn)(y_1, . . . , y_n)(y1​,...,yn​) of nnn linearly independent vectors in L∨L^\veeL∨. Not all of them are orthogonal to xxx. Hence, there exists an iii such that yi⋅x≠0y_i \cdot x \neq 0yi​⋅x=0 . By the definition of the dual lattice, we have yi⋅x∈Zy_i \cdot x \in \mathbb Zyi​⋅x∈Z and hence 1≤yi⋅x≤∥yi∥⋅∥x∥≤λ1⋅λn∨1 \leq y_i \cdot x \leq \|y_i\| \cdot \|x\| \leq \lambda_1 \cdot \lambda_n^\vee1≤yi​⋅x≤∥yi​∥⋅∥x∥≤λ1​⋅λn∨​

n = 5 # lattice dimension

B = 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 = 0
for v in B_dual_lll:
    lv = v.norm()
    if lv > lnd:
        lnd = lv
lnd = lnd.n() / 11

print(lnd * l1 > 1) 
# True

Geometry + Partitioning

// TODO

Q-ary lattices

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

Definition:

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

qZn⊆L⊆Znq\mathbb{Z}^n \subseteq {L} \subseteq \mathbb{Z}^nqZn⊆L⊆Zn

Intuition:

  • qZn⊆Lq\mathbb{Z^n} \subseteq \mathcal{L}qZn⊆L is periodic  mod  q\bmod \ qmod q

  • We use arithmetic  mod  q\bmod \ qmod 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}A∈(Z/qZ)n×m be a matrix with m>nm > nm>n. Consider the following lattices: Lq(A)={y∈Zm:y=ATx mod q∈ for some x∈Zn}⊂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)={y∈Zm:y=ATxmodq∈ for some x∈Zn}⊂Zm Lq⊥(A)={y∈Zm:Ay=0 mod q}⊂ZmL^\perp_q(A) = \{y \in \mathbb Z^m : Ay = 0 \bmod q \} \subset \mathbb{Z^m}Lq⊥​(A)={y∈Zm:Ay=0modq}⊂Zm

Intuition:

  • Think of Lq(A)L_q(A)Lq​(A) as the image of the matrix AAA, the matrix spanned by the rows of AAA

  • Think of Lq⊥(A)L_q^\perp(A)Lq⊥​(A) as the kernel of AAA modulo qqq. The set of solutions Ax=0Ax = 0Ax=0

Remark: If the same matrix AAA is used (AAA is fixed ) then Lq(A)≠Lq⊥(A)L_q(A) \neq L_q^\perp(A)Lq​(A)=Lq⊥​(A)

Claim:

Lq(A)L_q(A)Lq​(A) and Lq⊥(A)L_q^\perp(A)Lq⊥​(A) are the dual of each other (up to scaling): Lq(A)=1qLq⊥(A)L_q(A) = \dfrac 1 q L_q^\perp(A)Lq​(A)=q1​Lq⊥​(A)

Proof:

Firstly we will show Lq⊥(A)⊆q(Lq(A))∨L_q^\perp(A) \subseteq q(L_q(A))^\veeLq⊥​(A)⊆q(Lq​(A))∨

  • Let y∈Lq⊥(A)⇒Ay≡0 mod q  ⟺  Ay=qzy \in L_q^\perp(A) \Rightarrow Ay \equiv 0 \bmod q \iff Ay = qzy∈Lq⊥​(A)⇒Ay≡0modq⟺Ay=qzfor some z∈Zmz \in \mathbb{Z}^mz∈Zm

  • Let y′∈Lq(A)⇒y′≡ATx mod q  ⟺  y′=ATx+qz′y' \in L_q(A)\Rightarrow y' \equiv A^Tx \bmod q \iff y' = A^Tx + qz'y′∈Lq​(A)⇒y′≡ATxmodq⟺y′=ATx+qz′ for some x∈Zn, z′∈Zmx \in \mathbb Z^n, \ z' \in \mathbb Z^mx∈Zn, z′∈Zm

Then we have:y⋅y′=y⋅(ATx+qz′)=y⋅ATx+q(y⋅z′)=Ay⏟qz⋅x+q(y⋅z′)=qz⋅x+q(y⋅z′)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')y⋅y′=y⋅(ATx+qz′)=y⋅ATx+q(y⋅z′)=qzAy​​⋅x+q(y⋅z′)=qz⋅x+q(y⋅z′)

⇒1qy⋅y′∈Z⇒1qy∈Lq(A)∨\Rightarrow \dfrac 1 q y \cdot y' \in \mathbb{Z} \Rightarrow \dfrac 1 q y\in L_q(A)^\vee⇒q1​y⋅y′∈Z⇒q1​y∈Lq​(A)∨

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))^\veeLq⊥​(A)⊇q(Lq​(A))∨

Resources

PreviousHard lattice problemsNextCryptographic lattice problems

Last updated 3 years ago

Was this helpful?

https://en.wikipedia.org/wiki/Hermite_normal_form
https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/DualLattice.pdf
https://sp2.uni.lu/wp-content/uploads/sites/66/2019/06/DualLattice-Luca-Notarnicola.pdf
https://simons.berkeley.edu/sites/default/files/docs/14953/intro.pdf
https://cseweb.ucsd.edu/~daniele/papers/FOSAD11.pdf