Cryptology ePrint Archive: Report 2009/596

Could SFLASH be repaired?

Jintai Ding and Vivien Dubois and Bo-Yin Yang and Owen Chia-Hsin Chen and Chen-Mou Cheng

Abstract: The SFLASH signature scheme stood for a decade as the most successful cryptosystem based on multivariate polynomials, before an efficient attack was finally found in 2007. In this paper, we review its recent cryptanalysis and we notice that its weaknesses can all be linked to the fact that the cryptosystem is built on the structure of a large field. As the attack demonstrates, this richer structure can be accessed by an attacker by using the specific symmetry of the core function being used. Then, we investigate the effect of restricting this large field to a purely linear subset and we find that the symmetries exploited by the attack are no longer present. At a purely defensive level, this defines a countermeasure which can be used at a moderate overhead. On the theoretical side, this informs us of limitations of the recent attack and raises interesting remarks about the design itself of multivariate schemes.

Category / Keywords: multivariate cryptography, signature, SFLASH, differential

Publication Info: An extended abstract of this paper appears in the proceedings of ICALP 2008

Date: received 3 Dec 2009

Contact author: vivien dubois at m4x org

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20091204:085517 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]