Cryptology ePrint Archive: Report 2012/223

A Generalization of the Rainbow Band Separation Attack and its Applications to Multivariate Schemes

Enrico Thomae

Abstract: The Rainbow Signature Scheme is a non-trivial generalization of the well known Unbalanced Oil and Vinegar (UOV) signature scheme (Eurocrypt '99) minimizing the length of the signatures. By now the Rainbow Band Separation attack is the best key recovery attack known. For some sets of parameters it is even faster than a direct attack on the public key. Unfortunately the available description of the attack is very ad hoc and does not provide deep insights. In this article we provide another view on the Rainbow Band Separation attack using the theory of equivalent keys and a new generalization called good keys. Thereby we generalize the attack into a framework that also includes Reconciliation attacks. We further formally prove the correctness of the attack and show that it does not only perform well on Rainbow, but on all multivariate quadratic (MQ) schemes that suffer from missing cross-terms. We apply our attack and break the Enhanced STS signature scheme and all its variants, as well as the MFE encryption scheme and its variant based on Diophantine equations. In the case of Rainbow and Enhanced TTS we show that parameters have to be chosen carefully and that the remaining efficiency gain over UOV is small. As there is still some room to improve the Band Separation attack, it is not clear whether layer-based MQ-schemes will eventually become superfluous or not.

Category / Keywords: Multivariate Cryptography, Algebraic Cryptanalysis, Band Separation, Key Recovery Attack, Rainbow, Enhanced STS, Enhanced TTS, MFE, Diophantine Equations, MQQ-Enc, MQQ-Sig

Date: received 23 Apr 2012, last revised 11 Aug 2012

Contact author: enrico thomae at rub de

Available format(s): PDF | BibTeX Citation

Note: Two new attacks on MQQ-Enc, MQQ-Sig and STS based on prime factorization are added.

Version: 20120811:182512 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]