Paper 2009/596

Could SFLASH be repaired?

Jintai Ding, Vivien Dubois, Bo-Yin Yang, 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.

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. An extended abstract of this paper appears in the proceedings of ICALP 2008
Keywords
multivariate cryptographysignatureSFLASHdifferential
Contact author(s)
vivien dubois @ m4x org
History
2009-12-04: received
Short URL
https://ia.cr/2009/596
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/596,
      author = {Jintai Ding and Vivien Dubois and Bo-Yin Yang and Owen Chia-Hsin Chen and Chen-Mou Cheng},
      title = {Could SFLASH be repaired?},
      howpublished = {Cryptology ePrint Archive, Paper 2009/596},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/596}},
      url = {https://eprint.iacr.org/2009/596}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.