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.
翻译:最近以等级为基础的袭击使彩虹的安保低于NIST规定的安保要求,加快了使用古典数学技术的反复内核查找操作。如果应用量子算法来进行这些重复操作,那么按级进行的攻击可能更具有威胁性,并可能大大降低彩虹的安全水平。在本文中,我们提议了名为Q-rMinRank攻击的新型MinRank攻击,这是对彩虹进行关键回收攻击的第一个量子方法。通过设计能够找到内核的量子电路,我们实现了MinRank攻击的二次加速,以收回彩虹的私人钥匙。我们证明即使彩虹的参数五也达不到128位安全水平,也就是我们Q-rMinRank攻击的最低安全要求。这意味着彩虹在量计算环境中不再安全。