# MathSciDoc: An Archive for Mathematician ∫

#### TBDmathscidoc: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}.
@inproceedings{jintai2013degree,
title={Degree of Regularity for HFEv and HFEv-},
author={Jintai Ding, and Bo-Yin Yang},
url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220714141326698282639},
booktitle={PQCrypto 2013},
pages={52–66},
year={2013},
}

Jintai Ding, and Bo-Yin Yang. Degree of Regularity for HFEv and HFEv-. 2013. In PQCrypto 2013. pp.52–66. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220714141326698282639.