Paper 2025/1137

Security Analysis on UOV Families with Odd Characteristics: Using Symmetric Algebra

Abstract

UOV and its variants have been submitted to NIST's PQC Standardization Project. And security analysis against UOV families (i.e., UOV and its 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 novel key-recovery attack against UOV families that could be seen as an XL attack using exterior algebra; nevertheless, this new XL attack is applicable only when the underlying (finite) field of UOV instances is of characteristic $2$. In this work, we address this limitation by generalizing Lars Ran's approach, and our contributions are three-fold. First, we generalize the notion of exterior algebra and propose the notion of reduced symmetric algebra over any field, which is essentially symmetric algebra when the characteristic $p$ of the underlying field is $0$ and is exterior algebra when $p=2$. Moreover, based upon the reduced symmetric algebra, we propose a new XL attack against all UOV families: as a generalization of Lars Ran's attack, our XL attack also works for those UOV instances with odd characteristic; for instance, it works for those $12$ recommended QR-UOV instances submitted to NIST's PQC Standardization Project, although its performance does not outperform those of the existing key-recovery attacks. Finally, analysis on our XL attack reveals the connection between the characteristic $p$ and the concrete hardness of UOV instances.