THE QUANTUM INTELLIGENCER

Breaking Post-Quantum Security: Rectangular MinRank Attack Compromises MAYO, QR-UOV, and VOX Signature Schemes In Plain English: This research addresses a critical security problem: how to protect digital signatures from future quantum computers. The researchers found that three promising new signature methods submitted to a major government standards process have a serious security flaw. They discovered that an attack method previously used against another signature scheme also works against these three new methods, making them much easier to break than previously thought. This matters because these methods were being considered for protecting everything from government communications to online banking against future quantum computer attacks. Summary: This paper presents a significant cryptanalysis breakthrough demonstrating that the rectangular MinRank attack, originally developed by Beullens for the Rainbow signature scheme, is applicable to three newly proposed UOV-based variants: MAYO, QR-UOV, and VOX. These schemes were recently submitted to NIST's post-quantum cryptography standardization process for additional digital signature schemes. The research shows that despite UOV schemes traditionally being considered resistant to MinRank attacks due to their full-rank matrix structure, the rectangular variant of this attack successfully compromises these new implementations. The authors provide complexity estimates for the attack, with particularly severe consequences for VOX - all parameter sets submitted to NIST can be broken using at most 2^55 gate operations, representing a substantial reduction in security compared to claimed levels. This finding challenges the security assumptions underlying these UOV variants and has immediate implications for the NIST standardization process, potentially eliminating these candidates from consideration due to insufficient security margins. Key Points: - The rectangular MinRank attack, previously applied to Rainbow, works against three new UOV variants: MAYO, QR-UOV, and VOX - These schemes were submitted to NIST's post-quantum cryptography standardization process - UOV schemes were previously considered MinRank-resistant due to full-rank matrix public keys - The attack represents a fundamental vulnerability in these newly proposed signature schemes - VOX parameter sets submitted to NIST can be broken with at most 2^55 gate operations - The findings have significant implications for post-quantum cryptography standardization Notable Quotes: - "Rainbow is a multi-layered variant of the UOV scheme, and UOV is considered having a resistance to all MinRank attacks since its public key consists of full rank matrices." - "In this paper, we show that the rectangular MinRank attack is applicable to MAYO, QR-UOV and VOX." - "We report that all the parameter sets of VOX submitted to NIST PQC standardization are broken in at most 2^55 gate operations." Data Points: - VOX security broken with at most 2^55 gate operations (specific complexity measure) - Three specific schemes affected: MAYO, QR-UOV, VOX - These schemes were submitted to NIST PQC standardization for additional digital signature schemes - The attack was originally developed for Rainbow by Beullens - UOV schemes use public keys consisting of full rank matrices Controversial Claims: - The claim that UOV schemes have "resistance to all MinRank attacks" is presented as established knowledge but is directly challenged by this research. The assertion that the rectangular MinRank attack fundamentally compromises these schemes may be controversial among their designers, who likely believed their parameter choices provided adequate security. The implication that these schemes should be removed from NIST consideration represents a strong position on their viability. Technical Terms: - Multivariate public-key cryptography (MPKC) - Post-quantum cryptography (PQC) - MinRank attacks - Rectangular MinRank attack - UOV (Unbalanced Oil and Vinegar) scheme - Rainbow scheme - Gate operations (complexity measure) - NIST PQC standardization - Digital signature schemes - Public key cryptography - Cryptanalysis —Ada H. Pemberley Dispatch from Trigger Phase E0