Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleDegree of regularity for HFEV and HFEV--.
Author(s) Jintai Ding, Bo-Yin Yang
TypeBook, Chapter in Book, Conference Proceeding
AbstractIn 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.
KeywordsDegree of regularity, HFE, HFEv, HFEv
URL http://link.springer.com/chapter/10.1007%2F978-3-642-38616-9_4
PublisherBerlin: Springer
Translation No
Refereed No