3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Thanks for the links. I had seen a previous answer by you on a similar question which was also very helpful to me. $\endgroup$ – Natalie Jan 10 at 21:09
  • $\begingroup$ If I could bother you just a little bit more, I wanted to ask you if my understanding is correct. So when dealing with MQ based cryptosytems (semi-regular or not), the index/degree of regularity (defined as smallest d when Hilbert function equals Hilbert Polynomial) is what determines the difficulty of calculating GB. This degree of regularity is also an upper bound (but perhaps not tight?) on the largest degree of its GB? $\endgroup$ – Natalie Jan 10 at 21:24
  • $\begingroup$ So, when you say I should empirically check for small parameters, you are saying - take the theoretical estimates for semi-regular systems of the same degrees, no. of variables and run some experiments on my own system instances and check how the highest degrees of the GBs compare? $\endgroup$ – Natalie Jan 10 at 21:24
  • $\begingroup$ Yes, the degree of regularity, defined via the Hilbert function, is an upper bound on the degrees of polynomials in the Gröbner basis for degree-refining term orders. If the Gröbner basis had polynomials of higher degree, then they would not be found by a Gröbner basis algorithm that only processes polynomials of strictly lower degree, thereby disqualifying that algorithm from being a Gröbner basis algorithm. $\endgroup$ – Alan Jan 11 at 23:52
  • $\begingroup$ I do not think this bound is tight. However, the paper by Bardet that you cite seems to contradict my intuition. It states that the degree of regularity is the maximal degree in the Gröbner basis for grevlex order (i.e. the standard degree-refining order). I am not sure how to validate or refute this claim. Certainly, Magali Bardet is a better authority than I am :) $\endgroup$ – Alan Jan 11 at 23:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.