HybridRAM: The first quantum approach for key recovery attacks on Rainbow

A rectangular MinRank attack, proposed by Ward Beullens in 2021, reduced the security of Rainbow below the security requirements set out by NIST. If quantum algorithms are applied to perform repeated operations in this attack, the rectangular MinRank attacks may be more threatening and dramatically lower the security level of Rainbow. In this paper, we propose a Hybrid Rank Attack Model called HybridRAM that reduces the computation complexity of rank-based attacks by applying Grover's quantum search algorithm. We also design a Grover oracle quantum circuit suitable for the rectangular MinRank attack and then propose a Hybrid Rectangular MinRank attack that recovers the keys of Rainbow using the designed quantum circuit. We show that even the parameter set V of Rainbow does not fall short of the 128-bit security level, the minimum security requirement. It means that Rainbow is no longer secure in quantum computing environments.