Cryptanalysis of Rainbow

摘要

Rainbow is a fast asymmetric multivariate signature algorithm proposed by J. Ding and D. Schmidt in [5]. This paper presents a cryptanalysis of Rainbow which enables an attacker provided with the public key to recover an equivalent representation of the secret key, thus allowing her to efficiently forge a signature of any message. For the set of parameter values recommended by the authors of Rainbow in order to achieve a security level strictly higher than 2~(80), the complexity of our attack is less than 2~(71) operations. This is 2~(40) times less than the complexity of the best known attack used by the authors to dimension their system.