Generic Attacks and the Security of Quartz

  • Nicolas T. Courtois
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2567)


The signature scheme Quartz is based on a trapdoor function G belonging to a family called HFEv-. It has two independent security parameters, and we claim that if d is big enough, no better method to compute an inverse of G than the exhaustive search is known. Such a (quite strong) assumption, allows to view Quartz as a general construction, that transforms a trapdoor function into a short signature scheme. The main object of this paper is the concrete security of this construction. On one hand, we present generic attacks on such schemes. On the other hand, we study the possibility to prove or justify the security with some well chosen assumptions. Unfortunately for Quartz, our lower and upper security bounds do not coincide. Still the best attack known for Quartz is our generic attack using O(280) computations with O(280) of memory. We will also propose an alternative way of doing short signatures for which both bounds do coincide.


Asymmetric cryptography finite fields Hidden Field Equations (HFE) MQ HFEv- short signatures Quartz Flash Sflash Nessie 


  1. [1]
    Dan Boneh, H. Shacham, and B. Lynn: Short signatures from the Weil pairing, Asiacrypt 2001, LNCS 2139, Springer, pp. 514–532. 351Google Scholar
  2. [2]
    Nicolas Courtois: The security of Hidden Field Equations (HFE); Cryptographers’ Track Rsa Conf. 2001, LNCS2020, Springer-Verlag, pp. 266–281.Google Scholar
  3. [3]
    N. Courtois, L. Goubin, W. Meier, J.-D. Tacier: Solving Underdefined Systems of Multivariate Quadratic Equations; PKC 2002, LNCS 2274, Springer, pp. 211–227.Google Scholar
  4. [4]
    Nicolas Courtois, Matthieu Finiasz and Nicolas Sendrier: How to achieve a McEliece-based Digital Signature Scheme; Asiacrypt 2001, LNCS2248, Springer, pp. 157–174. 351Google Scholar
  5. [5]
    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. 355Google Scholar
  6. [6]
    Michael Garey, David Johnson: Computers and Intractability, a guide to the theory of NP-completeness, Freeman, p. 251.Google Scholar
  7. [7]
    S. Goldwasser, S. Micali and R. Rivest: A Secure Digital Signature Scheme; Siam Journal on Computing, Vol. 17, 2 (1988), pp. 281–308.zbMATHCrossRefMathSciNetGoogle Scholar
  8. [8]
    Neal Koblitz: Algebraic aspects of cryptography; Springer-Verlag, ACM3, 1998, Chapter 4: “Hidden Monomial Cryptosystems”, pp. 80–102.Google Scholar
  9. [9]
    Jacques Patarin: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of Asymmetric Algorithms; Eurocrypt’96, pp. 33–48.Google Scholar
  10. [10]
    Jacques Patarin: La Cryptographie Multivariable; Mémoire d'habilitation à diriger des recherches de l’Université Paris 7, 1999. 354Google Scholar
  11. [11]
    Jacques Patarin, Louis Goubin, Nicolas Courtois, + papers of Eli Biham, Aviad Kipnis, T.T. Moh, et al.: Asymmetric Cryptography with Multivariate Polynomials over a Small Finite Field; known as “orange script”, compilation of different papers with added materials. Available from Jacques.
  12. [12]
    Jacques Patarin, Nicolas Courtois, Louis Goubin: C*-+ and HM-Variations around two schemes of T. Matsumoto and H. Imai; Asiacrypt 1998, pp. 35–49. Unbalanced Oil and Vinegar Signature Schemes; Eurocrypt 1999, Springer-Verlag.Google Scholar
  13. [13]
    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. See [14] for the updated Quartz specification. 352, 357Google Scholar
  14. [14]
    Jacques Patarin, Louis Goubin, Nicolas Courtois: Quartz, 128-bit long digital signatures; An updated version of Quartz specification. available at 357, 359
  15. [15]
    Jacques Patarin, Louis Goubin, Nicolas Courtois: Flash, a fast multivariate signature algorithm; Cryptographers’ Track Rsa Conference 2001, LNCS2020, Springer. 358, 362Google Scholar
  16. [17]
    D. Pointcheval, J. Stern: Security arguments for Digital signatures and Blind Signatures; Journal of Cryptology, Vol.13(3), Summer 2000, pp. 361–396. Efficient signature schemes based on birational permutations zbMATHCrossRefGoogle Scholar
  17. [18]
    Nicolas Courtois, Adi Shamir, Jacques Patarin, Alexander Klimov, Efficient Algorithms for solving Overdefined Systems of Multivariate Polynomial Equations, Eurocrypt’2000, LNCS 1807, Springer-Verlag, pp. 392–407.Google Scholar
  18. [19]
    Adi Shamir, Aviad Kipnis: Cryptanalysis of the HFE Public Key Cryptosystem; Crypto’99.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Nicolas T. Courtois
    • 1
  1. 1.CP8 Crypto Lab, SchlumbergerSemaLouveciennes CedexFrance

Personalised recommendations