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
  • Overview
  • Definitions
  • Exercises

Was this helpful?

Export as PDF
  1. Lattices

Lattice reduction

PreviousLLL reductionNextMinkowski reduced

Last updated 4 years ago

Was this helpful?

Overview

Having introduced the LLL reduction, we now provide a more general notions of a reduced basis for a lattice as well as provide bounds for the basis vectors. The key idea behind introducing these definitions is that once we know some basis vector is []-reduced, we can bound the sizes of the basis, which is important when algorithms require short vectors in a lattice. For fast algorithms, LLL-reduction is typically the most important notion as it can be computed quickly. Two main definitions appear often when discussing lattice reductions, which we will provide here.

Definitions

A basis{bi}i=1d\left\{b_i\right\}_{i=1}^d{bi​}i=1d​is size-reduced if ∣μi,j∣≤12\left|\mu_{i,j}\right|\leq\frac12∣μi,j​∣≤21​. Intuitively this captures the idea that a reduced basis being "almost orthogonal".

Let LLLbe a lattice, 1≤i≤dim⁡L=d1\leq i\leq\dim L=d1≤i≤dimL=d, we define the ithi^\text{th}ithsuccessive minimaλi(L)\lambda_i(L)λi​(L) as

λ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)

Intuitively, λi(L)\lambda_i(L)λi​(L)is the length of the "ithi^\text{th}ith shortest lattice vector". This intuition is illustrated by the definition of λ1\lambda_1λ1​:

λ1(L)=min⁡(∥v∥:v∈L)\lambda_1(L)=\min\left(\left\lVert v\right\rVert:v\in L\right)λ1​(L)=min(∥v∥:v∈L)

However this is not precise as if vvvis the shortest lattice vector, then −v-v−vis also the shortest lattice vector.

Unfortunately, a basisbib_ibi​for LLLwhere λi(L)=∥bi∥\lambda_i(L)=\left\lVert b_i\right\rVertλi​(L)=∥bi​∥for dimensions 555 and above. This tells us that we can't actually define "the most reduced basis" in contrast to the 2D case (see ) and we would need some other definition to convey this intuition.

An alternate definition ofλi(L)\lambda_i(L)λi​(L)that will be helpful is the radius of the smallest ball centered at the origin such that the ball contains at leastiiilinearly independent vectors inLLL.

Exercises

1) Show that both definitions of λi\lambda_iλi​ are equivalent

2) Consider the lattice L=(2000002000002000002011111)L=\begin{pmatrix}2&0&0&0&0\\0&2&0&0&0\\0&0&2&0&0\\0&0&0&2&0\\1&1&1&1&1\end{pmatrix}L=​20001​02001​00201​00021​00001​​. Show that the successive minima are all222but no basisbib_ibi​can satisfy ∥bi∥=λi\left\lVert b_i\right\rVert=\lambda_i∥bi​∥=λi​.

Lagrange's algorithm