1
$\begingroup$

I'm studying the multivariate cryptography and specifically attacks using Groebner basis. On the complexity of such direct attacks, it is well-known that the most important parameter is the degree of regularity.

It is very confusing that there are index of regularity and degree of regularity in literature. Often, the definitions of them are different. For example, The degree of regularity of HFE systems by Dubois and Gama defined the degree of regularity using nontrivial degree falls.

However, in the Asymptotic behaviour of the index of regularity of quadratic semi-regular polynomial systems by Bardet et al., they defined the index of regularity by using Hilbert polynomial. And some article (I cannot remember, sorry) defined the index of regularity as a maximum degree of Groebner basis.

Referring the algorithm complexity formula everywhere, it seems like all are the same. Are those definitions all equivalent? How about this example?

What is the degree or index of regularity of the set $\{x_1,\cdots,x_n\}\subset\mathbb F_q[x_1,\cdots,x_n]$? I think the degree of regularity by the first definition (nontrivial degree fall) is $(q-1)n$ since there never be a nontrivial degree fall. However, the index of regularity by the second and third definition is 1, obviously.

It will be also thankful if you recommend some material to read about them.

$\endgroup$
3
$\begingroup$

There are a couple of definitions in the literature that each aim to capture an aspect of the degree $d$ to which a system of polynomial equations must be expanded before linear algebra on its Macaulay matrix will yield a solution. Some of them are confusingly referred to as the degree of regularity, despite being different things. I will do my best to avoid this term and call them by something else.

Index of Regularity. The index of regularity is defined using the Hilbert polynomial and sequence of an ideal $\mathcal{I}$ [1]. Denote the set of polynomials in $\mathcal{I}$ of degree $s$ or lower as $\mathcal{I}_{\leq s}$ and the same for $\mathbb{F}_q[\mathbf{x}]_{\leq s}$. The Hilbert function $HF_\mathcal{I} : \mathbb{N} \rightarrow \mathbb{N}$ of an ideal $\mathcal{I}$ is defined as $HF_\mathcal{I}(s) = \mathsf{dim} \, \mathbb{F}_q[\mathbf{x}]_{\leq s} / \mathcal{I}_{\leq s}$ and it follows immediately that $HF_\mathcal{I}(s) = \mathsf{dim} \, \mathbb{F}_q[\mathbf{x}]_{\leq s} - \mathsf{dim} \, \mathcal{I}_{\leq s}$. For sufficiently large $s$, the Hilbert function of $\mathcal{I}$ is identical to a polynomial $HP_\mathcal{I}(s) = \sum_{i=0}^d b_i \binom{s}{d-i}$ for some $b_i \in \mathbb{Z}$ and $b_0 \in \mathbb{N} \backslash \{0\}$. This polynomial is called the Hilbert polynomial. The index of regularity is the smallest $s_0$ such that for all $s \geq s_0$, $HF_\mathcal{I}(s) = HP_\mathcal{I}(s)$; this value is also called the Hilbert regularity [2].

Degree of Semi-Regularity. A sequence of polynomials $(p_1(\mathbf{x}), \ldots, p_m(\mathbf{x}))$ is regular if $g \cdot p_i \in \langle p_1, \ldots, p_{i-1}\rangle \implies g \in \langle p_1, \ldots, p_{i-1}\rangle$. Regular systems capture the worst case of polynomial systems. The Hilbert series of an ideal $\mathcal{I}$ is defined as the formal power series $HS_\mathcal{I}(t) = \sum_{s=0}^\infty HF_\mathcal{I}(s) t^s$.The Hilbert series of the ideal $\mathcal{I} = \langle p_1, \ldots, p_m\rangle$ spanned by a regular sequence of homogeneous polynomials $(p_1, \ldots, p_m)$ is given by $HS_\mathcal{I}(t) = \frac{\prod_{j=1}^m (1-t^{\mathsf{deg} \, p_j})}{(1-t)^n}$. It is known [3] that the degree of the highest-degree elements in a degree reverse lexicographical Gröbner basis is bounded (up to a linear change of variables) by the Macaulay bound: $\sum_{i=1}^m (\mathsf{deg}(p_i) - 1) + 1$. This bound can be used to estimate the complexity of Gröbner basis algorithms for regular (i.e., worst-case) systems. If $m = n$, the sequence is regular if and only if $HS_\mathcal{I}$ is a polynomial [4]. This means that for some bound $s_0$ and all $s \geq s_0$, $HF_\mathcal{I}(s) = 0$ and so $HP_\mathcal{I}(s) = 0$. In this case, $s_0 = \mathsf{deg}(HS_\mathcal{I}) + 1$ is exactly the index of regularity.

Unfortunately, regular systems do not exist when $m$ is larger than $n$. In this case, one must assume the ideal has a zero-dimensional variety, and given that this is the case one can adapt the definition of regular sequences as follows. A sequence of polynomials $(p_1, \ldots, p_m)$ is $d$-regular if for all $g \in \mathbb{F}_q[\mathbf{x}]$ with $\mathsf{deg}(g) < d - \mathsf{deg}(p_i)$, $g \cdot p_i \in \langle p_1, \ldots, p_{i-1} \rangle \implies g \in \langle p_1, \ldots, p_{i-1} \rangle$. The sequence $(p_1, \ldots, p_m)$ is semi-regular if and only if it is $s_0$-regular, where $s_0$ is the index of regularity [3]. For a semi-regular system the Hilbert series $HS_\mathcal{I}(t)$ will not be a polynomial but it can be written as a formal power series (i.e. a polynomial with an unlimited number of terms). In this case $s_0$ is the degree of the first term in this formal power series whose coefficient is zero or negative. I like to call this the degree of semi-regularity but it is in fact identical to the degree of regularity assuming the system is semi-regular. Treating random systems of quadratic polynomial equations as semi-regular seems to be empirically justified, but there is no proof that random systems are indeed semi-regular.

First Fall Degree. The first fall degree was first introduced by Dubois and Gama [5] in an attempt to explain why HFE systems seem easier to solve than random systems of the same dimensions. It recycles the intuition that the ``degree of regularity'' should be the lowest degree at which the system starts behaving irregularly, which in interpreted in this case as exhibiting a non-trivial combination of polynomials resulting in a degree fall.

Specifically, let $R = \mathbb{F}[x_1, \ldots, x_n] / \langle x_1^q-x_1, \ldots, x_n^q - x_n\rangle$, i.e., the ring of functions from $\mathbb{F}_q^n$ to $\mathbb{F}_q$. (In fact, we might as well use $R = \mathbb{F}_q[x_1, \ldots, x_n] / \langle x_1^q, \ldots, x_n^q\rangle$ because we only care about the functions' polynomials' homogeneous highest-degree part.) Consider the algebraic combination map $\psi : R \rightarrow \mathbb{F}_q[x_1, \ldots, x_n]$ defined by $(c_1, \ldots, c_m) \mapsto \sum_{i=1}^m c_i \cdot p_i$. We are interested in non-trivial elements of $R$ that are sent to $0$ under $\psi$; these represent combinations (with polynomials as coefficients) of the polynomials $p_1, \ldots, p_m$ that disappear --- a special word for this type of cancellation is syzygy, although that term applies more generally to algebraic combinations that result in any kind of cancellation and not necessarily mapping to zero. In fact, the syzygies we are interested in do not have to map to zero per se; it is enough for the image of $\psi$ to have a lower degree than $\mathsf{max}_i \, \mathsf{deg}(p_i) + \mathsf{max}_i \, \mathsf{deg}(c_i)$. Moreover, we are interested in syzygies of as low degree as possible. For simplicity, let $\mathsf{deg}(p_1) = \cdots = \mathsf{deg}(p_m) = 2$. Let $R_k$ be the subset of $R$ of homogeneous polynomials of degree $k$ and define $\psi_k : R_k \rightarrow \mathbb{F}_q[x_1, \ldots, x_n]$ accordingly as sending $(c_1, \ldots, c_m) \mapsto \sum_{i=1}^m c_i \cdot p_i$ and in this case the kernel of $\psi_k$ consists of exactly the syzygies we are interested in. Define the space of trivial syzygies $T_k(p_1, \ldots, p_m) \subset R$ as spanned by all basis elements of the form

  1. $c \cdot (0, \ldots, 0, p_j, 0, \ldots, 0, p_i, 0, \ldots, 0)$ where the $p_j$ is in the $i$th position and the $p_i$ is in the $j$th position, and where $c \in R_{k-2}$;

  2. $c \cdot (0, \ldots, 0, p_i^{q-1} - 1, 0, \ldots, 0)$ where the $p_i$ is in the $i$th position and where $c \in R_{k-2(q-1)}$.

The reason why $T_k$ is identifiable with trivial syzygies is that its basis elements can be derived without looking at the contents of the $p_i$; they can be described as functions of $p_i$ without replacing the symbol $p_i$ by the polynomial it represents. This leaves the space of non-trivial syzygies which can be characterized as the quotient space $\mathsf{ker} \, \psi_k / T_k$. Phrased crudely, this is the space of syzygies that do not boil down to clever combinations of trivial syzygies.

The first fall degree of the list of polynomials $p_1, \ldots, p_m$ is defined as $\mathsf{min}_k \{ \mathsf{ker} \, \psi_{k-2}(p_1, \ldots, p_m) / T_{k-2}(p_1, \ldots, p_m) \neq \{0\} \}$. Phrased crudely, this is the lowest degree at which algebraic combinations of the polynomials results in non-trivial degree falls. The first fall degree is useful because it is more easily bounded. See Ding et al. [7][8][9] for a series of upper bounds on the first fall degree of multivariate quadratic systems derived from the HFE construction. However, these bounds are not tight, especially for large field order $q$. While the index of regularity is always at least as high as the first fall degree, it can be higher. So a low first fall degree does not necessarily imply an easy-to-solve system although it definitely indicates that something fishy is going on.

Solving Degree. The solving degree was introduced by Ding and Schmidt [6] as a contrasting notion to the first fall degree. It is defined as the degree of the polynomials in the largest extended Macaulay matrix involved in the algebraic system solver. Linear algebra on this matrix dominates the solver's complexity, and so this degree is a good characterizer of this complexity. However, it is much more difficult to bound. Ding and Schmidt show experimentally that the solving degree lies close to the first fall degree. Nevertheless, it is possible to construct artificial systems where the difference is large.

[1]: David Cox and John Little and Donald O'Shea. Ideals, Varieties, and Algorithms. 2nd edition. Ch.9 Sect.3.

[2]: Wikipedia. https://en.wikipedia.org/wiki/Hilbert_series_and_Hilbert_polynomial

[3]: Magali Bardet and Jean-Charles Faugère and Bruno Salvy. On the complexity of Gröbner basis computation of semi-r egular overdetermined algebraic equations. https://www-polsys.lip6.fr/~jcf/Papers/43BF.pdf

[4]: Magali Bardet and Jean-Charles Faugère and Bruno Salvy. On the Complexity of the F5 Gröbner basis Algorithm. https://arxiv.org/pdf/1312.1655.pdf

[5]. Vivien Dubois and Nicolas Gama. The Degree of Regularity of HFE Systems. https://link.springer.com/chapter/10.1007/978-3-642-17373-8_32

[6]: Jintai Ding and Dieter Schmidt. Solving Degree and Degree of Regularity for Polynomial Systems over a Finite Fields. https://link.springer.com/chapter/10.1007/978-3-642-42001-6_4

[7]: Jintai Ding and Timothy Hodges. Inverting HFE Systems Is Quasi-Polynomial for All Fields. https://link.springer.com/chapter/10.1007/978-3-642-22792-9_41

[8]: Jintai Ding and Thorsten Kleinjung. Degree of regularity for HFE-. https://eprint.iacr.org/2011/570

[9]: Jintai Ding and Bo-Yin Yang. Degree of Regularity for HFEv and HFEv-. https://link.springer.com/chapter/10.1007/978-3-642-38616-9_4

$\endgroup$
  • $\begingroup$ Thank you for your kind explanation. I have some more questions. 1. How do you think of my last example? Using your terms, for $\mathcal I=\{x_1,\cdots,x_n\}$, I think the Hilbert function will be constant, $\mathrm{HF}_\mathcal I(s)=1$. So the Hilbert series is not a polynomial, which implies non-regularity. But as your first definition of \emph{regular}, this set of polynomial should be regular. Are there any nontrivial syzygies for $\mathcal I$? I'm sure I have some misunderstandings, but I don't know what it is. $\endgroup$ – wooa0923 Jul 3 '18 at 12:13
  • $\begingroup$ 2. On the last part of $\mathbf{First\; Fall\; Degree}$, you said that the index of the regularity is always larger than or equal to the first fall degree, is that for a semi-regular situation or every situation? It seems that the index of regularity don't need to be bigger than or equal to the first fall degree unless the set of polynomials is semi-regular. $\endgroup$ – wooa0923 Jul 3 '18 at 12:18
  • $\begingroup$ 3. Except for the solving degree, it seems that the first fall degree is the most weaker part. Is it enough to show that some cryptosystem has a large enough first fall degree? (only considering direct attacks) $\endgroup$ – wooa0923 Jul 3 '18 at 12:21
  • $\begingroup$ I agree that the Hilbert function in your example is the constant 1. However, I don't think regularity is a meaningful concept for linear systems of equations, precisely because linear systems. It is true that this ideal has no non-trivial syzygies but simultaneously any basis for this ideal is only a linear change of variables away from a Gröbner basis. $\endgroup$ – Alan Jul 3 '18 at 13:58
  • $\begingroup$ The first-fall degree is always smaller or equal to the index of regularity, independent of whether the system is semi-regular. (In fact, we don't know if semi-regular systems exist, but we are sure that systems have a definite index of regularity.) $\endgroup$ – Alan Jul 3 '18 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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