Paper 2020/1343

Improved Cryptanalysis of UOV and Rainbow

Ward Beullens

Abstract

The contributions of this paper are twofold. First, we simplify the description of the Unbalanced Oil and Vinegar scheme (UOV) and its Rainbow variant, which makes it easier to understand the scheme and the existing attacks. We hope that this will make UOV and Rainbow more approachable for cryptanalysts. Secondly, we give two new attacks against the UOV and Rainbow signature schemes; the intersection attack that applies to both UOV and Rainbow and the rectangular MinRank attack that applies only to Rainbow. Our attacks are more powerful than existing attacks. In particular, we estimate that compared to previously known attacks, our new attacks reduce the cost of a key recovery by a factor of $2^{17}$, $2^{53}$, and $2^{73}$ for the parameter sets submitted to the second round of the NIST PQC standardization project targeting the security levels I, III, and V respectively. For the third round parameters, the cost is reduced by a factor of $2^{20}$, $2^{40}$, and $2^{55}$ respectively. This means all these parameter sets fall short of the security requirements set out by NIST.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
post-quantum cryptographydigital signaturescryptanalysis
Contact author(s)
ward beullens @ esat kuleuven be
History
2020-10-26: received
Short URL
https://ia.cr/2020/1343
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1343,
      author = {Ward Beullens},
      title = {Improved Cryptanalysis of UOV and Rainbow},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1343},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1343}},
      url = {https://eprint.iacr.org/2020/1343}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.