Degree of Regularity for HFEv and HFEv-

Jintai Ding University of Cincinnati, Cincinnati OH, USA; Chongqing University, China Bo-Yin Yang Academia Sinica, Taipei, Taiwan

TBD mathscidoc:2207.43062

PQCrypto 2013, 52–66, 2013.6
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 \frac{(q−1)(r+v+a−1)}{2}+2 if q is even and r+a is odd, \frac{(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=⌊log_q (D−1)⌋+1. In particular, setting a = 0 gives us the case of HFEv where the degree of regularity is bound by \frac{(q−1)(r+v−1)}{2}+2 if q is even and r is odd, \frac{(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_4/F_5 or similar Gröbner methods to be around 2^{92}.
No keywords uploaded!
[ Download ] [ 2022-07-14 14:13:26 uploaded by dingjt ] [ 303 downloads ] [ 0 comments ]
  title={Degree of Regularity for HFEv and HFEv-},
  author={Jintai Ding, and Bo-Yin Yang},
  booktitle={PQCrypto 2013},
Jintai Ding, and Bo-Yin Yang. Degree of Regularity for HFEv and HFEv-. 2013. In PQCrypto 2013. pp.52–66.
Please log in for comment!
Contact us: | Copyright Reserved