On the second day of the Workshop HEAT, Antoine Joux gave an invited talk on the history of cryptanalytic applications of lattice-basis reduction algorithms.
Lattice
is a discrete subgroup of $\mathbb{R}^n$. Equivalently, it is a span of
integer-linear combinations of $\mathbb{R}$-linearly independent
vectors in $\mathbb{R}^n$. Finding a short basis in $\mathbb{R}^2$ is
relatively easy and Gauss' lattice-basis reduction algorithm is
effective for this purpose. As the speaker emphasised, things become
more complicated when we move to higher dimensions. He then went on to
discuss the details of the famous LLL algorithm, invented by
Lenstra, Lenstra and Lovász in 1982, for lattice-basis reduction in
arbitrary dimensions. LLL is a polynomial-time algorithm but returns a
short vector within an exponential approximation factor of the length of
the shortest vector in the lattice. This algorithm, which performs well
in practice, may be viewed as a combination of the Gauss lattice
reduction and the Gram-Schmidt orthogonalisation methods.
An early application of lattice-basis reduction is the cryptanalysis of knapsack-based cryptosystems. The knapsack problem, a.k.a. the subset-sum problem, is given integers $a_1, \ldots, a_n$, and $S$, find $\epsilon_1,\ldots,\epsilon_n \in \{0,1\}$ such that
\[S = \overset{n}{\underset{i=1}{\sum}} \epsilon_i \cdot a_ i.\]
This problem is NP-hard though some cases are easy, and it served as a basis for cryptosystems such as Merkle-Hellman
cryptosystem. The basic idea is to hide an easy knapsack in a
hard-looking one. However, at CRYPTO 1982, Shamir broke this
cryptosystem using lattice-basis reduction. This attacks works for super-increasing knapsacks, where we have $a_i > \sum_{j=1}^{i-1} a_j$. Other works starting with that of Lagarias-Odlyzko in 1985 lead to improved attacks on low-density knapsacks.
The speaker also briefly spoke about the application of lattie-basis reduction to the problems of
- reconstructing small linear dependencies: let $(x_1,\ldots,x_n)$ be a sequence of real numbers, we need to find small coefficients $v_i$ such that $\sum v_i\cdot x_i =0$,
- constructing polynomials for use in the Number Field Sieve for solving the Discrete Logarithm Problem, and
- finding small roots of univariate and bivariate integer polynomials modulo composite numbers: Coppersmith's attack.
No comments:
Post a Comment