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

Autor:	Enrico Thomae
Rok vydání:	2012
Předmět:	Pseudorandom number generator Discrete mathematics Ring (mathematics) Unbalanced Oil and Vinegar law Order (ring theory) Quaternion Cryptanalysis Multivariate cryptography Mathematics Key size law.invention
Zdroj:	Lecture Notes in Computer Science ISBN: 9783642329272 SCN
DOI:	10.1007/978-3-642-32928-9_20
Popis:	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 2288 to 2192 and of HighRank attacks from 2128 to 296 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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::7bd70a905d8cc95ad3e2eddab6770976 https://doi.org/10.1007/978-3-642-32928-9_20 Zobrazit plný text záznamu