NIST's confidence in Rainbow's security ?

[Quan Thoi Minh Nguyen]

Hi,

I'm a cryptographic practitioner. I rely on cryptographers and NIST’s judgement on security of cryptographic protocols.

When I read NIST’s chosen finalists, I’m confused and concerned about Rainbow’s security. To quote NIST’s documents https://nvlpubs.nist.gov/nistpubs/ir/2020/NIST.IR.8309.pdf

“Rainbow is a multivariate signature scheme with a layered construction based on the Unbalanced Oil-Vinegar (UOV) signature scheme. The additional structure imposed by the Rainbow layers exposes the scheme to a larger array of cryptanalytic techniques but improves the scheme’s efficiency. Rainbow offers fast signing and verifying and very short signatures but has very large public keys.

The selection of Rainbow increases the diversity of the finalist signature schemes ….”

https://www.scribd.com/document/474476570/PQC-Overview-Aug-2020-NIST

“Remaining concern: Ain’t nobody really sure about this multivariate stuff; MV has a bad rep. How confident can we be in MV security?”

On the one hand, NIST stresses that security is the number one selection criteria. On the other hand, while NIST doesn’t have enough confidence in Rainbow's security, Rainbow was still chosen as the finalists. In the next 12-18 months, I’m puzzled how the confidence on Rainbow's security can be improved:

 i/ If cryptographers publish new attacks, the confidence on Rainbow’s security is reduced.

ii/ If cryptographers don’t publish new attacks, as 12-18 months is such a short time for cryptanalysis, I don’t see how we can increase confidence in Rainbow’s security.

In summary, based on NIST’s current judgement on Rainbow security and attacks always get better over time, it looks risky to me to deploy Rainbow in any real world systems even if NIST decides to standardize it.

Best regards,

- Quan

[daniel.apon]

Hi Quan,

There are a few separate issues you've brought up here, let me try to dissect them:


First-- Regarding those slides: those were written from my personal point of view, originally targeted for grad students at a local university, in the hope of encouraging them to begin work in the area of NIST PQC related research.
While I'd absolutely stand behind the content of the slides, they are also full with "my personal recollection" or "my personal opinion" of this event or technical topic or that.

Where this delineation matters (in terms of "parsing the information recorded in those slides"): I primarily have personal expertise in lattice and hash-based cryptography (and more recently in code-based cryptography), but less so in multivariate cryptography (it's an area I'm just getting into), and much less so in isogeny-based cryptography.

You can contrast a set of slides written from my personal point of view, e.g. the ones posted online at request after the fact, against official products of the entire NIST PQC team, e.g. the report itself (where you can find our official comments about Rainbow) and e.g. Dustin Moody's upcoming talk surveying NIST PQC's 3rd Round (aimed for the broader PQC audience) that will be at PQCrypto 2020 very soon.


Interlude:
Q: "Is NIST changing its point of view between this presentation and that?"
A: "No, this is a rhetorical nonsense. These slides I wrote were those from a single member of the NIST PQC team who is not a MV expert, not from the full team, and -- for what it's worth -- it's not clear what the 'changes' even are."


Second-- Regarding the security of Rainbow. The more proper way to frame the security of Rainbow (again, in my view, given more than one bullet point to write in..) is as follows.
For many years, there has been a gap between the theoretical analysis of Rainbow and the empirical/experimental performance of attacks against Rainbow (and the related problems in multivariate cryptography).
In a situation where we have a gap between "our understanding" (the theoretical matter) and "our observations" (the empirical matter), this raises a concern -- "How confident can we be in the security of the system?"

Then, very recently, there were a sequence of three papers posted online that explored a new notion of "bi-degree" as it related to the band separation type of attack against Rainbow.
1) https://eprint.iacr.org/2020/702.pdf "Rainbow Band Separation is Better than we Thought" Smith-Tone, Perlner (NIST authors)
2) https://eprint.iacr.org/2020/703.pdf "New Complexity Estimation on the Rainbow-Band-Separation Attack" Nakamura, Ikematsu, Wang, Ding, Takagi (Japan & Univ of Cincinnati USA)
3) https://eprint.iacr.org/2020/908.pdf "Analysis on the MinRank Attack using Kipnis-Shamir Method Against Rainbow" Nakamura, Wang, Ikematsu (a subset of the 2nd paper; now looking at a 'multi-degree' notion)

The key point here (as I understand the situation..) is not that "attacks have improved, and may continue improving against Rainbow."
Rather, we first had a very loose theoretical analysis of the attacks, and empirical results (from a generic style of algorithm) that outperformed the theoretical analysis.
Now, however, the theoretical analysis has been tightened in a way that matches the empirical observations of the generic algorithm.

Rather than Rainbow having lost some claim to security, we now understand why the generic style of attack performs as it does.
So in fact, our theoretical understanding of attacks against Rainbow now align with our empirical observations of attacks against Rainbow.

(If you want more information about the technical matter, I'm at the limits of my personal grasp of the situation; I'll have to ask Ray or Daniel S-T from NIST if they would like to additionally chime in on the discussion.. =))

Hope this is helpful!
Best,
--Daniel

[Quan Thoi Minh Nguyen]

Thanks Daniel for detailed response and clarification, I really appreciate it.