Cryptology ePrint Archive: Report 2008/108
New Differential-Algebraic Attacks and Reparametrization of Rainbow
Jintai Ding AND Bo-Yin Yang AND Owen Chen AND 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.
Category / Keywords: rank, differential attack, algebraic attack, oil-and-vinegar
Publication Info: Will appear at ACNS 2008 and Springer LNCS volume 5037
Date: received 10 Mar 2008, last revised 24 May 2008
Contact author: by at moscito org
Available format(s): PDF | BibTeX Citation
Version: 20080524:092555 (All versions of this report)
Short URL: ia.cr/2008/108
[ Cryptology ePrint archive ]