Skip to main content
SpringerLink
Log in

A Variant of the F4 Algorithm

  • Conference paper
Topics in Cryptology – CT-RSA 2011 (CT-RSA 2011)

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

Included in the following conference series:

Abstract

Algebraic cryptanalysis usually requires to find solutions of several similar polynomial systems. A standard tool to solve this problem consists of computing the Gröbner bases of the corresponding ideals, and Faugère’s F4 and F5 are two well-known algorithms for this task. In this paper, we adapt the “Gröbner trace” method of Traverso to the context of F4. The resulting variant is a heuristic algorithm, well suited to algebraic attacks of cryptosystems since it is designed to compute with high probability Gröbner bases of a set of polynomial systems having the same shape. It is faster than F4 as it avoids all reductions to zero, but preserves its simplicity and its efficiency, thus competing with F5.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Augot, D., Bardet, M., Faugère, J.-C.: On the decoding of binary cyclic codes with the Newton identities. J. Symbolic Comput. 44(12), 1608–1625 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bard, G.: Algebraic Cryptanalysis, 1st edn. Springer, New York (2009)

    Book  MATH  Google Scholar 

  3. Bardet, M., Faugère, J.-C., Salvy, B., Yang, B.-Y.: Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems. Presented at MEGA 2005, Eighth International Symposium on Effective Methods in Algebraic Geometry (2005)

    Google Scholar 

  4. Bettale, L., Faugère, J.-C., Perret, L.: Hybrid approach for solving multivariate systems over finite fields. Journal of Mathematical Cryptology, 177–197 (2009)

    Google Scholar 

  5. Bosma, W., Cannon, J.J., Playoust, C.: The Magma algebra system I: The user language. J. Symb. Comput. 24(3/4), 235–265 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  6. Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, University of Innsbruck, Austria (1965)

    Google Scholar 

  7. Buchberger, B.: A criterion for detecting unnecessary reductions in the construction of Gröbner bases. In: Ng, K.W. (ed.) EUROSAM 1979 and ISSAC 1979. LNCS, vol. 72, pp. 3–21. Springer, Heidelberg (1979)

    Chapter  Google Scholar 

  8. Buchberger, B.: Gröbner bases: An algorithmic method in polynomial ideal theory. In: Bose, N. (ed.) Multidimensional systems theory, Progress, directions and open problems, Math. Appl., vol. 16, pp. 184–232. D. Reidel Publ. Co., Dordrecht (1985)

    Google Scholar 

  9. Courtois, N.: Efficient zero-knowledge authentication based on a linear algebra problem MinRank. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 402–421. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  10. 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 

  11. Diem, C.: On the discrete logarithm problem in elliptic curves. Preprint (2009), http://www.math.uni-leipzig.de/~diem/preprints/dlp-ell-curves.pdf

  12. Ebert, G.L.: Some comments on the modular approach to Gröbner-bases. SIGSAM Bull. 17(2), 28–32 (1983)

    Article  MATH  Google Scholar 

  13. Eder, C., Perry, J.: F5C: a variant of Faugère’s F5 algorithm with reduced Gröbner bases arXiv/0906.2967 (2009)

    Google Scholar 

  14. Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra 139(1-3), 61–88 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  15. Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In: Proceedings of ISSAC 2002. ACM, New York (2002)

    Google Scholar 

  16. 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 

  17. Faugère, J.-C., Levy-dit-Vehel, F., Perret, L.: Cryptanalysis of MinRank. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 280–296. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  18. Gaudry, P.: Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem. J. Symbolic Computation (2008), doi:10.1016/j.jsc.2008.08.005

    Google Scholar 

  19. Gebauer, R., Möller, H.M.: On an installation of Buchberger’s algorithm. J. Symbolic Comput. 6(2-3), 275–286 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  20. Joux, A., Vitse, V.: Elliptic curve discrete logarithm problem over small degree extension fields. Application to the static Diffie–Hellman problem on \({E}(\mathbb{F}_{q^5})\). Cryptology ePrint Archive, Report 2010/157 (2010)

    Google Scholar 

  21. Katsura, S., Fukuda, W., Inawashiro, S., Fujiki, N.M., Gebauer, R.: Distribution of effective field in the Ising spin glass of the ±J model at T= 0. Cell Biochem. Biophys. 11(1), 309–319 (1987)

    Google Scholar 

  22. Kipnis, A., Patarin, J., Goubin, L.: Unbalanced oil and vinegar signature schemes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 206–222. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  23. 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)

    Chapter  Google Scholar 

  24. Lazard, D.: Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations. In: van Hulzen, J.A. (ed.) ISSAC 1983 and EUROCAL 1983. LNCS, vol. 162, pp. 146–156. Springer, Heidelberg (1983)

    Chapter  Google Scholar 

  25. Macaulay, F.: Some formulae in elimination. In: Proceedings of London Mathematical Society, pp. 3–38 (1902)

    Google Scholar 

  26. Mohamed, M.S.E., Mohamed, W.S.A.E., Ding, J., Buchmann, J.: MXL2: Solving polynomial equations over GF(2) using an improved mutant strategy. In: Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol. 5299, pp. 203–215. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  27. Sasaki, T., Takeshima, T.: A modular method for Gröbner-basis construction over ℚ and solving system of algebraic equations. J. Inf. Process. 12(4), 371–379 (1989)

    MATH  Google Scholar 

  28. Semaev, I.: Summation polynomials and the discrete logarithm problem on elliptic curves. Cryptology ePrint Archive, Report 2004/031 (2004)

    Google Scholar 

  29. Traverso, C.: Gröbner trace algorithms. In: Gianni, P. (ed.) ISSAC 1988. LNCS, vol. 358, pp. 125–138. Springer, Heidelberg (1989)

    Chapter  Google Scholar 

  30. Weispfenning, V.: Comprehensive Gröbner bases. J. Symbolic Comput. 14(1), 1–29 (1992)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Direction Générale de l’Armement (DGA), France

    Antoine Joux

  2. Laboratoire PRISM, Université de Versailles Saint-Quentin, 45 av. des États-Unis, 78035, Versailles cedex, France

    Antoine Joux & Vanessa Vitse

Authors
  1. Antoine Joux
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Vanessa Vitse
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Informatics and Telecommunications, National and Kapodistrian University of Athen, Panepistimiopolis Ilisia, 15784, Athens, Greece

    Aggelos Kiayias

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Joux, A., Vitse, V. (2011). A Variant of the F4 Algorithm. In: Kiayias, A. (eds) Topics in Cryptology – CT-RSA 2011. CT-RSA 2011. Lecture Notes in Computer Science, vol 6558. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19074-2_23

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-19074-2_23

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-19073-5

  • Online ISBN: 978-3-642-19074-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation