International Association
for Cryptologic Research

In this paper we introduce a new attack on the multivariate encryption scheme HFERP, a big field scheme including an extra variable set, additional equations of the UOV or Rainbow shape as well as additional random polynomials. Our attack brings several parameter sets well below their claimed security levels. The attack combines novel methods applicable to multivariate schemes with multiple equation types with insights from the Simple Attack that broke Rainbow in early 2022, though interestingly the technique is applied in an orthogonal way. In addition to this attack, we apply support minors techniques on a MinRank instance drawing coefficients from the big field, which was effective against other multivariate big field schemes. This work demonstrates that there exist previously unknown impacts of the above works well beyond the scope in which they were derived.

The unbalanced oil and vinegar signature scheme (UOV) is a multivariate signature scheme that has essentially not been broken for over 20 years. However, it requires the use of a large public key; thus, various methods have been proposed to reduce its size. In this paper, we propose a new variant of UOV with a public key represented by block matrices whose components correspond to an element of a quotient ring. We discuss how it affects the security of our proposed scheme whether or not the quotient ring is a field. Furthermore, we discuss their security against currently known and newly possible attacks and propose parameters for our scheme. We demonstrate that our proposed scheme can achieve a small public key size without significantly increasing the signature size compared with other UOV variants. For example, the public key size of our proposed scheme is 85.8 KB for NIST's Post-Quantum Cryptography Project (security level 3), whereas that of compressed Rainbow is 252.3 KB, where Rainbow is a variant of UOV and is one of the third-round finalists of the NIST PQC project.