Paper 2008/108

New Differential-Algebraic Attacks and Reparametrization of Rainbow

Jintai Ding, Bo-Yin Yang, Owen Chen, Ming-Shing Chen, and Doug Cheng

Abstract

A recently proposed class of multivariate quadratic schemes, the Rainbow-Like signature Schemes, in which successive sets of central variables are obtained from previous ones by solving linear equations, seem to lead to efficient schemes (TTS, TRMS, and Rainbow) that perform well on systems of low computational resources. Recently SFLASH ($C^{\ast-}$) was broken by Dubois, Fouque, Shamir, and Stern via a differential attack. In this paper, we exhibit similar attacks based on differentials, that will reduce published Rainbow-like schemes below their security levels. We will present a new type of construction of Rainbow-Like schemes and design signature schemes with new parameters for practical applications.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Will appear at ACNS 2008 and Springer LNCS volume 5037
Keywords
rankdifferential attackalgebraic attackoil-and-vinegar
Contact author(s)
by @ moscito org
History
2008-05-24: last of 3 revisions
2008-03-12: received
See all versions
Short URL
https://ia.cr/2008/108
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/108,
      author = {Jintai Ding and Bo-Yin Yang and Owen Chen and Ming-Shing Chen and Doug Cheng},
      title = {New Differential-Algebraic Attacks and Reparametrization of Rainbow},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/108},
      year = {2008},
      url = {https://eprint.iacr.org/2008/108}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.