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
-
CC BY
BibTeX
@misc{cryptoeprint:2012/270,
author = {Enrico Thomae},
title = {Quo Vadis Quaternion? Cryptanalysis of Rainbow over Non-Commutative Rings},
howpublished = {Cryptology {ePrint} Archive, Paper 2012/270},
year = {2012},
url = {https://eprint.iacr.org/2012/270}
}
