Lattice reduction: a toolbox for the cryptoanalyst (Q1272333): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s001459900042 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1981326822 / rank | |||
Normal rank |
Latest revision as of 03:22, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Lattice reduction: a toolbox for the cryptoanalyst |
scientific article |
Statements
Lattice reduction: a toolbox for the cryptoanalyst (English)
0 references
26 August 1999
0 references
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.
0 references
lattices
0 references
cryptanalysis
0 references
knapsack cryptosystems
0 references
linear congruential generators
0 references