Lattice Cryptography

Lattice Cryptography

(permanently under construction!)

Navigation Bar

• Home

• Cryptography
  • CCA Encrypt
  • Functional Encryption
  • FHE
  • Group Sign
  • Hashing
  • Homomorphic Crypto
  • IBE
  • ZK and Id protocols
  • Key Exchange
  • Encryption
  • Sampling
  • Signatures
  • Foundation
  • Threshold Crypto

• Lattice Algorithms
  • Enumeration
  • Sieving
  • Voronoi
  • Basis Reduction
  • SIS/LWE

Lattice Algorithms based on Voronoi Cell Computation

The Voronoi cell computation algorithm of

1. A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
   (Micciancio & Voulgaris - SIAM J. Comput. 2013 / STOC 2010) [eccc, slides]

solves the Closest Vector Problem (CVP) (and a number of other related lattice problems, including SVP and SIVP) deterministically using time $O(2^{2n})$ and space $O(2^n)$.

The algorithm was the first one to solve CVP in single exponential time $2^{O(n)}$, improving the previous $n^{O(n)}$ upper bound based on enumeration methods. The algorithm of (1) is still the theoretically fastest deterministic algorithm to solve CVP and SVP, but its running time has been improved to $O(2^n)$ using randomization by combinatorial algorithms.

The algorithm of (1) is simple enough to be implemented and run in low dimension (say, $n<20$), but not competitive in practice with other methods based on Sieving or Enumeration techniques, due to its high space complexity and the fact that its actual running time is close to the theoretical worst-case upper bound.

The method of (1) to solve CVP after the Voronoi cell of the lattice has been computed is a variant of an algorithm first proposed in (2). The method is further studied in (3), and it is also related to the method used in (4) to solve CVP in certain lattices with special structure.

2. Finding the closest lattice point by iterative slicing
   (Sommer, Feder & Shalvi - SIAM J. Disc. Math. 2009)

3. Short paths on the Voronoi graph and closest vector problem with preprocessing
   (Dadush & Bonifas - SODA 2015)

4. Finding a closest point in a lattice of Voronoi’s first kind
   (McKilliam, Grant & Clarkson - SIAM J. Disc. Math. 2014)