Abstract
Quartz is a signature scheme based on an HFEv- trapdoor function published at Eurocrypt 1996. In this paper we study “inversion” attacks for Quartz, i.e. attacks that solve the system of multivariate equations used in Quartz. We do not cover some special attacks that forge signatures without inversion.
We are interested in methods to invert the HFEv- trapdoor function or at least to distinguish it from a random system of the same size. There are 4 types of attacks known on HFE: Shamir-Kipnis [27], Shamir-Kipnis- Courtois [8], Courtois [8], and attacks related to Gröbner bases such as the F5/2 attack by Jean Charles Faugére [15], [16].
No attack has been published so far on HFEv- and it was believed to be more secure than HFE. In this paper we show that even modified HFE systems can be successfully attacked. It seems that the complexity of the attack increases by at least a factor of q tot with tot being the total number of perturbations in HFE. From this and all the other known attacks we will estimate what is the complexity of the best “inversion” attack for Quartz.
The work described in this paper has been partially supported by the French Ministry of Research under RNRT Project “Turbo-signatures”.
Chapter PDF
Similar content being viewed by others
Keywords
References
Boo Barkee, Deh Cac Can, Julia Ecks, Theo Moriarty, R. F. Ree: Why You Cannot Even Hope to use Gröbner Bases in Public Key Cryptography: An Open Letter to a Scientist Who Failed and a Challenge to Those Who Have Not Yet Failed, in Journal of Symbolic Computation 18, 1994, pp. 497–501 341, 343
Dan Boneh, H. Shacham, and B. Lynn: Short signatures from the Weil pairing, Asiacrypt 2001, LNCS 2139, Springer, pp. 514–532. 348
Don Coppersmith, Shmuel Winograd: Matrix multiplication via arithmetic progressions; J. Symbolic Computation (1990), 9, pp. 251–280. 346
David Cox, John Little, Donal O’shea: Ideals, Varieties, and Algorithms, Springer-Verlag, 1992 340, 341
Francisco Corella: A fast implementation of DESan d triple DESon PARISC 2.0. http://www.usenix.org/events/osdi2000/wiess2000/full papers/ corella/corella.pdf347
Nicolas Courtois, Matthieu Finiasz and Nicolas Sendrier: How to achieve a McEliece-based Digital Signature Scheme; Asiacrypt 2001, LNCS2248, Springer, pp. 157–174. Available at http://www.cryptosystem.net/mceliece/. 348
Nicolas Courtois, Adi Shamir, Jacques Patarin, Alexander Klimov, Efficient Algorithms for solving Overdefined Systems of Multivariate Polynomial Equations, in Advances in Cryptology, Eurocrypt’2000, LNCS 1807, Springer-Verlag, pp. 392–407. 340, 344
Nicolas Courtois: The security of Hidden Field Equations (HFE); Cryptographers’ Track RSA Conference 2001, San Francisco 8–12 Avril 2001, LNCS2020, Springer-Verlag, pp. 266–281. 337, 339, 343, 347
Nicolas Courtois: The HFE cryptosystem home page. http://www.hfe.info
Nicolas Courtois: La sécurité des primitives cryptographiques basées sur les problèmes algébriques multivariables MQ, IP, MinRank, et HFE, PhD thesis, Paris 6 University, 2001, in French. Available at http://www.minrank.org/phd.pdf. 339, 340, 341, 343, 345
Nicolas Courtois: Generic Attacks and the Security of Quartz, PKC 2003, in these proceedings. A preliminary version was presented at the second Nessie workshop, Royal Holloway, University of London, September 2001. 338, 341, 345
Magnus Daum, Patrick Felke: Some new aspects concerning the Analysis of HFE type Cryptosystems; Presented at Yet Another Conference on Cryptography (YACC’02), June 3–7, 2002, Porquerolles Island, France. 339, 343
Magnus Daum: Das KryptosystemHFE und quadratische Gleichungssysteme über endlichen Körpern, Diplomarbeit, Universität Dortmund, 2001. Available from http://daum@itsc.ruhr-uni-bochum.de339, 341, 343
Jean-Charles Faugère: A new efficient algorithm for computing Gröbner bases (F4), Journal of Pure and Applied Algebra 139, 1–3 (1999) pp. 61–88. See http://www.elsevier.com/locate/jpaa 341
Jean-Charles Faugère: Computing Gröbner basis without reduction to 0, technical report LIP6, in preparation, source: private communication. Also presented at the Workshop on Applications of Commutative Algebra, Catania, Italy, 3–6 April 2002. 337, 339, 341
Jean-Charles Faugère: Report on a successful attack of HFE Challege 1 with Gröbner bases algorithm F5/2, announcement that appeared in sci. crypt newsgroup on the internet on April 19th 2002. 337, 339, 341, 347
Henri Gilbert, Marine Minier: Cryptanalysis of SFLASH, Eurocrypt 2002, LNCS 2332, pp. 288–298, Springer. 339
G.-M. Greuel, G. Pfister, and H. Schönemann. Singular 2.0.3. A Computer Algebra System for Polynomial Computations. Centre for Computer Algebra, University of Kaiserslautern (2001), http://www.singular.uni-kl.de. 342
Neal Koblitz: “Algebraic Aspects of Cryptography”; Springer-Verlag, ACM3, 1998, Chapter 4: “Hidden Monomial Cryptosystems”, pp. 80–102. 348
Tsutomu Matsumoto, Hideki Imai: “Public Quadratic Polynomial-tuples for efficient signature-verification and message-encryption”, Eurocrypt’88, Springer-Verlag 1998, pp. 419–453. 337
Jacques Patarin: “Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt’88”; Crypto’95, Springer-Verlag, pp. 248–261. 337, 345
Jacques Patarin: “Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of Asymmetric Algorithms”; Eurocrypt’96, Springer Verlag, pp. 33–48. The extended version can be found at http://www.minrank.org/hfe.ps 337, 341, 347
Jacques Patarin: La CryptographieMultivariable; Mémoire d'habilitation à diriger des recherches de l’Université Paris 7, 1999. 348
Jacques Patarin, Nicolas Courtois, Louis Goubin: “C*-+ and HM-Variations around two schemes of T. Matsumoto and H. Imai”; Asiacrypt 1998, Springer-Verlag, pp. 35–49. 339
Jacques Patarin, Louis Goubin, Nicolas Courtois: Quartz, 128-bit long digital signatures; Cryptographers’ Track Rsa Conference 2001, San Francisco 8–12 April 2001, LNCS2020, Springer-Verlag.
Jacques Patarin, Louis Goubin, Nicolas Courtois: Quartz, 128-bit long digital signatures; An updated version of Quartz specification available at http://www.cryptosystem.net/quartz/ 338, 341, 343, 345, 348, 350
Adi Shamir, Aviad Kipnis: “Cryptanalysis of the HFE Public Key Cryptosystem”; Crypto’99. Can be found at http://www.minrank.org/hfesubreg.ps 337, 338, 343
Volker Strassen: Gaussian Elimination is Not Optimal; Numerische Mathematik, vol 13, pp 354–356, 1969. 346
Nicolas Courtois, Magnus Daum and Patrick Felke: On the Security of HFE, HFEv-and Quartz; Cryptology ePrint Archive, Report 2002/138. Available at http://eprint.iacr.org. 342, 343, 344, 347
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Courtois, N.T., Daum, M., Felke, P. (2003). On the Security of HFE, HFEv- and Quartz. In: Desmedt, Y.G. (eds) Public Key Cryptography — PKC 2003. PKC 2003. Lecture Notes in Computer Science, vol 2567. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36288-6_25
Download citation
DOI: https://doi.org/10.1007/3-540-36288-6_25
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00324-3
Online ISBN: 978-3-540-36288-3
eBook Packages: Springer Book Archive