Quantum rectangular MinRank attack on multi-layer UOV signature schemes.

Area of Science:

• Cryptography
• Quantum Computing
• Information Security

Background:

• Recent rank-based attacks have weakened the security of Rainbow, a multi-layer Unbalanced Oil and Vinegar (UOV) signature scheme, below NIST requirements.
• The application of quantum algorithms to iterative operations in these attacks could pose a significant threat to multi-layer UOV signatures.

Purpose of the Study:

• To propose the first quantum approach for key recovery attacks on multi-layer UOV signatures, termed the quantum rectangular MinRank (Q-rMinRank) attack.
• To demonstrate the applicability of the Q-rMinRank attack to Rainbow and HiMQ signature schemes.

Main Methods:

• Designed two quantum oracle circuits for kernel finding, optimizing for either qubit width or circuit depth.
• Incorporated mathematical techniques to reduce quantum resource requirements and complexity for the MinRank attack.
• Estimated quantum resources and analyzed quantum complexity for the developed circuits.

Main Results:

• Achieved a quadratic speedup for the MinRank attack, enabling faster private key recovery for multi-layer UOV signatures.
• The width-optimized circuit requires 1089 logical qubits for Rainbow parameter set V.
• The depth-optimized circuit achieves a quantum complexity lower than that for recovering AES-192 secret keys.

Conclusions:

• The Q-rMinRank attack presents a novel and effective quantum method for attacking multi-layer UOV signatures.
• The developed quantum circuits demonstrate efficient key recovery with reduced quantum resources.
• This research provides crucial insights into the quantum security of UOV-based signature schemes.