Details:
Title  Degree of regularity for HFEV and HFEV.  Author(s)  Jintai Ding, BoYin Yang  Type  Book, Chapter in Book, Conference Proceeding  Abstract  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−1)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=⌊logq(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 F4/F5 or similar Gröbner methods to be around 292.  Keywords  Degree of regularity, HFE, HFEv, HFEv  ISBN  9783642386152/pbk 
URL 
http://link.springer.com/chapter/10.1007%2F9783642386169_4 
Language  English  Pages  5266  Publisher  Berlin: Springer  Year  2013  Edition  0  Translation 
No  Refereed 
No 
