Cryptanalysis of the SFLASH Signature Scheme

SFLASH is a signature scheme proposed by Patarin, Goubin and Courtois in 2001 [9,7] following a design they had introduced in 1998 [8]. SFLASH is reputed for being very fast and has been recommended by the NESSIE European Consortium since 2003 as the best known solution for implementation on low cost smart cards [5]. In this abstract, we present new attacks on the general design proposed by Patarin et al. [8] which allows to forge signatures in a few minutes for practical instantiations including the SFLASH scheme recommended by NESSIE [5].