Lattice-based Cryptography

Daniele Micciancio · Oded Regev

Post-Quantum Cryptography 2009

Time bound

T_reduce(m, δ); m ≈ sqrt(n log₂(q) / log₂(δ))

Space bound

Depends on the selected lattice-reduction algorithm.

Source / version date

7 Nov 2008

Comparison variant

Dual lattice · parameterized models

Cost scale

Parameter-dependent time and space expressions

Parameters

Prime q=q(n); secret dimension n; root-Hermite factor δ; choose m only when enough samples are available.

Error distribution

Rounded Gaussian width αq; continuous standard deviation αq/√(2π).

Secret distribution

General LWE secret in Z_q^n.

Sample budget

At least m ≈ √(n log₂ q / log₂ δ); cap m by the actual sample budget.

Objective

Distinguish LWE from uniform using a short dual vector.

Cost model

Unscaled dual length ≈ q⁻¹ min(q, 2^{2√(n log₂(q) log₂(δ))}); source Eqs. (10)–(11).

Assumptions

Empirical lattice-reduction quality model for random q-ary lattices.

Success guarantee

Non-negligible distinguishing signal requires suitably small αq·||w||; no common fixed advantage is imposed here.

Assumptions and source notes

Early explicit dual-LWE geometry model. Shortness and dimension predictions do not supply a universal LWE running-time exponent.

Source location

§5, Security discussion, pp. 21–22, Eqs. (10)–(11)
Version: Author manuscript dated 7 November 2008; edited chapter February 2009

Primary source ↗

@misc{micciancio-regev2008-lbc,
  author = {Daniele Micciancio and Oded Regev},
  title = {{Lattice-based Cryptography}},
  year = {2009},
  url = {https://cseweb.ucsd.edu/~daniele/papers/PostQuantum.pdf},
  keywords = {LWE, algorithmic complexity, historical literature},
  cr_date = {2008-11-07},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Post-Quantum Cryptography, pp. 147–191; DOI 10.1007/978-3-540-88702-7_5},
  cr_author_ids = {daniele-micciancio; oded-regev},
  note = {Post-Quantum Cryptography, pp. 147–191; DOI 10.1007/978-3-540-88702-7_5}
}