Could SFLASH be repaired?

Jintai Ding, Vivien Dubois, Bo Yin Yang*, Owen Chia Hsin Chen, Chen Mou Cheng

*Corresponding author for this work

Research output: Chapter in Book or Report/Conference proceedingConference Proceedingpeer-review

30 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationAutomata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings
Pages691-701
Number of pages11
EditionPART 2
DOIs
Publication statusPublished - 2008
Externally publishedYes
Event35th International Colloquium on Automata, Languages and Programming, ICALP 2008 - Reykjavik, Iceland
Duration: 7 Jul 200811 Jul 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 2
Volume5126 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference35th International Colloquium on Automata, Languages and Programming, ICALP 2008
Country/TerritoryIceland
CityReykjavik
Period7/07/0811/07/08

Keywords

  • Differential
  • Multivariate cryptography
  • SFLASH
  • Signature

Fingerprint

Dive into the research topics of 'Could SFLASH be repaired?'. Together they form a unique fingerprint.

Cite this