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

Enrico Thomae

Paper 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.

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

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Keywords: Multivariate Cryptography Algebraic Cryptanalysis Band Separation Key Recovery Attack Rainbow Enhanced STS Enhanced TTS MFE Diophantine Equations MQQ-Enc MQQ-Sig
Contact author(s): enrico thomae @ rub de
History: 2012-08-11: last of 2 revisions; 2012-04-30: received; See all versions
Short URL: https://ia.cr/2012/223
License: CC BY

BibTeX

@misc{cryptoeprint:2012/223,
      author = {Enrico Thomae},
      title = {A Generalization of the Rainbow Band Separation Attack and its Applications to Multivariate Schemes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/223},
      year = {2012},
      url = {https://eprint.iacr.org/2012/223}
}