The Quartz Signature Scheme

Quartz with the hidden polynomial degree increased is the only solution recommended by the Nessie Consortium for short digital signatures.

The Quartz signature scheme

Quartz is the shortest known secure signature scheme with signature length of only 128 bits. It is based on HFE with many improvements.

The only other such scheme the McEliece signature scheme that gives both faster and shorter signatures. Unfortunately it has a much larger public key of 1.125 Mb instead of 71 kb for Quartz.

Signature generation takes about 9 seconds on 500 MHz PC, and the verification is extremely fast.

Quartz is designed in order to provide long term security and anticipates the future attacks. There will probably never be any attack on Quartz other that the known generic attack in 2^80 that does not use the Quartz structure at all. Moreover this attack requires 2^80 of memory, and the only realistic memoryless attack known will require as much as 2^100 computations.

References:

Nicolas Courtois, Short Signatures, Provable Security, Generic Attacks and Computational Security of Multivariate Polynomial Schemes such as HFE, Quartz and Sflash, draft, eprint 2004/143. Ask also Louis Granboulan for his recent results on security proofs for Quartz...
Out of date, replaced by the above: Nicolas Courtois: Generic Attacks and the Security of Quartz, PKC 2003, LLNCS 2567, Springer, pp. 351-364. A preliminary version has been presented at the second Nessie workshop. Download the extended version of the paper / download my PKC presentation (not updated since).
Implementing QuartzLight in Java, by Christopher Wolf.
Using this implementation is not free of charge because it uses HFE that is patented and belongs to Axalto Smart Cards.
Nicolas Courtois, Magnus Daum and Patrick Felke: On the Security of HFE, HFEv- and Quartz, PKC 2003, LNCS 2567, Springer, pp. 337-350. An extended version can be found on eprint.
The Quartz specification has been updated. Download the updated version.
Dowload the version submitted to Nessie
Nicolas Courtois, Louis Goubin, Jacques Patarin: ``Quartz, 128-bit long digital signatures'': in Cryptographers' Track Rsa Conference 2001, LNCS 2020, pp.282-297, Springer-Verlag. Also submitted to Nessie European Call for Primitives
The Nessie discussion forum.
The Nessie Security report, version 1.0.
The Turbosignatures project by the French Government Research Departement.
The HFE cryptosystem home page
Much faster multivariate signature schemes and having a smaller public key : Flash /Sflash.

Interesting links: multivariate cryptanalysis:
Algebraic attacks on AES, Rijndael, Serpent, Camellia, etc.., the XSL attack on block ciphers
Algebraic attacks (or XL attacks) applied to stream ciphers
Interesting links: multivariate cryptography:
The McEliece_based short signature scheme CFS
The HFE cryptosystem home page
The Minrank Zero-knowledge identification scheme
Quartz /Flash /Sflash signature schemes
Nicolas Courtois research page
TTM cryptosystem, GPT cryptosystem

Last updated on 9th of December 2003.