International Association
for Cryptologic Research

Multivariate public key cryptosystems represent a promising family of post-quantum cryptographic schemes. Extensive research has demonstrated that multivariate polynomials are particularly well-suited for constructing digital signature schemes. Notably, the Unbalanced Oil and Vinegar (UOV) signature scheme and its variants have emerged as leading candidates in NIST's recent call for additional digital signature proposals. Security analysis against UOV variants are typically categorized into key-recovery attacks and forgery attacks, with the XL algorithm serving as one of the most significant methods for mounting key-recovery attacks. Recently, Lars Ran introduced a new attack against UOV variants that could be seen as an XL attack using exterior algebra; nevertheless, this new attacking algorithm is applicable only when the underlying (finite) field of the UOV variant is of characteristic $2$. In this work, we address this limitation by proposing a unified framework. Specifically, we first propose the notion of reduced symmetric algebra over any field, whose strength can be gleaned from the fact that it is essentially symmetric algebra when the characteristic $p$ of the underlying field is $0$ and is exterior algebra when $p=2$. Based upon the reduced symmetric algebra, we then propose a new XL attack against all UOV variants. Our XL attack is equivalent to Lars Ran's one for those UOV variants whose underlying fields are of characteristic $p=2$; more importantly, our XL attack can also be applied to analyze those UOV variants with odd characteristic, such as QR-UOV submitted to NIST's PQC Standardization Project. It should be noted that in regard to those 12 QR-UOV recommended instances, our XL attack does not outperform existing key-recovery counterparts; nevertheless, it is the optimal key-recovery attack for some specific UOV instances with odd characteristic.