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
  • Definitions
  • Proof sketch of Minkowski's theorem
  • Exercises

Was this helpful?

Export as PDF
  1. Lattices

Introduction

Lattices, also known as Minkowski's theory after Hermann Minkowski, or the geometry of numbers (deprecated!) allows the usage of geometrical tools (i.e. volumes) in number theory.

The intuitive notion of a lattice (perhaps surprisingly) matches its mathematical definition. For example, lattices are formed by

  • points on an infinite checkerboard;

  • centers of a hexagonal tessellation;

  • integers on the real number line.

The last example should hint at how we generalize this concept to arbitrary dimensions. In general, lattices consist of discrete points which appear at "regular intervals."

Definitions

A lattice LLL is a subgroup of Rn\mathbb{R}^nRngenerated by bib_ibi​, i.e.

L=∑i=1dZbi={∑i=1daibi∣ai∈Z}L=\sum_{i=1}^d\mathbb{Z} b_i = \left\{\left. \sum_{i=1}^d a_i b_i \right | a_i \in \mathbb{Z} \right\}L=i=1∑d​Zbi​={i=1∑d​ai​bi​​ai​∈Z}

where bib_ibi​ are linearly independent vectors. Collectively, {bi}i=1d\left\{b_i\right\}_{i=1}^d{bi​}i=1d​ form a basis ofLLL.

We say a set of vectors viv_ivi​are linearly independent if the only solution to the equation ∑iaibi=0\sum_{i} a_i b_i = 0∑i​ai​bi​=0 is when all aia_iai​are zero.

Taking a step back, this definition should resemble that of a vector space, with one exception: scalars are integers! The discrete nature of lattices comes from this restriction.

Some more terminology from linear algebra will be useful. The dimension of a lattice, denoteddim⁡L\dim LdimL, is ddd. A lattice is complete if d=nd=nd=n. Note that we can always choose a subspace of Rn\mathbb R^nRnsuch that the lattice is complete, namely the subspace generated by bib_ibi​.

The region

Φ={∑i=1dxibi∣0≤xi<1}\Phi=\left\{\left.\sum_{i=1}^dx_ib_i\right|0\leq x_i<1\right\}Φ={i=1∑d​xi​bi​​0≤xi​<1}

is known as the fundamental mesh.

In the image above, we see the points of a lattice in R2\mathbb R^2R2. The red vectors are one set of basis vectors and the shaded region is the corresponding fundamental mesh. The green vectors also form another set of basis vectors with its corresponding fundamental mesh. We see here that the basis vectors and fundamental mesh is not unique to a lattice.

Although the fundamental mesh is not unique, it turns out that the (mmmdimensional) volume of the fundamental mesh is constant for any given lattice. Hence we can define the volume of a lattice as the volume of a fundamental mesh. However this definition can be hard to handle hence we provide an equivalent definition via determinants:

LetB\mathcal BBbe ad×nd\times nd×nmatrix whose rows are given by the basis vectors. Then the volume of a fundamental mesh is given by

vol(L)=∣det⁡(BBT)∣\text{vol}(L)=\sqrt{\left|\det\left(\mathcal B\mathcal B^T\right)\right|}vol(L)=∣det(BBT)∣​

A subset XXXof Rn\mathbb R^nRnis known as centrally symmetric if x∈Xx\in Xx∈Ximplies −x∈X-x\in X−x∈X. It is convex if for any x,y∈Xx,y\in Xx,y∈X, the line joining x,yx,yx,y is contained in XXX, i.e. {tx+(1−t)y∣0≤t≤1}⊂X\left\{tx+(1-t)y|0\leq t\leq1\right\}\subset X{tx+(1−t)y∣0≤t≤1}⊂X. Finally we can introduce the most important theorem about lattices, the Minkowski's Lattice Point Theorem:

Let LLLbe a complete lattice of dimensionnnn and XXXbe a centrally symmetric convex set. Suppose

vol(X)>2nvol(L)\text{vol}(X)>2^n\text{vol}(L)vol(X)>2nvol(L)

Then XXXcontains at least one nonzero point of LL L. This result is primarily used to prove the existence of lattice vectors.

Throughout this section, ∥v∥=∑ivi2\left\lVert v\right\rVert=\sqrt{\sum_iv_i^2}∥v∥=∑i​vi2​​ denotes the ℓ2\ell_2ℓ2​norm and ⟨a,b⟩=∑iaibi\langle a,b\rangle=\sum_ia_ib_i⟨a,b⟩=∑i​ai​bi​ denotes the inner product.

Proof sketch of Minkowski's theorem

This proof is by some sort of a pigeonhole argument on volumes. Consider the set

12X={12x∣x∈X}\frac12X=\left\{\frac12x|x\in X\right\}21​X={21​x∣x∈X}

We have vol(12X)>vol(L)\text{vol}\left(\frac12 X\right)>\text{vol}(L)vol(21​X)>vol(L), hence the inclusion 12X→Rn/L\frac12X\to\mathbb R^n/L21​X→Rn/Lcannot be injective, thus we can find some x1=x2+ℓx_1=x_2+\ellx1​=x2​+ℓ, x1,x2∈12X,ℓ∈L,x1≠x2x_1,x_2\in\frac12 X,\ell\in L,x_1\neq x_2x1​,x2​∈21​X,ℓ∈L,x1​=x2​. Hence x1−x2∈Lx_1-x_2\in Lx1​−x2​∈Lis a nontrivial lattice point.

Exercises

1) Let LLLbe the lattice generated by B=(−1981−8−7)\mathcal B=\begin{pmatrix}-1&9&8\\1&-8&-7\end{pmatrix}B=(−11​9−8​8−7​)(take the rows as basis vectors).

  • Compute the volume of this lattice

  • Show that B′=(101011)\mathcal B'=\begin{pmatrix}1&0&1\\0&1&1\end{pmatrix}B′=(10​01​11​)generates the same lattice

  • Show that each row in C=(101022)\mathcal C=\begin{pmatrix}1&0&1\\0&2&2\end{pmatrix}C=(10​02​12​)is in the lattice butC\mathcal CCdoes not generate the lattice. This is one key difference from the case of linear algebra (over fields).

2) LetB,B′\mathcal B,\mathcal B'B,B′be d×nd\times nd×nmatrices whose row vectors are basis for lattices L,L′L,L'L,L′. Both lattices are the same iff there exists some U∈GLd(Z)U\in\text{GL}_d(\mathbb Z)U∈GLd​(Z) such that B′=UB\mathcal B'=U\mathcal BB′=UB. Find UUUfor problem 1. Note that GLd(Z)\text{GL}_d(\mathbb Z)GLd​(Z)is the group of invertible matrices with integer coefficients, meaning UUUand U−1U^{-1}U−1have integer coefficients.

3) Show that the condition in Minkowski's lattice point theorem is strict, i.e. for any complete latticeLLLof dimension nnn, we can find some centrally symmetric convex setXXXwithvol(X)=2nvol(L)\text{vol}(X)=2^n\text{vol}(L)vol(X)=2nvol(L)but the only lattice point inXXXis the origin.

4*) Letvvvbe the shortest nonzero vector for some lattice LLLwith dimensionnnn. Show that

∥v∥≤2πΓ(n2+1)1nvol(L)1n\left\lVert v\right\rVert\leq\frac2{\sqrt\pi}\Gamma\left(\frac n2+1\right)^{\frac1n}\text{vol}(L)^\frac1n∥v∥≤π​2​Γ(2n​+1)n1​vol(L)n1​
PreviousUntitledNextLLL reduction

Last updated 3 years ago

Was this helpful?