article

Lattice Reduction: A Toolbox for the Cryptanalyst

Authors:

Jacques SternAuthors Info & Claims

Journal of Cryptology, Volume 11, Issue 3

Pages 161 - 185

https://doi.org/10.1007/s001459900042

Published: 01 June 1998 Publication History

Abstract

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.

References

[1]

L. M. Adleman. On breaking generalized knapsack public key cryptosystems. In Proceedings of the 15th ACM Symposium on Theory of Computing, pages 402-412, 1983.

Digital Library

[2]

J. Boyar. Inferring sequences produced by a linear congruential generator missing low-order bits. J. Cryptology, 1(3):177-184, 1989.

Digital Library

[3]

E. F. Brickell. Solving low density knapsacks. In D. C. Chaum, editor, Proceedings of CRYPTO 83, pages 25-37. Plenum, New York, 1984.

[4]

E. F. Brickell. Breaking iterated knapsacks. In G. R. Blakley and D. C. Chaum, editors, Proceedings CRYPTO 84, pages 342-358. Lecture Notes in Computer Science, volume 196. Springer-Verlag, Berlin, 1985.

Digital Library

[5]

M. J. Coster, A. Joux, B. A. LaMacchia, A. Odlyzko, C.-P. Schnorr, and J. Stern. Improved low-density subset sum algorithms. Comput. Complexity, 2:11-28, 1992.

Digital Library

[6]

Y. M. Chee, A. Joux, and J. Stern. The cryptanalysis of a new public-key cryptosystem based on modular knapsacks. In J. Feigenbaum, editor, Advances in Cryptology: Proceedings of Crypto '91, pages 204-212. Lecture Notes in Computer Science, volume 576. Springer-Verlag, Berlin, 1991.

Digital Library

[7]

D. Coppersmith. Finding a small root of a univariate modular equation. In U. Maurer, editor, Proceedings of EUROCRYPT 96, pages 155-165. Lecture Notes in Computer Science, volume 1070. Springer-Verlag, Berlin, 1996.

Digital Library

[8]

P. Camion and J. Patarin. The knapsack hash-function proposed at Crypto '89 can be broken. In D. W. Davies, editor, Advances in Cryptology, Proceedings of Eurocrypt '91, pages 39-53. Lecture Notes in Computer Science, volume 547. Springer-Verlag, Berlin, 1991.

Digital Library

[9]

D. Coppersmith and A. Shamir. Lattice attacks on NTRU. In W. Fumy, editor, Proceedings of EUROCRYPT 97, pages 52-61. Lecture Notes in Computer Science, volume 1233. Springer-Verlag, Berlin, 1997.

Digital Library

[10]

I. Damgård. A design principle for hash functions. In Advances in Cryptology, Proceedings of Crypto '89, pages 25-37. Lecture Notes in Computer Science, volume 435. Springer-Verlag, Berlin, 1989.

Digital Library

[11]

A. M. Frieze. On the Lagarias-Odlyzko algorithm for the subset sum problems. SIAM J. Comput., 15(2):536-539, 1986.

Digital Library

[12]

A. M. Frieze, J. Hastad, R. Kannan, J. C. Lagarias, and A. Shamir. Reconstructing truncated integer variables satisfying linear congruences. SIAM J. Comput., 17(2):262-280, 1988.

Digital Library

[13]

C. F. Gauss. Disquisitiones arithmeticae. Leipzig, 1801.

[14]

L. Granboulan and A. Joux. A practical attack against knapsack based hash functions. In Proceedings of EUROCRYPT 94, pages 58-66. Lecture Notes in Computer Science, volume 950. Springer-Verlag, Berlin, 1995.

[15]

C. Hermite. Extraits de lettres de M. Hermite à M. Jacobi sur différents objets de la théorie des nombres, deuxième lettre. J. Reine Angew. Math., 40:279-290, 1850.

[16]

A. Joux. La Réduction de Réseaux en Cryptographie. Ph.D. thesis, Ecole Polytechnique, Palaiseau, 1993.

[17]

A. Joux and J. Stern. Cryptanalysis of another knapsack cryptosystem. In Advances in Cryptology: Proceedings of AsiaCrypt '91, pages 470-476. Lecture Notes in Computer Science, volume 739. Springer-Verlag, Berlin, 1991.

Digital Library

[18]

D. E. Knuth. The Art of Computer Programming, volume 2. Addison-Wesley, Reading, MA, 1969.

[19]

D. E. Knuth. Deciphering a linear congruential encryption. Technical Report 024800, Stanford University, 1980.

[20]

A. Korkine and G. Zolotarev. Sur les formes quadratiques. Math. Ann., 6:336-389, 1873.

[21]

L. Lagrange. Recherches d'arithmétique, pages 265-312. Nouv. Mém. Acad., Berlin, 1773.

[22]

H.W. Lenstra. Integer programming with a fixed number of variables. Math. Oper. Res., 8:538-548, 1983.

Digital Library

[23]

A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász. Factoring polynomials with rational coefficients. Math. Ann., 261:513-534, 1982.

[24]

J. C. Lagarias and A. M. Odlyzko. Solving low-density subset sum problems. J. Assoc. Comput. Mach., 32:229-246, 1985. Preliminary version in Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, pages 1-10, 1983.

Digital Library

[25]

H. Minkowski. Geometrie der Zahlen. Teubner, Leipzig, 1910.

[26]

R. Merkle and M. Hellman. Hiding information and signatures in trapdoor knapsacks. IEEE Trans. Inform. Theory, IT-24:525-530, 1978.

Digital Library

[27]

J. Plumstead. Inferring a sequence generated by a linear congruence. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, pages 153-159. IEEE, New York, 1982.

Digital Library

[28]

C.-P. Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci., 53:201-224, 1987.

[29]

C.-P. Schnorr. A more efficient algorithm for lattice basis reduction. J. Algorithms, 9:47-62, 1988.

Digital Library

[30]

C.-P. Schnorr and M. Euchner. Lattice basis reduction: improved practical algorithms and solving subset sum problems. In L. Budach, editor, Proceedings of Fundamentals of Computation Theory 91, pages 68-85. Lecture Notes in Computer Science, volume 529. Springer-Verlag, Berlin, 1991.

Digital Library

[31]

A. Shamir. A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, pages 145-152. IEEE, New York, 1982.

[32]

J. Stern. Secret linear congruential generators are not cryptographically secure. In Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, pages 421-426. IEEE, New York, 1987.

Digital Library

[33]

J. Stern and P. Toffin. Cryptanalysis of a public-key cryptosystem based on approximations by rational numbers. In Advances in Cryptology: Proceedings of Eurocrypt '90, pages 313-317. Lecture Notes in Computer Science, volume 473. Springer-Verlag, Berlin, 1990.

Digital Library

Cited By

Yu HZheng QLiu YBi JDuan YXue JWu YCao YCheng RWang LSun B(2023)An improved method for predicting truncated multiple recursive generators with unknown parametersDesigns, Codes and Cryptography10.1007/s10623-022-01175-491:5(1713-1736)Online publication date: 10-Jan-2023
https://dl.acm.org/doi/10.1007/s10623-022-01175-4
May ANowakowski J(2023)Too Many Hints – When LLL Breaks LWEAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8730-6_4(106-137)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-99-8730-6_4
Gutierrez J(2022)Attacking the linear congruential generator on elliptic curves via lattice techniquesCryptography and Communications10.1007/s12095-021-00535-614:3(505-525)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1007/s12095-021-00535-6
Show More Cited By

Recommendations

Cryptanalysis of a round optimal lattice-based multisignature scheme
Abstract
Kansal and Dutta recently proposed a multisignature scheme at AFRICACRYPT 2020. This is the first lattice-based multisignature scheme that generates a multisignature in only a single round of interaction and supports public key ...
Highlights
- We cryptanalyze Kansal and Dutta's multisignature scheme by launching a forgery attack.
Cryptanalysis and Improvement of a Certificateless Multi-proxy Signature Scheme

Certificateless cryptography is a new type of public key cryptography, which removes the certificate management problem in traditional public key cryptography and the key escrow problem in identity-based public key cryptography. Multi-proxy signature is ...
Collision Attacks Against CAESAR Candidates
Proceedings, Part II, of the 21st International Conference on Advances in Cryptology --- ASIACRYPT 2015 - Volume 9453

In this paper we study authenticated encryption algorithms inspired by the OCB mode Offset Codebook. These algorithms use secret offsets masks derived from a whitening key to turn a block cipher into a tweakable block cipher, following the XE or XEX ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Cryptology

Journal of Cryptology Volume 11, Issue 3

June 1998

70 pages

ISSN:0933-2790

Issue’s Table of Contents

Copyright © Copyright © 1998 International Association for Criptologic Research.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 June 1998

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yu HZheng QLiu YBi JDuan YXue JWu YCao YCheng RWang LSun B(2023)An improved method for predicting truncated multiple recursive generators with unknown parametersDesigns, Codes and Cryptography10.1007/s10623-022-01175-491:5(1713-1736)Online publication date: 10-Jan-2023
https://dl.acm.org/doi/10.1007/s10623-022-01175-4
May ANowakowski J(2023)Too Many Hints – When LLL Breaks LWEAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8730-6_4(106-137)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-99-8730-6_4
Gutierrez J(2022)Attacking the linear congruential generator on elliptic curves via lattice techniquesCryptography and Communications10.1007/s12095-021-00535-614:3(505-525)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1007/s12095-021-00535-6
Gao JXu JHu L(2022)Inferring Sequences Produced by the Quadratic GeneratorInformation Security and Cryptology10.1007/978-3-031-26553-2_26(483-494)Online publication date: 11-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-26553-2_26
Martinez F(2022)Attacks on Pseudo Random Number Generators Hiding a Linear StructureTopics in Cryptology – CT-RSA 202210.1007/978-3-030-95312-6_7(145-168)Online publication date: 7-Feb-2022
https://dl.acm.org/doi/10.1007/978-3-030-95312-6_7
Aggarwal DChen YKumar RLi ZStephens-Davidowitz NMarx D(2021)Dimension-preserving reductions between SVP and CVP in different p-normsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458209(2444-2462)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458209
Kirchner PEspitau TFouque P(2021)Towards Faster Polynomial-Time Lattice ReductionAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84245-1_26(760-790)Online publication date: 16-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-84245-1_26
Sun HZhu XZheng Q(2020)Predicting truncated multiple recursive generators with unknown parametersDesigns, Codes and Cryptography10.1007/s10623-020-00729-888:6(1083-1102)Online publication date: 1-Jun-2020
https://dl.acm.org/doi/10.1007/s10623-020-00729-8
Aggarwal DLi JNguyen PStephens-Davidowitz N(2020)Slide Reduction, Revisited—Filling the Gaps in SVP ApproximationAdvances in Cryptology – CRYPTO 202010.1007/978-3-030-56880-1_10(274-295)Online publication date: 17-Aug-2020
https://dl.acm.org/doi/10.1007/978-3-030-56880-1_10
Aggarwal DStephens-Davidowitz NDiakonikolas IKempe DHenzinger M(2018)(Gap/S)ETH hardness of SVPProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188840(228-238)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188840
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents