Lattice reduction: A toolbox for the cryptanalyst

In recent years, methods based on lattice reduction have been used repeatedly for the cryptanalytic attack of various systems. Even if they do not rest on highly sophisticated theories, these methods may look a bit intricate to practically oriented cryptographers, both from the mathematical and the...

Full description

Saved in:
Bibliographic Details
Published in:Journal of cryptology 1998-06, Vol.11 (3), p.161-185
Main Authors: JOUX, A, STERN, J
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Cryptography
Exact sciences and technology
Information, signal and communications theory
Reduction
Signal and communications theory
Telecommunications and information theory
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In recent years, methods based on lattice reduction have been used repeatedly for the cryptanalytic attack of various systems. Even if they do not rest on highly sophisticated theories, these methods may look a bit intricate to practically oriented cryptographers, both from the mathematical and the algorithmic point of view. The aim of this paper is to explain what can be achieved by lattice reduction algorithms, even without understanding the actual mechanisms involved. Two examples are given. One is the attack devised by the second author against Knuth's truncated linear congruential generator. This attack was announced a few years ago and appears here for the first time in complete detail.
ISSN:0933-2790
1432-1378
DOI:10.1007/s001459900042