# Lattices

### From Wiki

A **lattice** Λ of dimension *n* is a discrete subgroup of , where .
For applications in cryptography one usually restricts to lattices in .
A lattice is specified by a **basis matrix** *B*, consisting of *n* linearly independent basis vectors . With Λ(*B*) we denote the lattice spanned by the basis *B*.

#### Main Lattice Problems

##### SVP_{γ}^{p}: (Approximate) Shortest vector problem

Definition: Given a basis and real γ > 0, find a nonzero lattice vector such that .

Reductions: GapSVP_{γ}^{p} ≡_{P} SVP_{γ}^{p}

- USVP
^{p}(n,γ) ≤_{P}SVP^{p}(n,γ) - HermiteSVP
^{p}(n,γ,γ_{n}^{1/2}) ≤_{P}SVP^{p}(n,γ)

Algorithms: The best algorithms for SVP have exponential time. More efficient algorithms giving approximate solutions to the SVP include block-Korkine-Zolotarev and LLL.

Use in cryptography: identification schemes, digital signatures

History: SVP is a classical problem in number theory.

Remark: If not stated otherwise, γ=1, p=2. For NP-hardness see GapSVP.

References:

- Daniele Micciancio, Salil Vadhan. Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More. CRYPTO 2003.

##### CVP_{γ}^{p}: (Approximate) Closest vector problem

Definition: Given a basis , real γ > 0, and , find a nonzero lattice vector such that .

Reductions:

- GapCVP
_{γ}^{p}≡_{P}CVP_{γ}^{p} - SVP
_{γ}^{2}≤_{P}CVP_{γ}^{2}

Algorithms: The best algorithms for CVP have exponential time. More efficient algorithms, like Babai's nearest plane algorithm, give approximate solutions in polynomial time.

Use in cryptography: identification schemes, digital signatures

History:

Remark: If not stated otherwise, γ=1, p=2. Inhomogeneous version of SVP.

References:

- Daniele Micciancio, Salil Vadhan. Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More. CRYPTO 2003.

##### GapSVP_{γ}^{p}: Decisional shortest vector problem

Definition: Given a basis , lattice vector and reals *d*,γ > 0 decide

- YES: If ,
- NO: If ,

and arbitrarily otherwise.

Reductions: SVP_{γ}^{p} ≡_{P} GapSVP_{γ}^{p}

Algorithms:

Use in cryptography:

History:

Remark: If not stated otherwise, γ=1, p=2. GapSVP^{∞} is NP-complete, and GapSVP^{2} is NP-complete under randomized reductions.

References:

##### GapCVP_{γ}^{p}: Decisional closest vector problem

Definition: Given a basis , vector and reals *d*,γ > 0 decide

- YES: If ,
- NO: If ,

and arbitrarily otherwise.

Reductions:

- CVP
_{γ}^{p}≡_{P}GapCVP_{γ}^{p} - Subset-sum problem reduces to GapCVP, so the problem is NP-complete

Algorithms:

Use in cryptography:

History:

Remark: If not stated otherwise, γ=1, p=2

References:

#### Modular Lattice Problems

Modular lattice problems are typically defined as average-case problems.

##### SIS^{p}(n,m,q,β): Short integer solution problem

Definition: Let *q* be a prime and , where *A* is chosen from a distribution negligibly close to uniform over . Then is an *m*-dimensional lattice. The task is to find a vector with .

Reductions:

- Worst-case to average-case reduction: SIVP ≤
_{P}SIS for , and prime . The expression hides poly-logarithmic factors in*n*. - Tightest worst-case to average-case reduction: SIVP ≤
_{P}SIS for and prime*q*.

Algorithms:

Use in cryptography: Basis of security for provably secure lattice-based cryptography in general, i.e. not ideal, lattices.

History: In principle, Ajtai introduced the problem. The name, however, was established later.

Remark: The problem is mainly interesting for and norms.

References:

- Micciancio, Regev: Worst-Case to Average-Case Reductions Based on Gaussian Measures, SIAM J. Comput. Volume 37, Issue 1, pp. 267-302 (2007)
- Gentry, Peikert, and Vaikuntanathan: Trapdoors for Hard Lattices and New Cryptographic Constructions, STOC 2008

##### ISIS^{p}(n,m,q,β): Inhomogeneous short integer solution problem

Definition: Let *q* be a prime, , and . Both, *A* and *y* are chosen from a distribution negligibly close to uniform over the respective domain. The task is to find a vector with .

The remaining properties carry over from SIS.

##### LWE(n,q,φ): Learning with errors problem

Definition: Let denote the additive group on the reals modulo one.
Denote by *A*_{s,φ} the distribution on
obtained by choosing a vector uniformly at random,
choosing *e* according to a probability distribution φ
on and outputting
for some fixed vector .

The search version of the learning with errors problem ** LWE_{n,q,φ}** is to find
the secret , given access to polynomially many samples
of choice from

*A*

_{s,φ}. The decision version is to distinguish the probability distribution

*A*

_{s,φ}from the uniform random distribution.

Reductions: If there exists an efficient algorithm that solves LWE then there exists an efficient quantum algorithm that approximates the decision version of the shortest vector problem (GAP SVP) and the shortest independent vectors problem (SIVP).

Algorithms:

Use in cryptography:

History: Generalisation by Regev of the learning parity with noise problem.

Remark:

References:

- Oded Regev, On lattices, learning with errors, random linear codes, and cryptography, in Proceedings of the thirty-seventh annual

ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84-93

#### Miscellaneous Lattice Problems

##### USVP^{p}(n,γ): Approximate unique shortest vector problem

Definition: Let Λ be an *n*-dimensional lattice. The task is to find with , where is the first successive minimum of Λ in the *p*-norm and the shortest lattice vector is γ-unique.
In other words, for all with , we have for some .

Reductions:

Algorithms:

Use in cryptography: Is used to prove security of the Ajtai-Dwork and Regev cryptosystem.

History: One of the worst-case problems in Ajtai's worst-case to average case reduction. γ = 1 gives you the exact problem.

Remark:

References:

- Ajtai: Generating hard instances of lattice problems, STOC 1996
- Ajtai, Dwork: A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence, STOC 1997
- Regev: On lattices, learning with errors, random linear codes, and cryptography, STOC 2005
- Lyubashevsky: The
*n*^{c}-Unique Shortest Vector Problem is Hard, ePrint 2008/504

##### SBP^{p}(n,γ): Approximate shortest basis problem

Definition: Let be an *n*-dimensional lattice. The task is to find a basis *B* of Λ such that for all .

Reductions:

Algorithms:

Use in cryptography:

History: One of the worst-case problems in Ajtai's worst-case to average case reduction. γ = 1 gives you the exact problem.

Remark:

References:

- M. Ajtai: Generating hard instances of lattice problems, STOC 1996

##### SLP^{p}(n,γ): Approximate shortest length problem

Definition: Let Λ be an *n*-dimensional lattice. The task is to find the approximate length (w.r.t. the *p*-norm) λ^{(p)} of the shortest vector such that . denotes the first successive minimum of Λ in the *p*-norm.

Reductions:

Algorithms:

Use in cryptography:

History: One of the worst-case problems in Ajtai's worst-case to average case reduction. γ = 1 gives you the exact problem.

Remark:

References:

- M. Ajtai: Generating hard instances of lattice problems, STOC 1996

##### SIVP^{p}(n,γ): Approximate shortest independent vector problem

Definition: Let Λ be an *n*-dimensional lattice. The task is to find linearly independent vectors with with , where is the *n*th successive minimum of Λ in the *p*-norm.

Reductions:

Algorithms:

Use in cryptography:

History: γ = 1 gives you the exact problem.

Remark:

References:

- M. Ajtai: Generating hard instances of lattice problems, STOC 1996

##### hermiteSVP: Hermite shortest vector problem

Definition: Given a basis matrix (), and , find a nonzero vector *v* of norm

Reductions:
γ^{2}-SVP ≤_{P} γ-hermiteSVP

Algorithms: all polynomial time lattice reduction algorithms are Hermite-SVP algorithms, with approximation factor γ exponential in the lattice dimension *n*

Use in cryptography:

History:

Remark:

References:

- Nicolas Gama and Phong Q. Nguyen, Predicting lattice reduction, LNCS 4965, pp. 31-51, Eurocrypt 2008

##### CRP: Covering radius problem

Definition: Given an approximation factor , the input to CRP is a pair (*B*,*r*), where *B* is a basis matrix (), and .

- (
*B*,*r*) is a YES instance if - (
*B*,*r*) is a NO instance if

Reductions:

Algorithms: The CRP problem can be solved approximately (with approximation factor exponential in *n*) in polynomial time using SVP algorithms. It can be solved in exponential time using CVP algorithms for an approximation factor of 1 + ε.

Use in cryptography:

History:

Remark: The problem is defined in its promise version. This version is equivalent to compute the covering radius approximately. For details refer to the book of Micciancio and Goldwasser. The problem can also be defined for linear codes.

References:

- Venkatesan Guruswami, Daniele Micciancio, and Oded Regev, The complexity of the covering radius problem on lattices and codes, Proceedings of CCC 2004
- Daniele Micciancio and Shafi Goldwasser, Complexity of lattice problems - A cryptographic perspective, Kluwer Academic Publishers, 2002
- Ishay Haviv and Oded Regev, Hardness of the covering radius problem on lattices, Computational Complexity, CCC 2006

#### Ideal Lattice Problems

Let be the ring of integer polynomials modulo some monic polynomial *f* of degree *n*. Since *R* is isomorphic to as an additive group and ideals in *R* are by definition subgroups, they correspond to lattices. Lattices of this form are *ideal lattices* with respect to *f*.

##### Ideal-SVP_{γ}^{f,p}: (Approximate) Ideal shortest vector problem / Shortest polynomial problem

Definition: Given an ideal *I* in find a polynomial , such that .

Reductions:

Algorithms: The best algorithms for Ideal-SVP have exponential time. More efficient algorithms giving approximate solutions to the SVP include block-Korkine-Zolotarev (BKZ) and LLL.

Use in cryptography: hash functions, digital signatures, public-key encryption, identification schemes

History:

Remark: Not known to be NP-hard for any parameters.

References:

- Lyubashevsky, Micciancio: Generalized compact knapsacks are collision resistant. In Proceedings of ICALP, LNCS volume 4052, pages 144-155, Springer 2006.

##### Ideal-SIS_{q,m,β}^{f,p}: Ideal small integer solution problem

Definition: Given *n* and chosen uniformly at random from , find in , such that and , where the vector *e* is obtained by concatenating the coefficients of all *e*_{i}'s.

Reductions:

- Worst-case to average-case reduction: Ideal-SVP
^{f,2}(γ) ≤_{p}Ideal-SIS^{f,2}(*q*,*m*,β), assuming is monic, irreducible, prime, and , where .

Algorithms:

History:

Remark:

References:

- Lyubashevsky, Micciancio: Generalized compact knapsacks are collision resistant. In Proceedings of ICALP, LNCS volume 4052, pages 144-155, Springer 2006.