View Related Documents

Abstract

A recently proposed class of multivariate Public-Key Cryptosystems, the Rainbow-Like Digital 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  ∗ −) was broken by Dubois, Fouque, Shamir, and Stern via a differential attack. In this paper, we exhibit similar algebraic and diffential attacks, that will reduce published Rainbow-like schemes below their security levels. We will also discuss how parameters for Rainbow and TTS schemes should be chosen for practical applications.
Note: Up-to-date version will be available at http://eprint.iacr.org/2008/108

Keywords  rank - differential attack - algebraic attack - oil-and-vinegar

Fulltext Preview

Image of the first page of the fulltext document