Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Rainbow Band Separation is Better than we Thought

Published

Author(s)

Daniel Smith-Tone, Ray Perlner

Abstract

Currently the National Institute of Standards and Technology (NIST) is engaged in a post- quantum standardization effort, analyzing numerous candidate schemes to provide security against the advancing threat of quantum computers. Among the candidates in the second round of the standardization process is Rainbow, a roughly 15 year old digital signature scheme based on multivariate systems of equations. While there are many attack avenues for Rainbow, the parameters have to date seemed balanced in such a way to make every attack sufficiently costly that it meets the security levels specified by NIST in their standardization effort. One type of attack against Rainbow has historically outperformed empirically its theoretical complexity: the Rainbow Band Separation (RBS) attack. We explain this discrepancy by providing a tighter theoretical analysis of the attack complexity. While previous analyses assumed that the system of equations derived in the attack are generic, our analysis uses the fact that they are structured to justify tighter bounds on the complexity. As a result, we can prove under the same set of assumptions used to justify the analysis in the Rainbow submission specification that none of the parameters of Rainbow achieve their claimed security level. We then apply our analysis to suggest the small parameter changes necessary to guarantee that Rainbow can meet the NIST security levels.
Citation
Cryptology ePrint Archive
Volume
2020

Keywords

Multivariate, Digital Signature, Rainbow

Citation

Smith-Tone, D. and Perlner, R. (2020), Rainbow Band Separation is Better than we Thought, Cryptology ePrint Archive, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=930461, https://eprint.iacr.org/2020/702 (Accessed October 26, 2021)
Created June 9, 2020, Updated October 12, 2021