[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

All in the XL Family: Theory and Practice

  • Conference paper
Information Security and Cryptology – ICISC 2004 (ICISC 2004)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 3506))

Included in the following conference series:

Abstract

The XL (eXtended Linearization) equation-solving algorithm belongs to the same extended family as the advanced Gröbner Bases methods F 4 /F 5 . XL and its relatives may be used as direct attacks against multivariate Public-Key Cryptosystems and as final stages for many “algebraic cryptanalysis” used today. We analyze the applicability and performance of XL and its relatives, particularly for generic systems of equations over medium-sized finite fields.

In examining the extended family of Gröbner Bases and XL from theoretical, empirical and practical viewpoints, we add to the general understanding of equation-solving. Moreover, we give rigorous conditions for the successful termination of XL, Gröbner Bases methods and relatives. Thus we have a better grasp of how such algebraic attacks should be applied. We also compute revised security estimates for multivariate cryptosystems. For example, the schemes SFLASHv2 and HFE Challenge 2 are shown to be unbroken by XL variants.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Akkar, M., Courtois, N., Duteuil, R., Goubin, L.: A Fast and Secure Implementation of SFLASH. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 267–278. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  2. Ars, G., Faugère, J.-C., Imai, H., Kawazoe, M., Sugita, M.: Comparison of XL and Gröbner Bases Algorithms over Finite Fields. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 338–353. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  3. Bardet, M.: Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie. Ph.D. thesis, Université Paris 6 (2004)

    Google Scholar 

  4. Bardet, M., Faugère, J.-C., Salvy, B.: Complexity of Gröbner Basis Computations for Regular Overdetermined Systems, INRIA Rapport de Recherche No. 5049; a slightly modified preprint is accepted by the International Conference on Polynomial System Solving

    Google Scholar 

  5. Bardet, M., Faugère, J.-C., Salvy, B., Yang, B.-Y.: Asymptotic Complexity of Gröbner Basis Algorithms for Semi-regular Overdetermined Systems over Large Fields (manuscript)

    Google Scholar 

  6. Barkee, B., et al.: Why You Cannot Even Hope to Use Gröbner Bases in Public-Key Cryptography. J. Symbolic Computations 18, 497–501 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  7. Bunch, J.R., Hopcroft, J.E.: Triangular Factorizations and Inversion by Fast Matrix Multiplication. Math. Computations 24, 231–236 (1974)

    Article  MathSciNet  Google Scholar 

  8. Burden, R., Faires, J.D.: Numerical Analysis, 7th edn. PWS-Kent Publ. Co. (2000)

    Google Scholar 

  9. Bernstein, D.: Matrix Inversion Made Difficult, preprint, stated to be superseded by a yet unpublished version, available at http://cr.yp.to

  10. Caniglia, L., Galligo, A., Heintz, J.: Some New Effectivity Bounds in Computational Geometry. In: Mora, T. (ed.) AAECC 1988. LNCS, vol. 357, pp. 131–151. Springer, Heidelberg (1989)

    Google Scholar 

  11. Caniglia, L., Galligo, A., Heintz, J.: Equations for the Projective Closure and Effective Nullstellensatz. Discrete Applied Mathematics 33, 11–23 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  12. Chester, C., Friedman, B., Ursell, F.: An Extension of the Method of Steepest Descents. Proc. Camb. Philo. Soc. 53, 599–611 (1957)

    Article  MATH  MathSciNet  Google Scholar 

  13. Coppersmith, D.: Private communication

    Google Scholar 

  14. Courtois, N.: The Security of Hidden Field Equations (HFE). In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 266–281. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  15. Courtois, N.: Higher-Order Correlation Attacks, XL Algorithm and Cryptanalysis of Toyocrypt. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 182–199. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  16. Courtois, N.T.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 177–194. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  17. Courtois, N.: Algebraic attacks over gF(2k), application to HFE challenge 2 and sflash-v2. In: Bao, F., Deng, R., Zhou, J. (eds.) PKC 2004. LNCS, vol. 2947, pp. 201–217. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  18. Courtois, N.: Private communication

    Google Scholar 

  19. Courtois, N., Goubin, L., Patarin, J.: SFLASHv3, a Fast Asymmetric Signature Scheme, preprint, available at http://eprint.iacr.org/2003/211

  20. Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  21. Courtois, N.T., Pieprzyk, J.: Cryptanalysis of block ciphers with overdefined systems of equations. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 267–287. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  22. Courtois, N.T., Patarin, J.: About the XL algorithm over GF(2). In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 141–157. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  23. Daemen, J., Rijmen, V.: The Design of Rijndael, AES - The Advanced Encryption Standard. Springer, Heidelberg (2002)

    Google Scholar 

  24. Diem, C.: The XL-algorithm and a conjecture from commutative algebra. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 323–337. Springer, Heidelberg (2004) private communication

    Chapter  Google Scholar 

  25. Diffie, W., Hellman, M.: New Directions in Cryptography. IEEE Trans. Info. Theory IT-22(6), 644–654 (1972)

    MathSciNet  Google Scholar 

  26. Ding, J., Schmidt, D.: Cryptanalysis of SFlashv3, eprint.iacr.org/2004/103

  27. Duff, I.S., Erismann, A.M., Reid, J.K.: Direct Methods for Sparse Matrices, published by Oxford Science Publications (1986)

    Google Scholar 

  28. Eberly, W., Kaltofen, E.: On Randomized Lanczos Algorithms. In: Proc. ISSAC 1997, pp. 176–183. ACM Press, New York (1997)

    Chapter  Google Scholar 

  29. Faugére, J.-C.: A New Efficient Algorithm for Computing Gröbner Bases (F4). Journal of Pure and Applied Algebra 139, 61–88 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  30. Faugère, J.-C.: A New Efficient Algorithm for Computing Gröbner Bases without Reduction to Zero (F5). In: Proceedings of ISSAC 2002, pp. 75–83. ACM Press, New York (2002)

    Chapter  Google Scholar 

  31. Faugère, J.-C., Joux, A.: Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using gröbner bases. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 44–60. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  32. Fröberg, R.: An Inequality for Hilbert Series of Graded Algebras. Math. Scand. 56, 117–144 (1985)

    MATH  MathSciNet  Google Scholar 

  33. Garey, M., Johnson, D.: Computers and Intractability, A Guide to the Theory of NP-completeness. W.H. Freeman, New York (1979)

    MATH  Google Scholar 

  34. Geiselmann, W., Steinwandt, R., Beth, T.: Revealing 441 Key Bits of sflashv2. In: 3rd NESSIE Workshop (2002)

    Google Scholar 

  35. Hwang, H.-K.: Asymptotic estimates of elementary probability distributions. Studies in Applied Mathematics 99(4), 393–417 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  36. Hartshorne, R.: Algebraic Geometry. Springer, Heidelberg (1977)

    MATH  Google Scholar 

  37. Kipnis, A., Shamir, A.: Cryptanalysis of the HFE public key cryptosystem by relinearization. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 19–30. Springer, Heidelberg (1999)

    Google Scholar 

  38. LaMacchia, B., Odlyzko, A.: Solving large sparse linear systems over finite fields. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 109–133. Springer, Heidelberg (1991)

    Google Scholar 

  39. Lang, S.: Algebra, 3rd edn. Addison-Wesley, Reading (1993)

    MATH  Google Scholar 

  40. Lazard, D.: Gröbner Bases, Gaussian Elimination and Resolution of Systems of Algebraic Equations. In: van Hulzen, J.A. (ed.) EUROCAL 1983. LNCS, vol. 162, pp. 146–156. Springer, Heidelberg (1983)

    Google Scholar 

  41. McGeoch, C.: “Veni, Divisi, Vici”. Appearing in the “Computer Science Sampler” column of the Amer. Math. Monthly (May 1995)

    Google Scholar 

  42. The MAGMA project, University of Sydney, see http://magma.maths.usyd.edu.au/users/allan/gb

  43. Matsumoto, T., Imai, H.: Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 419–453. Springer, Heidelberg (1988)

    Google Scholar 

  44. Moh, T.: On The Method of XL and Its Inefficiency Against TTM, available at http://eprint.iacr.org/2001/047

  45. Murphy, S., Robshaw, M.: Essential algebraic structure within the AES. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 1–16. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  46. Murphy, S., Robshaw, M.: Comments on the Security of the AES and the XSL Technique, preprint available from the authors, http://www.isg.rhul.ac.uk/~sean/

  47. NESSIE Security Report, V2.0, available at http://www.cryptonessie.org

  48. Patarin, J.: Hidden fields equations (HFE) and isomorphisms of polynomials (IP): Two new families of asymmetric algorithms. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996)

    Google Scholar 

  49. Patarin, J., Goubin, L., Courtois, N.T.: \(C^{*}_{-+}\) and HM: Variations around two schemes of T. Matsumoto and H. Imai. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 35–50. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  50. Patarin, J., Courtois, N., Goubin, L.: QUARTZ, 128-bit long digital signatures. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 282–297. Springer, Heidelberg (2001) Update at http://www.cryptonessie.org

    Chapter  Google Scholar 

  51. Patarin, J., Courtois, N., Goubin, L.: FLASH, a fast multivariate signature algorithm. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 298–307. Springer, Heidelberg (2001), Update with SFLASHv2 available at http://www.cryptonessie.org

    Chapter  Google Scholar 

  52. Stanley, R.: Enumerative Combinatorics, vol. 1, second printing (1996); vol. 2 in (1999) Both published by Cambridge University Press, Cambridge

    Google Scholar 

  53. Strassen, V.: Gaussian Elimination is not Optimal. Numer. Math. 13, 354–356 (1969)

    Article  MATH  MathSciNet  Google Scholar 

  54. Sugita, M., Kawazoe, M., Imai, H.: Relation between XL algorithm and Groebner Bases Algorithms, preprint, http://eprint.iacr.org/2004/112 Part of this merged with [2]

  55. Szegö, G.: Orthogonal Polynomials, 4th edn. American Math. Society, Providence

    Google Scholar 

  56. Wiedemann, D.: Solving Sparse Linear Equations over Finite Fields. IEEE Transaction on Information Theory IT-32(1), 54–62 (1976)

    MathSciNet  Google Scholar 

  57. Wong, R.: Asymptotic Approximations of Integrals. Academic Press, San Diego (1989)

    MATH  Google Scholar 

  58. Yang, B.-Y., Chen, J.-M.: Theoretical analysis of XL over small fields. In: Wang, H., Pieprzyk, J., Varadharajan, V. (eds.) ACISP 2004. LNCS, vol. 3108, pp. 277–288. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  59. Yang, B.-Y., Chen, J.-M., Courtois, N.T.: On asymptotic security estimates in XL and gröbner bases-related algebraic cryptanalysis. In: López, J., Qing, S., Okamoto, E. (eds.) ICICS 2004. LNCS, vol. 3269, pp. 401–413. Springer, Heidelberg (2004) Formerly titled Exact and Asymptotic Behavior of XL-Related Methods

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Tamkang University, Tamsui, Taiwan

    Bo-Yin Yang

  2. Chinese Data Security, Inc., & National, Taiwan U

    Jiun-Ming Chen

Authors
  1. Bo-Yin Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jiun-Ming Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. National Security Research Institute, 305-348, Daejeon, Korea

    Choon-sik Park

  2. National Security Research Institute (NSRI), 161 Gajeong-dong, Yuseong-gu, 305-350, Daejeon, Korea

    Seongtaek Chee

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Yang, BY., Chen, JM. (2005). All in the XL Family: Theory and Practice. In: Park, Cs., Chee, S. (eds) Information Security and Cryptology – ICISC 2004. ICISC 2004. Lecture Notes in Computer Science, vol 3506. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11496618_7

Download citation

  • DOI: https://doi.org/10.1007/11496618_7

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-26226-8

  • Online ISBN: 978-3-540-32083-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics