Paper 2025/1808

Variables for Free: Fault Injection Attack on MAYO via Valid Solutions

Abstract

Abstract. Multivariate quadratic problem over a finite field, a NP-hard problem, is also considered as one of the hard problems for cryptanalytic-relevant quantum computers. It is the foundation of multivariate quadratic-based cryptography and several post-quantum digital signature schemes initially proposed in 1990s. Patarin’s unbalanced Oil-and-Vinegar (UOV) scheme is the oldest MQ signature algorithm that remain secure against large-scale cryptanalytic-relevant quantum computers. UOV has compact signature size and succinct verification time. However, it suffers from a very large public key size. Subsequently, UOV-based variants have focused on minimizing the size of central map. MAYO, a candidate advanced to NIST’s round 2 additional post-quantum digital signatures, is based off the UOV algorithm with whipped structure to reduce public key size. In this paper, we present a theoretical framework for fault injection-based attack. It targets the construction of valid signatures during the signing phase. This fault-based analysis allows efficient extraction of secret oil vectors from the public signatures, facilitating the complete recovery of the entire secret oil space O. Finally, we show that this analysis is applicable to parameter sets of all three security level of all versions of MAYO.