Degree of regularity for HFEv and HFEv-

In this paper, we first prove an explicit formula which bounds the degree of regularity of the family of HFEv ("HFE with vinegar") and HFEv- ("HFE with vinegar and minus") multivariate public key cryptosystems over a finite field of size q. The degree of regularity of the polynomial system derived from an HFEv- system is less than or equal to (q - 1)(r + v + a - 1)/2 + 2 if q is even and r + a is odd, (q - 1)(r + v + a)/2 + 2 otherwise, where the parameters v, D, q, and a are parameters of the cryptosystem denoting respectively the number of vinegar variables, the degree of the HFE polynomial, the base field size, and the number of removed equations, and r is the "rank" paramter which in the general case is determined by D and q as r = ⌊_q(D - 1)⌋ + 1. In particular, setting a = 0 gives us the case of HFEv where the degree of regularity is bound by (q - 1)(r + v - 1)/2 + 2 if q is even and r is odd, (q - 1)(r + v)/2 + 2 otherwise. This formula provides the first solid theoretical estimate of the complexity of algebraic cryptanalysis of the HFEv- signature scheme, and as a corollary bounds on the complexity of a direct attack against the QUARTZ digital signature scheme. Based on some experimental evidence, we evaluate the complexity of solving QUARTZ directly using F₄/F₅ or similar Gröbner methods to be around 2⁹².