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
-
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},
url = {https://eprint.iacr.org/2009/596}
}
