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
  • Shortest vector problem + GapSVP
  • Closest Vector problem + GapCVP
  • Bounded distance decoding
  • Shortest independent vectors (SIVP)
  • Hardness of lattice problems
  • Resources

Was this helpful?

Export as PDF
  1. Lattices

Hard lattice problems

This section is not complete. Help is needed with relevance + examples in cryptography, algorithms + hardness, relations between problems.

Also needs review from more experienced people.

Introduction

Now that we are comfortable with lattices we shall study why are they important to cryptography.

Like we said, when we construct cryptosystems we usually are looking for hard problems to base them on. The lattice world provides us with such problems such as the shortest vector problem or the closest vector problem.

What makes lattices even more special is that some cryptographic problems (which we will study in the next chapter) can be reduced to worst-case lattice problems which makes them crazy secure. Moreover, some problems are even secure against quantum computers.

But enough talk, let's get right into it!

Shortest vector problem + GapSVP

Before we go into any problems we must first define the concept of distance in a lattice.

Let:

  • L=L= L= Lattice

  • B=\mathcal B = B= the basis of the lattice

  • n=n = n=the dimension of the lattice

Distance function

Given some distance function (Example: Euclidean norm) the distance from a vector ttt to the lattice LLL is the distance from the vector to the closest point in the in lattice.

μ(t,L)=min⁡v∈L∥t−v∥\mu(t, L) = \underset{v \in \mathcal{L}}{\min}{\|t-v\|}μ(t,L)=v∈Lmin​∥t−v∥

We will denote the length of the shortest vector with ∥v∥=λ1(L)\|v\| = \lambda_1(L)∥v∥=λ1​(L)and the length of the next independent vectors in order with λi(L)⇒λ1(L)≤λ2(L)≤...≤λn(L)\lambda_i(L) \Rightarrow\lambda_1({L}) \leq \lambda_2({L}) \leq ... \leq \lambda_n({L})λi​(L)⇒λ1​(L)≤λ2​(L)≤...≤λn​(L)

Shortest vector problem

Given a lattice LLL and an arbitrary basis B\mathcal{B}B for it our task is to find the shortest vector v∈Lv \in Lv∈L.

Approximate SVP

We relax the SVP problem a bit. Given an arbitrary basis B\mathcal{B}Bfind a shortest nonzero lattice vector v∈Lv \in Lv∈Lsuch that v<γ(n)⋅λ1(L)v < \gamma(n)\cdot \lambda_1(L)v<γ(n)⋅λ1​(L). Here γ(n)>1\gamma(n) > 1γ(n)>1is some approximation factor.

Decision SVP (GapSVP)

Given a lattice LLLwith a basis B\mathcal BB we must distinguish if λ1(L)≤1\lambda_1(L) \leq 1λ1​(L)≤1 or λ>γ(n)\lambda > \gamma(n)λ>γ(n)

Sage example

# We can find the shortest vector using the LLL algorithm
M = matrix([[-1, 2], [-2, 3]])
B = M.LLL()
print(B[0])
# (0, -1)

# Or we can use the Integer Lattice class
L = IntegerLattice(M)
L.shortest_vector()
# (-1, 0)

Closest Vector problem + GapCVP

Closest vector problem

Given a lattice LLL with an arbitrary basis B\mathcal BB and a vector w∈Rnw \in \mathbb{R}^nw∈Rn find the closest lattice vector to www v∈L,∥v−w∥≤μv \in {L}, \|v-w\| \leq \muv∈L,∥v−w∥≤μ

Approximate CVP

Given a lattice LLL with an arbitrary basis B\mathcal BB and a vector w∈Rnw \in \mathbb{R}^nw∈Rn find the closest lattice vector to www v∈L,∥v−w∥<γ(n)⋅μv \in {L}, \|v-w\| < \gamma(n) \cdot \muv∈L,∥v−w∥<γ(n)⋅μ

Decision CVP (GapCVP)

Given a lattice LLLwith a basis B\mathcal BB and a vector www we must decide if

  • There exists v∈Lv \in Lv∈Ls.t ∥v−w∥≤1\| v - w\| \leq 1∥v−w∥≤1

  • ∀v∈L:∥v−w∥>γ(n)\forall v \in L: \|v - w\| > \gamma(n)∀v∈L:∥v−w∥>γ(n)

Sage example

M = matrix([[-1, 2], [-2, 3]])
L = IntegerLattice(M)

w = vector([1.8, 1.5])
L.closest_vector(w)
# (2.00000000000000, 2.00000000000000)

Bounded distance decoding

Given a lattice LLL with an arbitrary basis BBB, a vector w∈Rnw \in \mathbb{R}^nw∈Rn and a real number d∈Rd \in \mathbb{R}d∈R find a lattice vector v∈Lv \in {L}v∈L s.t ∥w−v∥<d⋅λ1(L)\|w-v\| < d \cdot \lambda_1({L})∥w−v∥<d⋅λ1​(L)

Remark

  • If we have d<12d < \dfrac 12d<21​ the solution to the BDD problem is guaranteed to be unique.

Shortest independent vectors (SIVP)

Given a full rank lattice LLL with an arbitrary basis B\mathcal BBfind nnn linearly independent lattice vectors of length at most λn(L)⇒max⁡i∥vi∥≤λn(L)\lambda_n(L) \Rightarrow \max_i\|v_i\| \leq \lambda_n(L)λn​(L)⇒maxi​∥vi​∥≤λn​(L) or max⁡i∣vi∣≤γ(n)λn(L)\max_i|v_i| \leq \gamma(n) \lambda_n(L)maxi​∣vi​∣≤γ(n)λn​(L)for the approximate version.

Hardness of lattice problems

Resources

  • Or generated by me

PreviousExtensions of Coppersmith algorithmNextLattices of interest

Last updated 4 years ago

Was this helpful?

Pictures taken from and "Cryptography made simple - Nigel Smart" and edited a bit

https://simons.berkeley.edu/sites/default/files/docs/14953/intro.pdf