Lattice reduction: a toolbox for the cryptoanalyst (Q1272333): Difference between revisions

A lattice \(L\) is a discrete subgroup of \(\mathbb R^n\), the set of integral linear combinations \[ {\lambda}_1 b_1 + \cdots+{\lambda}_p b_p \] of a given set of independent \(n\)-dimensional vectors \(b_1 , \dots , b_p\). The set \((b_1 , \ldots,b_p)\) is said to be a basis of \(L\) and \(p\) its dimension. An aim of the paper is explain the application of lattice techniques to cryptanalysis by transforming the cryptographic problem into a lattice reduction problem. A brief description of the LLL algorithm is given to determine an approximation to the shortest vector in a lattice, in the sense of finding a vector whose length does not exceed the length of the shortest vector by more than a given multiplicative constant which depends on the lattice dimension and the actual algorithm used. Some generic problems that come under the scope of lattice reduction problems are considered, including searching for a linear dependence relation with small coefficients among a family of vectors. The case of modular relations is also discussed, as well as solving knapsacks and finding minimal polynomials. Two specific cryptanalyses are given, using these techniques: the cryptanalysis of Knuth's truncated linear congruential generator [\textit{D. E. Knuth}, The Art of Computer Programming, Vol. 2, Addison-Wesley (1969; Zbl 0191.18001)] and the cryptanalysis of Damgård's hash function [\textit{I. Damgård}, Crypto 1989, Lect. Notes Comput. Sci. 435, 416--427 (1989; Zbl 0724.68029)]. A sequence of appendices elaborates further on lattices and their application.