Lattices

From Wiki

Jump to: navigation, search

A lattice $Λ$ of dimension $n$ is a discrete subgroup of $\mathbb{R}^d$ , where $d \geq n$ . For applications in cryptography one usually restricts to lattices in $\mathbb{Z}^d$ . A lattice is specified by a $d \times n$ basis matrix $B$ , consisting of $n$ linearly independent basis vectors $\vec{b}_i \in \mathbb{R}^d$ . With $Λ(B)$ we denote the lattice spanned by the basis $B$ .

Main Lattice Problems

SVP_γ^p: (Approximate) Shortest vector problem

Definition: Given a basis $B \in \mathbb{Z}^{m \times n}$ and real $γ > 0$ , find a nonzero lattice vector $v \in B \mathbb{Z}^n \setminus \{0\}$ such that $\|v\|_p \le \gamma \lambda_1^p(B)$ .

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 $B \in \mathbb{Z}^{m \times n}$ , real $γ > 0$ , and $t \in B \mathbb{R}^n$ , find a nonzero lattice vector $v \in B \mathbb{Z}^n$ such that $\|t - v\|_p \le \gamma \lambda_1^p(B)$ .

Reductions:

GapCVP_γ^p ≡_P CVP_γ^p
SVP_γ² ≤_P CVP_γ²

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 $B \in \mathbb{Z}^{m \times n}$ , lattice vector $v \in B \mathbb{Z}^n$ and reals $d,γ > 0$ decide

YES: If $\min\{ \| v \|_p : v \in B \mathbb{Z}^n \setminus \{0\} \} \le d$ ,
NO: If $\min\{ \| v \|_p : v \in B \mathbb{Z}^n \setminus \{0\} \} > \gamma d$ ,

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² is NP-complete under randomized reductions.

References:

GapCVP_γ^p: Decisional closest vector problem

Definition: Given a basis $B \in \mathbb{Z}^{m \times n}$ , vector $t \in B \mathbb{R}^n$ and reals $d,γ > 0$ decide

YES: If $\min\{ \| t - v \|_p : v \in B \mathbb{Z}^n \} \le d$ ,
NO: If $\min\{ \| t - v \|_p : v \in B \mathbb{Z}^n \} > \gamma d$ ,

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 $A \in \mathbb{Z}^{n \times m}_q$ , where $A$ is chosen from a distribution negligibly close to uniform over $\mathbb{Z}^{n \times m}_q$ . Then $\Lambda^\perp_q(A) = \lbrace \vec{x} \in \mathbb{Z}^m : A\vec{x} \equiv \vec{0} \in \mathbb{Z}^n \pmod{q} \rbrace$ is an $m$ -dimensional lattice. The task is to find a vector $\vec{v} \in \Lambda^\perp_q(A)$ with $\|\vec{v}\|_p \le \beta$ .

Reductions:

Worst-case to average-case reduction: SIVP $\,^p(n,\beta \tilde{\mathcal{O}}(n))$ ≤_P SIS $\,^p(n,m=n^{c_1},q,\beta=n^{c_2})$ for $c_1,c_2 = \mathcal{O}(1)$ , and prime $q \ge \beta \omega(n\log(n))$ . The expression $\tilde{\mathcal{O}}(n)$ hides poly-logarithmic factors in $n$ .
Tightest worst-case to average-case reduction: SIVP $\,^p(n,\tilde{\mathcal{O}}(n))$ ≤_P SIS $\,^p(n,n^{c},\tilde{\mathcal{O}}(n),\sqrt{m})$ for $c = \mathcal{O}(1)$ 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 $\ell_2$ and $\ell_\infty$ 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, $A \in \mathbb{Z}^{n \times m}_q$ , and $\vec{y} \in \mathbb{Z}^n$ . Both, $A$ and $y$ are chosen from a distribution negligibly close to uniform over the respective domain. The task is to find a vector $\vec{v} \in \lbrace \vec{x} \in \mathbb{Z}^m : A\vec{x} \equiv \vec{y} \pmod{q} \rbrace$ with $\|\vec{v}\|_p \le \beta$ .

The remaining properties carry over from SIS.

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

Definition: Let $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ denote the additive group on the reals modulo one. Denote by $A s,φ$ the distribution on $\mathbb{Z}_q^n \times \mathbb{T}$ obtained by choosing a vector $\mathbf{a}\in \mathbb{Z}_q^n$ uniformly at random, choosing $e$ according to a probability distribution $φ$ on $\mathbb{T}$ and outputting $(\mathbf{a},\langle \mathbf{a},s \rangle /q + e)$ for some fixed vector $\mathbf{s} \in \mathbb{Z}_q^n$ .

The search version of the learning with errors problem $L W E n, q,φ$ is to find the secret $s \in \mathbb{Z}_q^n$ , 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 $\vec{v} \in \Lambda \setminus \lbrace\vec{0}\rbrace$ with $\|\vec{v}\|_p \le \gamma \lambda^{(p)}_1(\Lambda)$ , where $\lambda^{(p)}_1(\Lambda)$ is the first successive minimum of $Λ$ in the $p$ -norm and the shortest lattice vector $\vec{u}$ is $γ$ -unique. In other words, for all $\vec{w} \in \Lambda$ with $\lambda^{(p)}_1(\Lambda) \le \| \vec{w} \|_p \le \gamma \lambda^{(p)}_1(\Lambda)$ , we have $\vec{w} = z \vec{u}$ for some $z \in \mathbb{Z}$ .

Reductions:

GapSVP^p(n,γ) ≤_PUSVP^p(n,γ/(6 n^1/2)) for γ > 6 n^1/2

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 $\Lambda \subseteq \mathbb{R}^d$ be an $n$ -dimensional lattice. The task is to find a basis $B$ of $Λ$ such that for all $B^\prime \in \lbrace B \in \mathbb{Q}^{d \times n} : \Lambda = \Lambda(B) \rbrace$ $\max^n_{i=1}\lbrace\|\vec{b}_i\|_p\rbrace \le \gamma \max^n_{i=1}\lbrace\|\vec{b^\prime}_i\|_p\rbrace$ .

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 $\vec{v} \in \Lambda \setminus \lbrace\vec{0}\rbrace$ such that $\lambda^{(p)}_1(\Lambda) \le \lambda^{(p)} \le \gamma \lambda^{(p)}_1(\Lambda)$ . $\lambda_1^{(p)}(\Lambda)$ 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 $\vec{v}_1, \ldots, \vec{v}_n \in \Lambda$ with with $\max^n_{i=1} \|\vec{v}_i\|_p \le \gamma \lambda^{(p)}_n(\Lambda)$ , where $\lambda^{(p)}_n(\Lambda)$ is the $n$ th successive minimum of $Λ$ in the $p$ -norm.

Reductions:

SBP^p(n,γ n) ≤_P SIVP^p(n,γ)

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 $B \in \mathbb{Z}^{m \times n}$ ( $m \geq n$ ), and $\gamma \geq 1$ , find a nonzero vector $v$ of norm $||v|| \leq \gamma det(L(B))^{1/n}$

Reductions: γ²-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 $\gamma \geq 1$ , the input to CRP is a pair $(B, r)$ , where $B$ is a basis matrix $B \in \mathbb{Z}^{m \times n}$ ( $m \geq n$ ), and $r \in \mathbb{R}$ .

$(B, r)$ is a YES instance if $\rho(L(B)) \leq r$
$(B, r)$ is a NO instance if $\rho(L(B)) > \gamma \cdot r$

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 $R = \mathbb{Z}[x] / \langle f \rangle$ be the ring of integer polynomials modulo some monic polynomial $f$ of degree $n$ . Since $R$ is isomorphic to $\mathbb{Z}^n$ 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 $\mathbb{Z}[x] / \langle f \rangle$ find a polynomial $g \in I \setminus \{0\}$ , such that $\| g \ \bmod \ f \|_p \leq \gamma \lambda_1^p(I)$ .

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 $g_1, \ldots, g_m$ chosen uniformly at random from $\mathbb{Z}_q[x] / \langle f \rangle$ , find $e_1, \ldots, e_m$ in $\mathbb{Z}[x]$ , such that $\sum_{i \leq m} e_ig_i = 0 \pmod{q}$ and $\| e \|_p \leq \beta$ , 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 $f \in \mathbb{Z}[x]$ is monic, irreducible, $\deg(f)=n, m = \Omega(\log(n)), q = \tilde{\Omega}(EF(f,3) \beta m^2 n)$ prime, and $\gamma = \tilde{O}(EF^2(f,2) \beta m n^{1/2})$ , where $EF(f,k) := \max \{ \|g \ \bmod \ f\| / \| g \| : g \in \mathbb{Z}[x]/ \{0\},\ \deg(g) \leq k (\deg(f)-1) \}$ .

Algorithms:

History:

Remark:

References:

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

Retrieved from "http://www.ecrypt.eu.org/wiki/index.php/Lattices"

Views

Personal tools

Log in / create account

Search

Toolbox