The Sflash Signature Scheme

WARNING: WE HEAR THAT SFLASH HAVE BEEN BROKEN... MORE INFO TO FOLLOW.

There is also a way to avoid the new attack.

Sflash has been selected by Nessie Consortium and recommended for low-cost smart cards. Since then, the authors have specified the new version Sflash-v3, but after recent research, the old version Sflash-v2 is still preferred see below. Sflash-v2 remains the fastest signature scheme known and can only be rivalled by NTRU.

The Sflash signature scheme

Sflash is very fast multivariate signature scheme that can be implemented in low-end smart cards.
The first version Sflash-v1 was insecure, and Henri Gilbert found the decisive argument that breaks it (published at Eurocrypt 2002).

Then the Sflash specification has been updated twice.

In Sflash-v2the new version Sflash-v3 the signature length is of 259 bits and the public key has 15 Kbytes.

In the later version Sflash-v3 the signature length is of 469 bits and the public key has (unfortunately) 112 kb.

Sflash-v2 and Sflash-v3 can sign AND verify signatures on a low-power device (smart card, PDA, etc.). It can be implemented on low-end smart cards, for example, Sflash-v2 (recommended by Nessie) takes only 60 ms to compute a signature on a simple Infineon SLE66 at 10 MHz (Intel 8051 based). Sflash should remain the fastest signature scheme in the world and can be rivalled only be NTRU (The TTS signature scheme from CHES 2004 have been broken by Ding and Yin, cf. IWAP 2004).

The security of Sflash is based on a hard problem of solving random systems of quadratic equations, which underlies the security of many multivariate public key schemes, such as HFE and Quartz. More importantly, the hardness of this problem is also necessary for the security of many block ciphers including AES, and for many stream ciphers.

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.
Jiun-Ming Chen, Nicolas Courtois and Bo-Yin Yang: On Asymptotic Security Estimates in XL and Gröbner Bases-Related Algebraic Cryptanalysis, will be presented at ICICS'04, 27-29 October 2004, Malaga, Spain. To appear in LNCS, Springer.
Nicolas Courtois: Algebraic Attacks over GF(2^k), Application to HFE Challenge 2 and Sflash-v2. PKC 2004, March 1-4 2004, Singapore.
WARNING: the numerical results in the proceedings paper are clearly too optimistic and none of the attacks is really faster than 2^80. See the above work by Jiun-Ming Chen, Nicolas Courtois and Bo-Yin Yang.
Nicolas Courtois, Louis Goubin and Jacques Patarin: SFLASHv3, a fast asymmetric signature scheme available on eprint.iacr.org/2003/211/.
This paper specifies the new version of Sflash, Sflash-v3. In this paper the previous version is no longer recommended by the authors, however later the authors have changed their minds and Sflash-v2 is still recommended.
Recently intai Ding reported an attack on Sflash-v3 (but not on v2). It seems that this attack does not work, further research is required.
A pseudo-attack: A Key Substitution Attack on SFLASHv3, by Willi Geiselmann and Rainer Steinwandt at eprint.iacr.org/2003/245/. This paper is shows a funny way of playing with Sflash keys BUT has probably no implications whatsoever on the security of digital signatures with Sflash (see the standard definition of a secure digital signature, no problem, and moreover hundreds of similar "pseudo-attacks" exist for about any signature scheme).
Mehdi-Laurent Akkar, Nicolas Courtois, Louis Goubin, Romain Duteuil, A Fast and Secure Implementation of Slash, (meaning for Sflash-v2) PKC 2003, LNCS 2567, Springer, pp. 267-278.
Nessie imlementation report to be published soon.
Nicolas Courtois, Louis Goubin, Jacques Patarin: ``Flash, a fast multivariate signature algorithm'': in Cryptographers' Track Rsa Conference 2001, LNCS 2020, pp. 298-307, Springer. Also submitted to Nessie European Call for Primitives
The Sflash-v2 specification (still 100 % recommended).
And here is the (very old and badly broken) version Sflash-v1 submitted to Nessie
The Nessie discussion forum.
The Nessie Security report, version 2.0.
The Turbosignatures project by the French Government Research Departement.
The HFE cryptosystem home page

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