Lattice reduction: A toolbox for the cryptanalyst

被引:93
作者
Joux, A [1 ]
Stern, J
机构
[1] DGA, CELAR, Bruz, France
[2] Ecole Normale Super, Lab Informat, F-75231 Paris, France
关键词
lattices; cryptanalysis; knapsack cryptosystems;
D O I
10.1007/s001459900042
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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.
引用
收藏
页码:161 / 185
页数:25
相关论文
共 33 条
[21]   SOLVING LOW-DENSITY SUBSET SUM PROBLEMS [J].
LAGARIAS, JC ;
ODLYZKO, AM .
JOURNAL OF THE ACM, 1985, 32 (01) :229-246
[22]  
LAGARIAS JC, 1983, P 24 IEEE S FDN COMP, P1
[23]  
LAGRANGE L, 1773, NOUV MEM ACAD, P265
[24]  
LENSTRA AK, 1982, MATH ANNELAN, V261, P513
[25]   INTEGER PROGRAMMING WITH A FIXED NUMBER OF VARIABLES [J].
LENSTRA, HW .
MATHEMATICS OF OPERATIONS RESEARCH, 1983, 8 (04) :538-548
[26]   HIDING INFORMATION AND SIGNATURES IN TRAPDOOR KNAPSACKS [J].
MERKLE, RC ;
HELLMAN, ME .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1978, 24 (05) :525-530
[27]  
MINKOWSKI H, 1910, GEOMETRIE ZHALEM
[28]  
Plumstead J.B, 1982, P 23 ANN IEEE S FDN, P153
[29]   A HIERARCHY OF POLYNOMIAL-TIME LATTICE BASIS REDUCTION ALGORITHMS [J].
SCHNORR, CP .
THEORETICAL COMPUTER SCIENCE, 1987, 53 (2-3) :201-224
[30]  
SCHNORR CP, 1991, LECT NOTES COMPUT SC, V529, P68