You are looking at a specific version 20120718:133228 of this paper. See the latest version.

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

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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Multivariate CryptographyAlgebraic CryptanalysisRainbowMinRankHighRankNon-Commutative RingsQuaternions
Contact author(s)
enrico thomae @ rub de
History
2012-07-18: revised
2012-05-29: received
See all versions
Short URL
https://ia.cr/2012/270
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.