Abstract
For some applications of digital signatures the traditional schemes as RSA, DSA or Elliptic Curve schemes, give signature size that are not short enough (with security 280, the minimal length of these signatures is always ≥ 320 bits, and even ≥ 1024 bits for RSA). In this paper we present a first well defined algorithm and signature scheme, with concrete parameter choice, that gives 128-bit signatures while the best known attack to forge a signature is in 280. It is based on the basic HFE scheme proposed on Eurocrypt 1996 along with several modifications, such that each of them gives a scheme that is (quite clearly) strictly more secure. The basic HFE has been attacked recently by Shamir and Kipnis (cf [3]) and independently by Courtois (cf this RSA conference) and both these authors give subexponential algorithms that will be impractical for our parameter choices. Moreover our scheme is a modification of HFE for which there is no known attack other that inversion methods close to exhaustive search in practice. Similarly there is no method known, even in theory to distinguish the public key from a random quadratic multivariate function.
QUARTZ is so far the only candidate for a practical signature scheme with length of 128-bits.
QUARTZ has been accepted as a submission to NESSIE (New European Schemes for Signatures, Integrity, and Encryption), a project within the Information Societies Technology (IST) Programme of the European Commission.
Part of this work is an output of project “Turbo-signatures”, supported by the french Ministry of Research.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. Courtois, A. Shamir, J. Patarin, A. Klimov, Eficient Algorithms for solving Overdefined Systems of Multivariate Polynomial Equations, in Advances in Cryptology, Proceedings of EUROCRYPT’2000, LNCS no 1807, Springer, 2000, pp. 392–407. 1 On a Pentium III 500 MHz. This part can be improved: the given software was not optimized. 2 This part can be improved: the given software was not optimized.
E. Kaltofen, V. Shoup, Fast polynomial factorization over high algebraic extensions of finite fields, in Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, 1997.
A. Kipnis, A. Shamir, Cryptanalysis of the HFE public key cryptosystem, in Advances in Cryptology, Proceedings of Crypto’99, LNCS n˚ 1666, Springer, 1999, pp. 19–30.
J. Patarin, Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms, in Advances in Cryptology, Proceedings of EUROCRYPT’96, LNCS no 1070, Springer Verlag, 1996, pp. 33–48.
A. Kipnis, J. Patarin and L. Goubin, Unbalanced Oil and Vinegar Signature Schemes, in Advances in Cryptology, Proceedings of EUROCRYPT’99, LNCS no 1592, Springer, 1999, pp. 206–222.
The HFE cryptosystem web page: http://www.hfe.minrank.org
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Patarin, J., Courtois, N., Goubin, L. (2001). QUARTZ, 128-Bit Long Digital Signatures. In: Naccache, D. (eds) Topics in Cryptology — CT-RSA 2001. CT-RSA 2001. Lecture Notes in Computer Science, vol 2020. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45353-9_21
Download citation
DOI: https://doi.org/10.1007/3-540-45353-9_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41898-6
Online ISBN: 978-3-540-45353-6
eBook Packages: Springer Book Archive