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 CryptographyAlgebraic CryptanalysisBand SeparationKey Recovery AttackRainbowEnhanced STSEnhanced TTSMFEDiophantine EquationsMQQ-EncMQQ-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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2012/223}},
      url = {https://eprint.iacr.org/2012/223}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.