A Fast and Secure Implementation of Sflash

  • Mehdi-Laurent Akkar
  • Nicolas T. Courtois
  • Romain Duteuil
  • Louis Goubin
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2567)


Sflash is a multivariate signature scheme, and a candidate for standardisation, currently evaluated by the European call for primitives Nessie. The present paper is about the design of a highly optimized implementation of Sflash on a low-cost 8-bit smart card (without coprocessor). On top of this, we will also present a method to protect the implementation protection against power attacks such as Differential Power Analysis.

Our fastest implementation of Sflash takes 59 ms on a 8051 based CPU at 10MHz. Though the security of Sflash is not as well understood as for example for RSA, Sflash is apparently the fastest signature scheme known. It is suitable to implement PKI on low-cost smart card, token or palm devices. It allows also to propose secure low-cost payment/banking solutions.


Digital Signatures PKI Addition Chains Multivariate Cryptography Matsumoto-Imai cryptosystem C* C*— trapdoor function HFE portable devices Smart cards Power Analysis SPA DPA 


  1. [1]
    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. Available at 268
  2. [2]
    Nicolas Courtois, Magnus Daum, Patrick Felke, On the Security of HFE, HFEvand Quartz, PKC’2003, to appear in LNCS, Springer. 268Google Scholar
  3. [3]
    Magnus Daum, Patrick Felke, Some new aspects concerning the Analysis of HFE type Cryptosystems, Presented at Yet Another Conference on Cryptography (YACC’02), June 3–7, 2002, Porquerolles Island, France. 268Google Scholar
  4. [4]
    Magnus Daum, Das Kryptosystem HFE und quadratische Gleichungssysteme über endlichen Körpern, Diplomarbeit, Universität Dortmund, 2001. Available at
  5. [5]
    Jean-Charles Faugère, Report on a successful attack of HFE Challenge 1 with Gröbner bases algorithm F5/2, announcement that appeared in sci.crypt newsgroup on the internet on April 19th 2002.Google Scholar
  6. [6]
    Henri Gilbert, Marine Minier, Cryptanalysis of Sflash, EUROCRYPT’2002, LNCS 2332, Springer, pp. 288–298. 268Google Scholar
  7. [7]
    Michael Garey, David Johnson, Computers and Intractability, a guide to the theory of NP-completeness, Freeman, p. 251.Google Scholar
  8. [8]
    Willi Geiselmann, Rainer Steinwandt, Thomas Beth, Revealing 441 Key Bits of SFLASH-v2, Third NESSIE Workshop, November 6–7, 2002, Munich, Germany. 270Google Scholar
  9. [9]
  10. [10]
    Neal Koblitz,Algebraic aspects of cryptography, Springer, ACM3, 1998, Chapter 4: “Hidden Monomial Cryptosystems”, pp. 80–102. 267Google Scholar
  11. [11]
    Paul Kocher, Joshua Jaffe, Benjamin Jun, Introduction to Differential Power Analysis and Related Attacks. Technical Report, Cryptography Research Inc., 1998. Available at 268, 274
  12. [12]
    Tsutomu Matsumoto, Hideki Imai, Public Quadratic Polynomial-tuples for efficient signature-verification and message-encryption, EUROCRYPT’88, LNCS 330, Springer 1998, pp. 419–453. 267Google Scholar
  13. [13]
    Jacques Patarin, Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt’88, CRYPTO’95, LNCS 963, Springer, pp. 248–261. 267Google Scholar
  14. [14]
    Jacques Patarin, Nicolas Courtois, Louis Goubin, C*-+ and HM-Variations around two schemes of T. Matsumoto and H. Imai, ASIACRYPT’98, LNCS 1514, Springer, pp. 35–49. 267, 268Google Scholar
  15. [15]
    Jacques Patarin, Louis Goubin, Nicolas Courtois, Quartz, 128-bit long digital signatures, Cryptographers’ Track RSA Conference 2001, San Francisco 8–12 April 2001, LNCS 2020, Springer, pp. 282–297. Note: The Quartz signature scheme has been updated since, see [16].Google Scholar
  16. [16]
    Jacques Patarin, Louis Goubin, Nicolas Courtois, Quartz, 128-bit long digital signatures, An updated version of Quartz specification. available at 278
  17. [17]
    Jacques Patarin, Louis Goubin, Nicolas Courtois, Flash, a fast multivariate signature algorithm, Cryptographers’ Track RSA Conference 2001, San Francisco 8–12 April 2001, LNCS 2020, Springer, pp. 298–307. 267, 268, 269Google Scholar
  18. [19]
    Adi Shamir, Efficient signature schemes based on birational permutations, CRYPTO’93, LNCS 773, Springer, pp. 1–12. 268Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Mehdi-Laurent Akkar
    • 1
  • Nicolas T. Courtois
    • 1
  • Romain Duteuil
    • 1
  • Louis Goubin
    • 1
  1. 1.SchlumbergerSemaCP8 Crypto LabLouveciennesFrance

Personalised recommendations