  Recent rank-based attacks have reduced the security of Rainbow below the
security requirements set out by NIST by speeding up repeated kernel finding
operations using classical mathematics techniques. If quantum algorithms are
applied to perform these repeated operations, the rank-based attacks may be
more threatening and could dramatically lower the security level of Rainbow. In
this paper, we propose a novel MinRank attack called Q-rMinRank attack, the
first quantum approach to the key recovery attacks on Rainbow. By designing
quantum circuits that can find the kernel, we achieved quadratic speedup for
the MinRank attack to recover the private keys of Rainbow. We show that even
the parameter set V of Rainbow does not meet the 128-bit security level, the
minimum security requirement through our Q-rMinRank attack. It means that
Rainbow is no longer secure in quantum computing environments.

Cryptography and Security