Cryptology ePrint Archive: Report 2012/270

Quo Vadis Quaternion? Cryptanalysis of Rainbow over Non-Commutative Rings

Enrico Thomae

Abstract: The Rainbow Signature Scheme is a non-trivial generalization of the well known Unbalanced Oil and Vinegar Signature Scheme (Eurocrypt '99) minimizing the length of the signatures. Recently a new variant based on non-commutative rings, called NC-Rainbow, was introduced at CT-RSA 2012 to further minimize the secret key size. We disprove the claim that NC-Rainbow is as secure as Rainbow in general and show how to reduce the complexity of MinRank attacks from 2^288 to 2^112 and of HighRank attacks from 2^128 to 2^96 for the proposed instantiation over the ring of Quaternions. We further reveal some facts about Quaternions that increase the complexity of the signing algorithm. We show that NC-Rainbow is just a special case of introducing further structure to the secret key in order to decrease the key size. As the results are comparable with the ones achieved by equivalent keys, which provably do not decrease security, and far worse than just using a PRNG, we recommend not to use NC-Rainbow.

Category / Keywords: public-key cryptography / Multivariate Cryptography, Algebraic Cryptanalysis, Rainbow, MinRank, HighRank, Non-Commutative Rings, Quaternions

Date: received 11 May 2012, last revised 18 Jul 2012

Contact author: enrico thomae at rub de

Available format(s): PDF | BibTeX Citation

Note: Pdf file was damaged. It was not possible to search within the file.

Version: 20120718:133228 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]