Question about degree of regularity

Question

I have been reading some papers on cryptography based on multivariate systems and I have a question. How does one relate the difficulty of calculating Gröbner basis (GB) of a multivariate system with its degree of regularity?

From what I understand, for a lot of cryptosystems, there are ways of getting a system of polynomial equations, and a solution for such a system will give us the secret key (let us suppose this is unique). Once we have such a system, we can 'linearize' and solve them (like in Arora-Ge) or we can attack the system by calculating its GB and finding the root from there.

From Bardet's paper, for semi-regular systems, there is a quantity called a degree of regularity (there is also a way to calculate it) and she also gives how to estimate the difficulty of GB calculation using this quantity.

My question is: what if we don't know if our system is semi-regular? This degree of regularity seems to be roughly the highest degree term in the GB. If so, how can I estimate the highest degree term of the GB of a system of polynomials that I have in my hand?

There seem to be a few papers which go into any sort of detail in these topics, so I will be glad if I could also get some papers to read.

Answer 1

For random systems of multivariate polynomial equations, the assumption that it is regular or semi-regular is generally accepted. Here "random" means with every coefficient being sampled uniformly. An open question in this field is to determine the probability of a random system being regular or semi-regular as a function of the number of variables, equations, and of the degree. This assumption implies that this probability is cryptographically negligible, but until that is proven it is technically an assumption.

Unfortunately, for systems of multivariate polynomial equations that are not random, we don't even have such an assumption, much less a rigorous framework supporting it. The best you can do is instantiate the system of equations for various small parameters and observe to what degree, if any, the empirical degree of regularity deviates from that of random systems with the same dimensions.

Having said that, there might be a couple of interesting sources for you in this vein:

1. Faugère and Perret study the complexity of a direct algebraic attack on UOV, and observe that the degree of regularity of the resulting system of polynomial equations equals that of random ones. This result has since been used to justify the stronger assumption that attacking UOV in this way is the same as solving random systems of equations, which enables complexity estimation and hence parameter selection. IACR ePrint
2. Ding et al. study the first fall degree, which is similar to but subtly different from the degree of regularity, of Square systems which are $\mathbb{F}_q$-affine equivalent to the monomial $\mathcal{X}^2 \in \mathbb{F}_{q^n}[\mathcal{X}]$ for some odd $q$. They conclude that this degree is exactly $q$. This is surprising, because generally we observe that the degree of regularity is independent of the field over which the equations are defined. Unfortunately, Square systems are insecure due to structural attacks that have nothing to do with Gröbner bases. ScienceDirect
3. Ding and various co-authors study the same first fall degree in the context of HFE$_v^-$ systems. They achieve upper bounds on the first fall degree (which they confusingly call the degree of regularity) as a function of the degree of the hidden polynomial, the number of vinegar variables added, and the number of polynomials dropped. Unfortunately, this upper bound is not tight and so it cannot be used to argue that a HFE-like system is probably secure. Springer Journal page Author home page