ROUND 3 OFFICIAL COMMENT: Rainbow

242 views
Skip to first unread message

Ward Beullens

unread,
Oct 26, 2020, 5:34:41 AM10/26/20
to pqc-co...@nist.gov, pqc-...@list.nist.gov
Hi everyone,

I found 2 new attacks on the Rainbow signature scheme. The first attack
uses the ideas from the Kipnis-Shamir attack [1] and reduces the
security of Rainbow I, III and V by 7 bits, 4 bits and 19 bits
respectively. This attack also applies to the UOV scheme.

The second attack is specific to Rainbow and is also more efficient. It
reduces a key recovery to a new instance of the MinRank problem, which
can then be solved with the methods of Bardet et al.[2] . This attack
reduces the security level of Rainbow I, III and V by 20 bits, 40 bits
and 55 bits respectively.

The paper is on ePrint: https://eprint.iacr.org/2020/1343

I would like to thank the Rainbow team for reviewing an earlier version
of the paper and providing me with helpful feedback.

All the best,
Ward

[1] https://link.springer.com/chapter/10.1007/BFb0055733
[2] https://arxiv.org/abs/2002.08322

Bo-Yin Yang

unread,
Oct 26, 2020, 9:46:09 AM10/26/20
to pqc-forum, Ward Beullens, pqc-...@list.nist.gov, pqc-co...@nist.gov
Dear All,

The Rainbow team acknowledges that the new attacks by Ward Beullens are fundamentally correct and does cut down the security of Rainbow somewhat, in the same manner as most other schemes still in the NIST competition have lost a considerable number of security bits.  We are actively studying the consequences and will formulate a comprehensive response including a new set of parameters soon.

Bo-Yin, for the Rainbow team members
Reply all
Reply to author
Forward
0 new messages