[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Studying lattice reduction algorithms improved by quick reordering technique

  • regular contribution
  • Published:
International Journal of Information Security Aims and scope Submit manuscript

Abstract

Under the threat of quantum computers’ expected powerful computational capacity, the study on post-quantum cryptography is becoming urgent nowadays. Lattice-based cryptography is one of the most promising candidates of post-quantum cryptography. To give a secure instantiation for practical applications, it is necessary to understand the complexity of the best-known attacks. Most of the attacks to lattice-based cryptography use basis reduction algorithms. For instance, the most commonly used practical basis reduction algorithms are variants of the block Korkin–Zolotarev (BKZ) algorithm. In this paper, we study the effect of applying the quick reordering technique (QRT) to lattice algorithms, mainly the enumeration algorithm and the BKZ algorithm. We show that QRT is a simple method to improve these two algorithms with respect to cutting down the number of search nodes and thus reducing the total runtime. For improving on the LLL algorithm with dimensions smaller than 30, the success rate is larger than 10%, and for the BKZ algorithm with blocksize smaller than 30, the success rate is larger than 40%. At first, we observe that reordering the LLL-reduced basis vectors by increasing norm orders will change the distribution of search nodes in the enumeration tree, which gives a chance to reduce the enumeration search nodes with a certain probability. The experimental results show that the runtime of the enumeration algorithm can be accelerated approximately by a factor of two. We further explain this phenomenon from a theoretical point of view, which follows Gama–Nguyen–Regev’s analysis (Gama et al., in: Advances in cryptology—EUROCRYPT 2010, proceedings of 29th annual international conference on the theory and applications of cryptographic techniques, pp 257–278, 2010). Then we apply this reordering technique to the implementation of the BKZ algorithm in the open-source library NTL. Our experimental results in dimensions 100–120 with blocksize 15–30 show that on the LLL-reduced bases, our modified NTL-BKZ outputs a vector shorter than the original NTL-BKZ with rate 40.91%-45.73% by setting the LLL approximation factor by \(\delta _{LLL}=0.99\). Furthermore, in the instances where the improved BKZ found one same or shorter vector, the runtime is up to 2.02 times faster than the original NTL-BKZ when setting the blocksize \(\beta =25\) with \(\delta _{LLL}=0.99\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, pp. 601–610 (2001)

  2. Albrecht, M.R., Ducas, L., Herold, G., Kirshanova, E., Postlethwaite, E. W., Stevens, M.: The general sieve kernel and new records in lattice reduction. In: Advances in Cryptology—EUROCRYPT 2019—38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part II, pp. 717–746 (2019)

  3. Aono, Y.: A faster method for computing Gama–Nguyen–Regev’s extreme pruning coefficients. CoRR, arXiv:1406.0342 (2014)

  4. Aono, Y., Nguyen, P.Q.: Random sampling revisited: Lattice enumeration with discrete pruning. In: Advances in Cryptology—EUROCRYPT 2017—36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part II, pp. 65–102 (2017)

  5. Aono, Y., Nguyen, P.Q., Seito, T., Shikata, J.: Lower bounds on lattice enumeration with extreme pruning. In: Advances in Cryptology—- CRYPTO 2018—38th Annual International Cryptology Conference, Proceedings, Part II, pp. 608–637 (2018)

  6. Aono, Y., Wang, Y., Hayashi, T., Takagi, T.: Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator. In: Advances in Cryptology—EUROCRYPT 2016—35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part I, pp. 789–819 (2016)

  7. Bai, S., Stehlé, D., Wen, W.: Measuring, simulating and exploiting the head concavity phenomenon in BKZ. In: Advances in Cryptology—ASIACRYPT 2018—- 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part I, pp. 369–404 (2018)

  8. Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, vol. 2016, pp. 10–24 (2016)

  9. Chen, Y., Nguyen, P.Q.: Bkz 2.0: better lattice security estimates. In: Advances in Cryptology—ASIACRYPT 2011: 17th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, pp. 1–20 (2011)

  10. N.I.o.S. Computer Security Division, Information Technology Laboratory and U. D. o. C. Technology. Post-quantum cryptography | csrc, (2017)

  11. Darmstadt, T.: Svp challenge (2017). https://www.latticechallenge.org/svp-challenge

  12. T. F. development team. fplll, a lattice reduction library (2017). https://github.com/fplll/fplll

  13. Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comput. 44(170), 463–471 (1985)

    Article  MathSciNet  Google Scholar 

  14. Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Advances in Cryptology—EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, pp. 31–51 (2008)

  15. Gama, N., Nguyen, P.Q., Regev, O.: Lattice enumeration using extreme pruning. In: Advances in Cryptology—EUROCRYPT 2010, Proceedings of 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 257–278 (2010)

  16. Hoare, C.A.R.: Quicksort. Comput. J. 5(1), 10–16 (1962)

    Article  MathSciNet  Google Scholar 

  17. Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Algorithmic Number Theory, Third International Symposium, ANTS-III, Proceedings, pp. 267–288 (1998)

  18. Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pp. 193–206 (1983)

  19. Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48(177), 203–209 (1987)

    Article  MathSciNet  Google Scholar 

  20. Korkine, A., Zolotareff, G.: Sur les forms quadratiques. Math. Ann. 6, 581–583 (1873)

    Article  Google Scholar 

  21. Lagrange, L.: Recherches d’arithmétique. Nouv. Mém. Acad. (1773)

  22. Lenstra, A., Lenstra, H., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515–534 (1982)

    Article  MathSciNet  Google Scholar 

  23. Micciancio, D., Voulgaris, P.: Faster exponential time algorithms for the shortest vector problem. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, vol. 2010, pp. 1468–1480 (2010)

  24. Miller, V.S.: Use of elliptic curves in cryptography. In: Advances in Cryptology—CRYPTO’85, Proceedings, pp. 417–426 (1985)

  25. Nguyen, P.Q., Stehlé, D.: Floating-point LLL revisited. In: Advances in Cryptology—EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, pp. 215–233 (2005)

  26. Nguyen, P.Q., Stehlé, D.: LLL on the average. In: Algorithmic Number Theory, 7th International Symposium, ANTS-VII, Proceedings, pp. 238–256 (2006)

  27. Nguyen, P.Q., Vidick, T.: Sieve algorithms for the shortest vector problem are practical. J. Math. Cryptol. 2(2), 181–207 (2008)

    Article  MathSciNet  Google Scholar 

  28. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 84–93 (2005)

  29. Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)

    Article  MathSciNet  Google Scholar 

  30. Schnorr, C.: A more efficient algorithm for lattice basis reduction. J. Algorithms 9(1), 47–62 (1988)

    Article  MathSciNet  Google Scholar 

  31. Schnorr, C.: Lattice reduction by random sampling and birthday methods. In: STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings, pp. 145–156 (2003)

  32. Schnorr, C., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66, 181–199 (1994)

    Article  MathSciNet  Google Scholar 

  33. Schnorr, C., Hörner, H.H.: Attacking the chor-rivest cryptosystem by improved lattice reduction. In: Advances in Cryptology—EUROCRYPT’95, International Conference on the Theory and Application of Cryptographic Techniques, Saint-Malo, France, May 21–25, 1995, Proceeding, pp. 1–12 (1995)

  34. Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124–134 (1994)

  35. Shoup, V.: NTL, a library for doing number theory (2017). http://www.shoup.net/ntl/

  36. Skiena, S.: The Algorithm Design Manual, 2nd edn. Springer, Berlin (2008)

    Book  Google Scholar 

  37. Wang, Y., Takagi, T.: Improving the BKZ reduction algorithm by quick reordering technique. In: Information Security and Privacy—23rd Australasian Conference, ACISP 2018, Proceedings, pp. 787–795 (2018)

  38. Yamaguchi, J., Yasuda, M.: Explicit formula for gram-Schmidt vectors in LLL with deep insertions and its applications. In: Number-Theoretic Methods in Cryptology-First International Conference, 2017, Revised Selected Papers, pp. 142–160 (2017)

Download references

Funding

This study was funded by JSPS KAKENHI Grant Number JP17J01987 and JST CREST Grant Number JPMJCR14D6, Japan.

Author information

Authors and Affiliations

  1. School of Information Science, Security and Networks, Japan Advanced Institute of Science and Technology, Ishikawa, Japan

    Yuntao Wang

  2. CREST, Japan Science and Technology Agency, Kawaguchi, Japan

    Yuntao Wang & Tsuyoshi Takagi

  3. Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, Japan

    Tsuyoshi Takagi

Authors
  1. Yuntao Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tsuyoshi Takagi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yuntao Wang.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Ethical approval

This article does not contain any studies with human participants or animals performed by any of the authors.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendices

Comparison of applying QRT with increasing order and decreasing order

See Fig. 4.

Fig. 4
figure 4

By applying the increasing QRT and the decreasing QRT, respectively, in “LLL (\(\delta _{LLL}\in \{0.85,0.90,0.95,0.99\}\)) then SE-ENUM” model, the probabilities of GSO vectors becoming convex are the upper filled dots with lines, and the probabilities of reducing SE-ENUM cost successfully are the lower hollow squares

Full size image
Table 4 Success rate of QRT (increasing and decreasing, respectively), reducing SE-ENUM search nodes successfully in “LLL (\(\delta _{LLL}=0.90\)) then SE-ENUM” model
Full size table
Table 5 Success probability \(p_{succLen}\) of QRT-BKZ finding a shorter vector than NTL-BKZ with \(\beta \in \{15,20,25,30\}\) and \(\delta _{LLL}=0.90 \)
Full size table
Table 6 Success probability \(p_{succLen}\) of QRT-BKZ finding a shorter vector than NTL-BKZ with \(\beta \in \{15,20,25,30\}\) and \(\delta _{LLL}=0.95 \)
Full size table
Table 7 Success probability \(p_{succLen}\) of QRT-BKZ finding a shorter vector than NTL-BKZ with \(\beta \in \{15,20,25,30\}\) and \(\delta _{LLL}=0.99\)
Full size table

The success probability of QRT-BKZ from dimension 100 to 120.

See Tables 4, 5, 6 and 7.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Wang, Y., Takagi, T. Studying lattice reduction algorithms improved by quick reordering technique. Int. J. Inf. Secur. 20, 257–268 (2021). https://doi.org/10.1007/s10207-020-00501-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10207-020-00501-y

Keywords

Search

Navigation