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
  • Definition
  • Bounds

Was this helpful?

Export as PDF
  1. Lattices
  2. Lattice reduction

LLL reduced

PreviousHKZ reducedNextApplications

Last updated 4 years ago

Was this helpful?

Definition

Let δ∈(14,1)\delta\in\left(\frac14,1\right)δ∈(41​,1). A basis{bi}i=1d\left\{b_i\right\}_{i=1}^d{bi​}i=1d​is δ\deltaδ- LLL-reduced if it is size reduced and satisfy the Lovász condition, i.e.

δ∥bi∗∥2≤∥bi+1∗+μi+1,ibi∗∥2\delta\left\lVert b_i^*\right\rVert^2\leq\left\lVert b_{i+1}^*+\mu_{i+1,i}b_i^*\right\rVert^2δ∥bi∗​∥2≤​bi+1∗​+μi+1,i​bi∗​​2

This notion of reduction is most useful to use for fast algorithms as such a basis can be found in polynomial time (see ).

Bounds

∥b1∥≤(44δ−1)d−14vol(L)1d∥bi∥≤(44δ−1)d−12λi(L)∏i=1d∥bi∥≤(44δ−1)d(d−1)4vol(L)\begin{align*} \left\lVert b_1\right\rVert&\leq\left(\frac4{4\delta-1}\right)^{\frac{d-1}4}\text{vol}(L)^\frac1d\\ \left\lVert b_i\right\rVert&\leq\left(\frac4{4\delta-1}\right)^{\frac{d-1}2}\lambda_i(L)\\ \prod_{i=1}^d\left\lVert b_i\right\rVert&\leq\left(\frac4{4\delta-1}\right)^{\frac{d(d-1)}4}\text{vol}(L) \end{align*}∥b1​∥∥bi​∥i=1∏d​∥bi​∥​≤(4δ−14​)4d−1​vol(L)d1​≤(4δ−14​)2d−1​λi​(L)≤(4δ−14​)4d(d−1)​vol(L)​
LLL reduction