User menu

Polynomial equivalence problems: Algorithmic and theoretical aspects

Bibliographic reference Faugere, Jean-Charles ; Perret, Ludovic. Polynomial equivalence problems: Algorithmic and theoretical aspects.24th Annual International Conference on Theory and Applications of Cryptographic Techniques (St Petersburg(Russia), May 28-jun 01, 2006). In: Lecture Notes in Computer Science, Vol. 4004, p. 30-47 (2006)
Permanent URL
  1. Adams, W.W., Loustaunau, P.: An Introduction to Gröbner Bases, vol. 3. AMS. Graduate Studies in Mathematics 3 (1994)
  2. Ars Gwénolé, Faugère Jean-Charles, Imai Hideki, Kawazoe Mitsuru, Sugita Makoto, Comparison Between XL and Gröbner Basis Algorithms, Advances in Cryptology - ASIACRYPT 2004 (2004) ISBN:9783540239758 p.338-353, 10.1007/978-3-540-30539-2_24
  3. Bardet, M., Faugère, J.-C., Salvy, B., Yang, B.-Y.: Asymptotic Behaviour of the Degree of Regularity of Semi-Regular Polynomial Systems. In: MEGA 2005, Eighth International Symposium on Effective Methods in Algebraic Geometry, 15 pages (2005)
  4. Bardet, M., Faugère, J.-C., Salvy, B.: On the Complexity of Gröbner Basis Computation of Semi-Regular Overdetermined Algebraic Equations. In: Proc. of International Conference on Polynomial System Solving (ICPSS), pp. 71–75 (2004)
  5. Billet Olivier, Gilbert Henri, A Traceable Block Cipher, Advances in Cryptology - ASIACRYPT 2003 (2003) ISBN:9783540205920 p.331-346, 10.1007/978-3-540-40061-5_21
  6. Biryukov Alex, De Cannière Christophe, Braeken An, Preneel Bart, A Toolbox for Cryptanalysis: Linear and Affine Equivalence Algorithms, Lecture Notes in Computer Science (2003) ISBN:9783540140399 p.33-50, 10.1007/3-540-39200-9_3
  7. Boppana Ravi B., Hastad Johan, Zachos Stathis, Does co-NP have short interactive proofs?, 10.1016/0020-0190(87)90232-8
  8. Buchberger, B.: Gröbner Bases: an Algorithmic Method in Polynomial Ideal Theory. Recent trends in multidimensional systems theory, Reider ed. Bose (1985)
  9. Buchberger, B., Collins, G.-E., Loos, R.: Computer Algebra Symbolic and Algebraic Computation, 2nd edn. Springer, Heidelberg (1982)
  10. Courtois, N.: La sécurité des primitives cryptographiques basées sur des problèmes algébriques multivariables: MQ, IP, MinRank, HFE. Ph.D. Thesis, Paris (2001)
  11. Patarin Jacques, Goubin Louis, Courtois Nicolas, Improved algorithms for isomorphisms of polynomials, Lecture Notes in Computer Science (1998) ISBN:9783540645184 p.184-200, 10.1007/bfb0054126
  12. Courtois, N., Goubin, L., Patarin, J.: Improved Algorithms for Isomorphism of Polynomials - (extended Version), available from:
  13. Courtois, N., Goubin, L., Patarin, J.: SFLASH, a Fast Asymmetric Signature Scheme for low-cost Smartcards – Primitive Specification and Supporting Documentation, available at:
  14. Courtois Nicolas, Klimov Alexander, Patarin Jacques, Shamir Adi, Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations, Advances in Cryptology — EUROCRYPT 2000 (2000) ISBN:9783540675174 p.392-407, 10.1007/3-540-45539-6_27
  15. Cox David, Little John, O’Shea Donal, Ideals, Varieties, and Algorithms, ISBN:9781475721836, 10.1007/978-1-4757-2181-2
  16. Faugére Jean-Charles, A new efficient algorithm for computing Gröbner bases (F4), 10.1016/s0022-4049(99)00005-5
  17. Faugère, J.-C.: A New Efficient Algorithm for Computing Gröbner Basis without Reduction to Zero: F5. In: Proceedings of ISSAC, pp. 75–83. ACM press, New York (2002)
  18. Faugère Jean-Charles, Joux Antoine, Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases, Advances in Cryptology - CRYPTO 2003 (2003) ISBN:9783540406747 p.44-60, 10.1007/978-3-540-45146-4_3
  19. Faugère J.C., Gianni P., Lazard D., Mora T., Efficient Computation of Zero-dimensional Gröbner Bases by Change of Ordering, 10.1006/jsco.1993.1051
  20. Felke Patrick, On the Affine Transformations of HFE-Cryptosystems and Systems with Branches, Coding and Cryptography (2006) ISBN:9783540354819 p.229-241, 10.1007/11779360_19
  21. Fortin, S.: The Graph Isomorphism problem. Technical Report 96-20, University of Alberta (1996)
  22. Garey, M.R., Johnson, D.B.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)
  23. Geiselmann Willi, Steinwandt Rainer, Beth Thomas, Attacking the Affine Parts of SFLASH, Cryptography and Coding (2001) ISBN:9783540430261 p.355-359, 10.1007/3-540-45325-3_31
  24. Group-Theoretic Algorithms and Graph Isomorphism, ISBN:9783540114932, 10.1007/3-540-11493-9
  26. Matsumoto Tsutomu, Imai Hideki, Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption, Lecture Notes in Computer Science ISBN:9783540502517 p.419-453, 10.1007/3-540-45961-8_39
  28. Patarin Jacques, Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms, Advances in Cryptology — EUROCRYPT ’96 (1996) ISBN:9783540611868 p.33-48, 10.1007/3-540-68339-9_4
  29. Patarin, J.: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of Asymmetric Algorithms – (extended Version), available from:
  30. Patarin Jacques, Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt’88, Advances in Cryptology — CRYPT0’ 95 (1995) ISBN:9783540602217 p.248-261, 10.1007/3-540-44750-4_20