Algorithmics and Lattices, some references

Lattice-based Cryptanalyses

Back to the main page

Cryptanalyses of the RSA Cryptosystem:

Low-exponent RSA with Related Messages, Coppersmith D. and Franklin M. and Patarin J. and Reiter M. (1996)
Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities, Coppersmith D. (1997)
An Attack on RSA Given a Small Fraction of the Private Key Bits, Boneh D. and Durfee G. and Frankel Y. (1998)
The Béguin-Quisquater Server-Aided RSA Protocol from Crypto '95 is not Secure, Nguyen P. and Stern J. (1998)
Twenty Years of Attacks on the RSA Cryptosystem, Boneh D. (1999)
Cryptanalysis of RSA with Private Key d less than N0.292, Boneh D. and Durfee G. (1999)
Extending Wiener's Attack in the Presence of Many Decrypting Exponents, Howgrave-Graham N. and Seifert J.P. (1999)
The Effectiveness of Lattice Attacks Against Low-Exponent RSA, Coupé C. and Nguyen P. and Stern J. (1999)
Cryptanalysis of the RSA Schemes with Short Secret Exponent from Asiacrypt '99, Durfee G. and Nguyen P. (2000)
Low Secret Exponent RSA Revisited, Blömer J. and May A. (2001)
On the Insecurity of a Server-Aided RSA Protocol, Nguyen P. and Shparlinski I. (2001)
Cryptanalysis of Unbalanced RSA with Small CRT-Exponent, May A. (2002)
Cryptanalysis of RSA with Small Prime Difference, De Weger B. (2002)
New Partial Key Exposure Attacks on RSA, Blömer J. and May A. (2003)
Attacking Unbalanced RSA-CRT Using SPA, Fouque P.-A. and Martinet G. and Poupard G. (2003)
A Generalized Wiener Attack on RSA, Blömer J. and May A. (2004)
Secret Exponent Attacks on RSA-type Schemes with Moduli N=p^rq, May A. (2004)
Computing the RSA Secret Key is Deterministic Polynomial Time Equivalent to Factoring, May A. (2004)

Cryptanalyses of Digital Signature Schemes:

"Pseudo-Random" Number Generation within Cryptographic Algorithms: the DSS Case, Bellare M. and Goldwasser S. and Micciancio D. (1997)
Lattice Attacks on Digital Signature Schemes, Howgrave-Graham N. and Smart N.P. (1999)
The Insecurity of the Digital Signature Algorithm with Partially Known Nonces, Nguyen P. and Shparlinski I. (2002)
The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces, Nguyen P. and Shparlinski I. (2002)
On the Security of RDSA, Fouque P.A. and Poupard G. (2003)
Experimenting with Faults, Lattices and the DSA, Naccache D., Nguyen P., Tunstall M. and Whelan C. (2005)

Cryptanalyses of Linear Congruential Generators:

Linear Congruential Generators Do Not Produce Random Sequences, FOCS 1984, Frieze A. and Kannan R. and Lagarias J. (1984)
The Cryptographic Security of Truncated Linearly Related Variables, STOC 1985, Håstad J. and Shamir A. (1985)
Secret Linear Congruential Generators are not Cryptographically Secure, Proc of the IEEE Symposium on Foundations of Computer Science, Stern J. (1987)
Reconstructing Truncated Integer Variables Satisfying Linear Congruences, SIAM J. Comput. 17, Frieze A. and Håstad J. and Kannan R. and Lagarias J. and Shamir A. (1988)

Cryptanalyses of Knapsack based Cryptosystems:

A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem, CRYPTO 1982, Shamir A. (1982)
A Preliminary Report on the Cryptanalysis of Merkle-Hellman Knapsack Cryptosystems, CRYPTO 1982, Brickell E. and Davis A. and Simmons G. (1982)
Knapsack Public Key Cryptosystems and Diophantine Approximation, CRYPTO 1983, Lagarias J. (1983)
Evaluation of the Adleman Attack on Multiply Iterated Knapsack Cryptosystems, CRYPTO 1983, Brickell E. and Lagarias J. and Odlyzko A.(1983)
Solving Low-Density Subset Sum Problems, FOCS 1983, Lagarias J. and Odlyzko A.(1983)
Breaking Iterated Knapsacks, CRYPTO 1984, Brickell E. (1984)
Performance Analysis of Shamir's Attack on the Basic Merkle-Hellman Knapsack Cryptosystem, ICALP 1984, Lagarias J. (1984)
An Improved Low-Density Subset Sum Algorithm, EUROCRYPT 1991, Coster J. and LaMacchia B. and Odlysko A. (1991)
The cryptanalysis of a New Public-key Cryptosystem Based on Modular Knapsacks, Crypto 91, LNCS 576, Chee Y.M. and Joux A. and Stern J. (1991)
Improving the Critical Density of the Lagarias-Odlyzko Attack against Subset Sum Problems, Fundamentals of Computation Theory, LNCS 529, Joux A. and Stern J. (1991)
Cryptanalysis of Another Knapsack Cryptosystem, Asiacrypt 91, LNCS 739, Joux A. and Stern J. (1992)
Improved Low-density Subset Sum Algorithms, Coster M. and Joux A. and LaMacchia B. and Odlyzko A. and Schnorr C.P. and Stern J. (1992)
Practical Attack against Knapsack based Hash Functions, Joux A. and Granboulan L. (1994)
Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction, Schnorr C.P. and Hörner H.H. (1995)
Breaking Knapsack Cryptosystems by Max-Norm Enumeration, Ritter H. (1996)
Merkle-Hellman Revisited: a Cryptanalysis of the Qu-Vanstone Cryptosystem Based on Group Factorizations, Nguyen P. and Stern J. (1997)

Other Lattice-based Cryptanalyses:

How to Break Okamoto's Cryptosystem by Reducing Lattice Bases, EUROCRYPT 1988, Girault M. and Toffin P. and Vallée B. (1988)
Cryptanalysis of a Public-key Cryptosystem Based on Approximations by Rational Numbers, Eurocrypt 90, LNCS 473, Stern J. and Toffin P. (1990)
On the Security of the KMOV Public Key cryptosystem, Bleichenbacher D. (1997)
The Multi-Variable Modular Polynomial and its Applications to Cryptography, Naito S. and Takagi T. (1997)
Cryptanalysis of a Fast Public Key Cryptosystem Presented at SAC '97, Nguyen P. and Stern J. (1998)
Cryptanalysis of MQV with partially known nonces, Leadbitter P. and Smart N. (2002)
Can We Trust Cryptographic Software? Cryptographic Flaws in GNU Privacy Guard v1.2.3 Nguyen P. (2004)

Last update: 12/21/2004. Page maintained by Damien Stehlé.