Analysis of Multivariate Encryption Schemes: Application to Dob

Abstract

In this paper, we study the effect of two modifications to multivariate public key encryption schemes: internal perturbation (ip), and $Q_+$. Focusing on the Dob encryption scheme, a construction utilising these modifications, we accurately predict the number of degree fall polynomials produced in a Gröbner basis attack, up to and including degree five. The predictions remain accurate even when fixing variables. Based on this new theory we design a novel attack on the Dob encryption scheme, which breaks Dob using the parameters suggested by its designers.

While our work primarily focuses on the Dob encryption scheme, we also believe that the presented techniques will be of particular interest to the analysis of other big–field schemes.

1 Introduction

Public key cryptography has played a vital role in securing services on the internet that we take for granted today. The security of schemes based on integer factorization and the discrete logarithm problem (DLP) is now well understood, and the related encryption algorithms have served us well over several decades.

In [25] it was shown that quantum computers can solve both integer factorization and DLP in polynomial time. While large scale quantum computers that break the actual implementations of secure internet communication have yet to be built, progress is being made in constructing them. This has led the community for cryptographic research to look for new public key primitives that are based on mathematical problems believed to be hard even for quantum computers, so called post–quantum cryptography.

In 2016 NIST launched a project aimed at standardizing post–quantum public key primitives. A call for proposals was made and many candidate schemes were proposed. The candidates are based on a variety of problems, including the shortest vector problem for lattices, the problem of decoding a random linear code, or the problem of solving a system of multivariate quadratic equations over a finite field (the MQ problem).

The first encryption scheme based on the MQ problem, named $C^*$, was proposed in [21] and was broken by Patarin in [23]. Since then, much work has gone into designing new central maps, as well as modifications that can enhance the security of existing ones. Several multivariate schemes have been proposed following $C^*$, for instance [5, 24, 27, 28]. While some of the schemes for digital signatures based on the MQ problem seem to be secure, it has been much harder to construct encryption schemes that are both efficient and secure. The papers [1, 16, 22, 26, 29], all present attacks on MQ-based public key encryption schemes, and as of now we are only aware of a few (e.g., [9, 32]) that remain unbroken.

In [20] a new kind of central mapping is introduced, which can be used to construct both encryption and signature schemes. The novel feature of the central mapping is that it has a high degree over an extension field, while still being easy to invert. The encryption variant proposed in [20] is called Dob and uses two types of modifications to its basic construction.

Our Contribution

The initial part of our work provides a theoretical analysis of (combinations of) two modifications for multivariate cryptosystems. The $Q_+$–modification was (to the best of our knowledge) first proposed in [20], while the second, internal perturbation (ip), has been in use for earlier schemes [8, 9, 12]. More specifically, we develop the tools for computing the dimension of the ideal associated with these modifications, at different degrees. This in turn provides key insights into the complexity of algebraic attacks based on Gröbner basis techniques.

As an application, we focus on the Dob encryption scheme proposed in [20]. We are able to deduce formulas that predict the exact number of first fall polynomials for degrees 3,4 and 5. These formulas furthermore capture how the number of degree fall polynomials changes as an attacker fixes variables, which also allows for the analysis of hybrid methods (see e.g., [3]).

Finally, the newfound understanding allow us to develop a novel attack on the Dob encryption scheme. Through analyzing and manipulating smaller, projected polynomial systems, we are able to extract and isolate a basis of the secret modifiers, breaking the scheme. While the details of the attack have been worked out for the Dob encryption scheme, we believe the techniques themselves could be further generalised to include different central maps and modifications.

Organisation

The paper is organized as follows. In Sect. 2 we recall the relation between $\mathbb {F}_2^d$ and $\mathbb {F}_{2^d}$, as well as the necessary background for solving multivariate systems over $\mathbb {F}_2$. In Sect. 3 we develop the general theory that explores the effectiveness of the modifications $Q_+$ and ip . Section 4 introduces the Dob scheme, and we deduce formulas that predict the number of degree fall polynomials for this construction. Experimental data verifying the accuracy of these formulas is presented in Sect. 5. In Sect. 6 we develop the novel attack on the Dob encryption scheme, using the information learned from the previous sections. Finally, Sect. 7 concludes the work.

Table of definitions

Throughout the paper we will use the notation in Table 1. We list it here for easy reference.

Table 1. Notation used in the paper

2 Preliminaries

Multivariate big–field encryption schemes are defined using the field $\mathbb {F}_{q^d}$ and the d-dimensional vector space over the base field, $\mathbb {F}_q^d$. In practical implementations, $q=2$ is very often used, and we restrict ourselves to only consider this case in the paper.

2.1 Polynomial System Solving

A standard technique used in the cryptanalysis of multivariate schemes, is to compute a Gröbner basis associated with the ideal $\langle p_i + y_i \rangle _{1\le i\le m}$, for a fixed ciphertext $y_1,\ldots ,y_m$ (see for example [7] for more information on Gröbner bases). As we are interested in an encryption system, we can reasonably expect a unique solution in the boolean polynomial ring B(n). In this setting the solution can be read directly from a Gröbner basis of any order.

One of the most efficient algorithms for computing Gröbner bases is F$_4$ [15]. In the usual setting, the algorithm proceeds in a step–wise manner; each step has an associated degree, D, where all the polynomial pairs of degree D are reduced simultaneously using linear algebra. The degree associated with the most time consuming step is known as the solving degree, $D_{solv}$, and time complexity of F$_4$ can be estimated to be:

$$\begin{aligned} \text {Complexity}_{\text {GB}} = \mathcal {O}\bigg (\bigg (\sum _{i = 0}^{D_{solv}}\left( {\begin{array}{c}d\\ i\end{array}}\right) \bigg )^{\omega }\bigg ), \end{aligned}$$

(1)

where $2\le \omega \le 3$ denotes the linear algebra constant. Determining $D_{solv}$ is in general difficult, but there is an important class of polynomial systems that is well understood. Recall that a homogeneous polynomial system, $\mathcal {F}^h = (f_1^h,\ldots ,f_m^h) \in \overline{B}(n)^m$, is said to be semi–regular if the following holds; for all $1\le i \le m$ and any $g\in \overline{B}(n)$ satisfying

$$\begin{aligned} gf_i^h\in \langle f_1^h,\ldots ,f_{i-1}^h\rangle \text { and deg}(gf_i) < D_{reg}, \end{aligned}$$

(2)

then $g\in \langle f_1^h,\ldots ,f_{i}^h\rangle$ (note that $f_{i}^h$ is included since we are over $\mathbb {F}_2$). Here $D_{reg}$ is the degree of regularity as defined in [2], (for $i=1$ the ideal generated by $\emptyset$ is the 0–ideal). We will also need a weaker version of this definition, where we say that $\mathcal {F}^h$ is $D_0$–semi–regular, if the same condition holds, but for $D_0 < D_{reg}$ in place of $D_{reg}$ in Eq. (2). An inhomogeneous system $\mathcal {F}$ is said to be ($D_0$–)semi–regular if its upper homogeneous part is. For a quadratic, semi–regular system $\mathcal {F}$ over $\overline{B}(n)$, the Hilbert series of $\overline{B}(n)/\mathcal {F}$ is written as (Corollary 7 in [2]):

$$\begin{aligned} T_{m,n}(z) = \frac{(1+z)^n}{(1 + z^2)^m}, \end{aligned}$$

(3)

and the degree of regularity can be computed explicitly as the degree of the first non–positive term in this series. Determining whether a given polynomial system is semi–regular may, in general, be as hard as computing a Gröbner basis for it. Nevertheless, experiments seem to suggest that randomly generated polynomial systems behave as semi–regular sequences with a high probability [2], and the degree of regularity can in practice be used as the solving degree in Eq. (1). We will denote the degree of regularity for a semi–regular sequence of m polynomials in n variables as $D_{reg}(m,n)$. On the other hand, it is well known that many big–field multivariate schemes are not semi–regular (e.g., [5, 16]). In these cases the first fall degree is often used to estimate the solving degree ([10, 22]). The first fall degree, according to [10], will be defined in Definition 2, but before that we recall the definition of a Macaulay matrix associated to a polynomial system.

Definition 1

Let $\mathcal {P}$ be an (inhomogeneous) polynomial system in B(n), of degree two. An (inhomogeneous) Macaulay matrix of $\mathcal {P}$ at degree D, $M_{D}(\mathcal {P})$, is a matrix with entries in $\mathbb {F}_2$, such that:

• 1. The columns are indexed by the monomials of degree $\le D$ in B(n).

• 2. The rows are indexed by the possible combinations $x^{\alpha }p_i$, where $1\le i \le n$ and $x^{\alpha }\in B(n)$ is a monomial of degree $\le D-2$. The entries in one row corresponds to the coefficients of the associated polynomial.

Similarly, we define the homogeneous Macaulay matrix of $\mathcal {P}$ at degree D, $\overline{M}_D(\mathcal {P})$, by considering $\mathcal {P}^h\in \overline{B}(n)$, only including monomials of degree D in the columns, and rows associated to combinations $x^{\alpha }p_i^h$, deg$(x^\alpha ) = D-2$.

Syzygies and Degree Fall Polynomials. Let $\mathcal {P}^h = (p_1^h,\ldots ,p_m^h) \in \overline{B}(n)_2^m$ denote a homogeneous quadratic polynomial system. The set $\mathcal {P}^h$ induces a map:

$$\begin{aligned} \begin{array}{rccl} \psi ^{\mathcal {P}^h}: &{} \overline{B}(n)^m &{} \longrightarrow &{} \overline{B}(n)\\ &{} (b_1,\ldots ,b_m) &{} \longmapsto &{} \sum _{i = 1}^{m}b_ip_i^h, \end{array} \end{aligned}$$

(4)

which in turn splits into graded maps $\psi _{\nu -2}^{\mathcal {P}^h}: \overline{B}(n)_{\nu -2}^m \longrightarrow \overline{B}(n)_{\nu }$. The $\overline{B}(n)$–module Syz$(\mathcal {P}^h)_\nu = \text {Ker}(\psi _{\nu -2}^{\mathcal {P}^h})$ is known as the $\nu$–th grade of the (first) syzygy module of $\mathcal {P}^h$. When $\nu = 4$, Syz$(\mathcal {P}^h)_4$ will contain the Koszul Syzygies¹, which are generated by $(0,...,0,p_j^h,0,...,0,p_i^h,0,...,0)$ ($p_j^h$ is in position i and $p_i^h$ is in position j), and the field syzygies, which are generated by $(0,...,0,p_i^h,0,...,0)$ ($p_i^h$ in position i). These syzygies correspond to the cancellations $p_j^hp_i^h + p_i^hp_j^h = 0$ and $(p_i^h)^2 = 0$. As they are always present, and not dependent of the structure of $\mathcal {P}^h$, they are sometimes referred to as the trivial syzygies. More generally, we will define the submodule $\mathcal {T}(\mathcal {P}^h)_{\nu } \subseteq \text {Syz}(\mathcal {P}^h)_{\nu }$ to be the $\nu$–th graded component of the module generated by the Koszul and field syzygies, and denote $\mathcal {S}(\mathcal {P})_\nu = \text {Syz}(\mathcal {P}^h)_\nu /\mathcal {T}(\mathcal {P}^h)_\nu$.

Definition 2

The first fall degree associated with the quadratic polynomial system $\mathcal {P}$ is the natural number

$$\begin{aligned} D_{ff} = \text {min}\{ D\ge 2 | \mathcal {S}(\mathcal {P})_D \ne 0 \}. \end{aligned}$$

Representations over Base and Extension Fields. For any fixed isomorphism $\mathbb {F}_2^d \simeq \mathbb {F}_{2^d}$, there is a one–to–one correspondence between d polynomials in B(d) and a univariate polynomial in $\mathbb {F}_{2^d}[X]/\langle X^{2^{d}} + X\rangle$ (see 9.2.2.2 in [4] for more details). For an integer j, let $w_2(j)$ denote the number of nonzero coefficients in the binary expansion of j. For a univariate polynomial H(X), we define max$_{w_2}(H)$ as the maximal $w_2(j)$ where j is the degree of a term occurring in H. Let P(X) be the univariate representation of the public key of a multivariate scheme, and suppose there exists a polynomial H(X) such that

$$\begin{aligned} \text {max}_{w_2}(H(X)P(X)) < \text {max}_{w_2}(H(X)) + \text {max}_{w_2}(P(X)). \end{aligned}$$

(5)

Then the multivariate polynomials corresponding to the product H(X)P(X) will yield degree fall polynomials from (multivariate) degree $\text {max}_{w_2}(H) + \text {max}_{w_2}(P)$ down to degree $\text {max}_{w_2}(HP)$.

It was mentioned in [16] that the presence of polynomials satisfying Eq. (5) was the reason for Gröbner basis algorithms to perform exceptionally well on HFE–systems. Constructing particular polynomials that satisfy Eq. (5) has also been a central component in the security analyzes found in [10] and [22].

3 Estimating the Number of Degree Fall Polynomials

We start by introducing a general setting, motivated by the Dob encryption scheme which we will focus on later. Let $\mathcal {F}:\mathbb {F}_2^n\rightarrow \mathbb {F}_2^m$ be a system of m quadratic polynomials over B(n). Furthermore, consider the following two modifiers²:

• 1. The internal perturbation (ip) modification chooses k linear combinations $v_1,\ldots ,v_k$, and adds a random quadratic polynomial in the $v_i$’s to each polynomial in $\mathcal {F}$.

• 2. The $Q_+$ modifier selects t quadratic polynomials $q_1,\ldots ,q_t$, and adds a random linear combination of them to each polynomial in $\mathcal {F}$.

Let $H_{ip}$ be the random quadratic polynomials in $v_1,\ldots ,v_k$ and $H_{Q_+}$ the random linear combinations of $q_1,\ldots ,q_t$. A modification of the system $\mathcal {F}$ can then be written as

$$\begin{aligned} \begin{aligned} \mathcal {P}:\mathbb {F}_2^n&\longrightarrow \mathbb {F}_2^m \\ x&\longmapsto \mathcal {F}(x) + H_{ip}(x) + H_{Q_+}(x). \end{aligned} \end{aligned}$$

(6)

The problem we will be concerned with in this section is the following: given full knowledge of the degree fall polynomials of the system $\mathcal {F}$, what can we say about the degree fall polynomials of the system $\mathcal {P}$?

3.1 The Big Picture

Let $\mathcal {F}^h$ and $\mathcal {P}^h$ denote the homogeneous parts of the systems $\mathcal {F}$ and $\mathcal {P}$ respectively, and consider them over $\overline{B}(n)$. For a positive integer $\alpha \le k$, we define $V^\alpha$ to be the homogeneous ideal in $\overline{B}(n)$ that is generated by all possible combinations of $\alpha$ linear forms from the ip modification, i.e.:

$$\begin{aligned} V^\alpha = \langle (v_{i_{1}}v_{i_{2}}\cdots v_{i_{\alpha }})^h | 1\le i_1< i_2< \ldots < i_\alpha \le k\rangle . \end{aligned}$$

(7)

In other words, $V^{\alpha }$ is the product ideal $\overbrace{V^1\cdot V^1 \cdot \ldots \cdot V^1}^{\alpha }$. Similarly, for the quadratic polynomials associated with the $Q_+$ modifier we define $Q^\beta$ for a positive integer $\beta \le t$ to be the product ideal:

$$\begin{aligned} Q^\beta = \langle (q_{i_{1}}q_{i_{2}}\cdots q_{i_{\beta }})^h | 1\le i_1< i_2< \ldots < i_\beta \le t\rangle . \end{aligned}$$

(8)

Finally, for $0\le \alpha \le k$ and $0\le \beta \le t$, we define the ideal of different combinations of the modifiers, $M^{(\alpha ,\beta )} = \langle V^\alpha ,Q^\beta \rangle$, along with the boundary cases $M^{(\alpha ,0)} = V^\alpha$, $M^{(0,\beta )} = Q^\beta$ and $M^{(0,0)} = \langle 1\rangle$.

The following result is an important first step to understand how the degree fall polynomials in $\mathcal {F}$ behave when modifiers are introduced to the scheme.

Lemma 1

Let $\mathcal {P}^h$, $\mathcal {F}^h$, $M^{(2,1)}$ be defined as above, and $\psi ^{\mathcal {P}^h}$ be as defined in Eq. (4). Then $\langle \psi ^{\mathcal {P}^h}(\mathcal {S}(\mathcal {F}))\rangle$ and $\langle \psi ^{\mathcal {P}^h}(\text {Syz}(\mathcal {F}^h))\rangle$ are homogeneous subideals of $\langle \mathcal {P}^h \rangle \cap M^{(2,1)}$.

Proof

We show the statement for $\langle \psi ^{\mathcal {P}^h}(\text {Syz}(\mathcal {F}^h))\rangle$; the case of $\langle \psi ^{\mathcal {P}^h}(\mathcal {S}(\mathcal {F}))\rangle$ is similar. First note that $\psi ^{\mathcal {P}^h}(\text {Syz}(\mathcal {F}^h))$ is a group, as it is the image of a group under a group homomorphism. Secondly, for any element $\mathbf {a} = (a_1,\ldots ,a_m)\in \text {Syz}(\mathcal {F}^h)$, and any $r\in \overline{B}(n)$, we have $r\psi ^{\mathcal {P}^h}(\mathbf {a}) = \psi ^{\mathcal {P}^h}((ra_1,\ldots ,ra_m))$, where also $(ra_1,\ldots ,ra_m)\in \text {Syz}(\mathcal {F}^h)$. It follows that $\psi ^{\mathcal {P}^h}(\text {Syz}(\mathcal {F}^h))$ is indeed an ideal.

The inclusion $\langle \psi ^{\mathcal {P}^h}(\text {Syz}(\mathcal {F}^h))\rangle \subseteq \langle \mathcal {P}^h \rangle$ follows directly from the definition of $\psi ^{\mathcal {P}^h}$. For the other inclusion we note that, by construction, we can write $p_i^h = f_i^h + \sum _{j = 1}^t b_{i,j}q_j^h + \sum _{j,l = 0}^k c_{i,j,l}(v_jv_l)^h$, for all $1\le i \le m$ and for suitable constants $b_{i,j},c_{i,j,l}\in \mathbb {F}_2$, where $f_i^h$, $p_i^h$ are the polynomials of $\mathcal {F}^h$ and $\mathcal {P}^h$ respectively. When $\mathbf {a} \in \text {Syz}(\mathcal {F}^h)$, the $f_i^h$–parts in $\psi ^{\mathcal {P}^h}(\mathbf {a})$ will vanish, and we are left with a polynomial that can be generated from the elements of $V^2$ and $Q^1$. Hence we also have $\langle \psi ^{\mathcal {P}^h}(\text {Syz}(\mathcal {F}^h))\rangle \subseteq M^{(2,1)}$.

In particular, there is the following chain of ideals

$$\begin{aligned} \langle \psi ^{\mathcal {P}^h}(\mathcal {S}(\mathcal {F}))\rangle \subseteq \langle \psi ^{\mathcal {P}^h}(\text {Syz}(\mathcal {F}^h))\rangle \subseteq \langle \mathcal {P}^h\rangle \cap M^{(2,1)} \subseteq M^{(2,1)}. \end{aligned}$$

(9)

We now allow ourselves to be slightly informal, in order to see how this all relates in practice to the cases we are interested in. At each degree $\nu$, the dimension dim$_\nu (M^{(2,1)})$ of $M^{(2,1)}_\nu$ as a vector space over $\mathbb {F}_2$ can be seen as a measure of how much information the modifiers can hide. An interesting case from an attacker’s point of view is when $\langle \psi ^{\mathcal {P}^h}(\mathcal {S}(\mathcal {F}))\rangle _{\nu _0}$ has the maximal dimension dim$_{\nu _0}(\langle \psi ^{\mathcal {P}^h}(\mathcal {S}(\mathcal {F}))\rangle ) = \text {dim}_{\nu _0}(M^{(2,1)})$, for a relatively small $\nu _0$. While ‘excess’ polynomials in $\langle \psi ^{\mathcal {P}^h}(\mathcal {S}(\mathcal {F}))\rangle _{\nu _0}$ will sum to 0 in $\overline{B}(n)$, there is a chance that the corresponding inhomogeneous polynomials will result in degree fall polynomials when treated over B(n). In particular, this yields an upper bound $D_{ff}\le \nu _0$ on the first fall degree. We can do even better in practice.

Note that $(M^{(2,1)}\langle \mathcal {P}^h \rangle )_\nu$ will be a subspace of (the row space of) the Macaulay matrix $\overline{M}_\nu (\mathcal {P})$. As this matrix can be constructed by an attacker, we should count the possible combinations of polynomials from both $(M^{(2,1)}\langle \mathcal {P}^h \rangle )$ and the image of $\psi ^{\mathcal {P}^h}(\mathcal {S}(\mathcal {F}))$. Some caution is warranted when counting these combinations. For instance, $\psi ^{\mathcal {P}^h}(ms) \in M^{(2,1)}\langle \mathcal {P}^h \rangle$ for any $m\in M^{(2,1)}$ and $s\in \mathcal {S}(\mathcal {F})$, so we need to be careful in order to not count the same elements twice. For now we will keep up with our informal theme and denote ‘$M^{(2,1)}\langle \mathcal {P}^h\rangle$ modulo these collisions’ by $\mathcal {P}_{M^{(2,1)}}$. We will deal with it more properly when computing its dimension in Sect. 3.3. It is shown in Appendix A of [33] that $\langle \psi ^{\mathcal {P}^h}(\mathcal {T}(\mathcal {F}^h))\rangle \subseteq M^{(2,1)}\langle \mathcal {P}^h \rangle$, which is why we will focus on $\langle \psi ^{\mathcal {P}^h}(\mathcal {S}(\mathcal {F}))\rangle$ (as opposed to $\langle \psi ^{\mathcal {P}^h}(\text {Syz}(\mathcal {F}^h))\rangle$).

We now have everything needed to discuss estimates of the number of degree fall polynomials at different degrees. We start by assuming that none of the degree fall polynomials we get from $\mathcal {S}(\mathcal {F})$ (under $\psi ^{\mathcal {P}^h}$) can be reduced by lower–degree Macaulay matrices of $\mathcal {P}$. This allows us to directly use dim$_\nu (\mathcal {S}(\mathcal {F}))$. We furthermore add $\text {dim}_\nu (\mathcal {P}_{M^{(2,1)}})$, and subtract by dim$_\nu (M^{(2,1)})$. This yields the expression for our first estimate of degree fall polynomials, $N_\nu ^{(0,0)}$, at degree $\nu$:

$$\begin{aligned} \begin{aligned} N_\nu ^{(0,0)}&= \text {dim}_\nu (\mathcal {S}(\mathcal {F})) + \text {dim}_\nu (\mathcal {P}_{M^{(2,1)}}) - \text {dim}_\nu (M^{(2,1)}). \end{aligned} \end{aligned}$$

(10)

In a sense, $N_\nu ^{(0,0)}$ can be thought of as estimating the number of degree fall polynomials, as an effect of ‘over saturating’ $M^{(2,1)}_\nu$. When $N_\nu ^{(0,0)}$ is a positive number, this is the number of degree fall polynomials we expect to find (based on this effect); if $N_\nu ^{(0,0)}$ is negative, there is no such over saturation, and we do not expect any degree fall polynomials at degree $\nu$. The benefits of having the expression in Eq. (10) is that the study of the relatively complex polynomial system $\mathcal {P}^h$ can be broken down to studying three simpler systems. The dimensions of $M^{(2,1)}$ and $\mathcal {P}_{M^{(2,1)}}$ can, in particular, be further studied under the assumptions that the modifiers form a semi–regular system. In addition to being a reasonable assumption as the modifiers are randomly chosen, this is also the ideal situation for the legitimate user, as this maximizes the dimension of $M^{(2,1)}$. Indeed, the study of $M^{(2,1)}$ and $\mathcal {P}_{M^{(2,1)}}$ will be continued in the following subsections. Before that, we will generalize the ideas presented so far, arriving at several expressions that can be used to estimate the number of degree fall polynomials.

Generalised Estimates of Degree Fall Polynomials. Let $M^{(\alpha ,\beta )}\text {Syz}(\mathcal {F})$ denote the module $\{ ms | m\in M^{(\alpha ,\beta )}, s\in \text {Syz}(\mathcal {F})\}$ (which is well–defined since $\text {Syz}(\mathcal {F})$ is a $\overline{B}(n)$–module), and define

$$\begin{aligned} \mathcal {S}(\mathcal {F})_{M^{(\alpha ,\beta )}} := [M^{(\alpha ,\beta )}\text {Syz}(\mathcal {F})]/\mathcal {T}(\mathcal {F}). \end{aligned}$$

Instead of considering all the syzygies $\mathcal {S}(\mathcal {F})$, we can start with submodules of the form $\mathcal {S}(\mathcal {F})_{M^{(\alpha ,\beta )}}$. The benefit is that the ideal we need to ‘over saturate’ will now be $M^{(\alpha ,\beta )}M^{(2,1)}$. In Sect. 5 we will see several examples where this yields a better estimate than $N_\nu ^{(0,0)}$. Following through with this idea, along with the same considerations discussed prior to Eq. (10), we arrive at the following estimate for $\alpha , \beta \ge 0$:

$$\begin{aligned} \begin{aligned} N_\nu ^{(\alpha ,\beta )}&= \text {dim}_\nu (\mathcal {S}(\mathcal {F})_{M^{(\alpha ,\beta )}}) - \text {dim}_\nu (M^{(\alpha ,\beta )}M^{(2,1)}) \\&+ \text {dim}_\nu (\mathcal {P}^h_{M^{(\alpha ,\beta )}M^{(2,1)}}). \end{aligned} \end{aligned}$$

(11)

Recalling the convention that $M^{(0,0)} = \langle 1 \rangle$, this is indeed a generalisation of Eq. (10).

We now have several different estimates for degree fall polynomials, varying with the choice of $\alpha , \beta$. Any of these may be dominating, depending on the parameters of the scheme. The general estimate at degree $\nu$ is then taken to be their maximum:

$$\begin{aligned} N_{\nu } = \text {max}\{0,N_\nu ^{(\alpha ,\beta )}| 0\le \alpha \le k~ \text {and}~0\le \beta \le t\}. \end{aligned}$$

(12)

Note in particular that if $N_\nu = 0$, then all our estimates are non–positive, and we do not expect any degree fall polynomials at this degree.

Consider now the main assumptions underlying these estimates. Firstly, recall that we assumed that none of the degree fall polynomials that can be made from $\psi ^{\mathcal {P}}(\mathcal {S}(\mathcal {F})_{M^{(\alpha ,\beta )}})$ will be reduced to 0 when solving the system $\mathcal {P}$. Secondly, the formulas implicitly assume that all the polynomials in $M^{(\alpha ,\beta )}M^{(2,1)}$ need to be reduced before we can observe degree fall polynomials. The third assumption, concerning $\mathcal {P}^h_{M^{(\alpha ,\beta )}M^{(2,1)}}$, will be specified in Sect. 3.3.

Finally, we stress that the aim of this section has been to investigate one of the aspects that can lead to a system exhibiting degree fall polynomials. The estimates presented should not be used without care to derive arguments about lower bounds on the first fall degree. Nevertheless, we find that in practice these estimates and their assumptions seem to be reasonable. With the exception of a slight deviation in only two cases (see Sect. 4.3), the estimates lead to formulas that are able to describe all our experiments for the Dob encryption scheme that will be investigated in Sect. 4.

3.2 Dimension of the Modifiers

The estimate given in Eq. (11) requires knowledge of the dimension of (products of) the ideals $M^{(\alpha ,\beta )}$. These will in turn depend on the chosen modifications $V^\alpha$ and $Q^\beta$. In this section we collect various results that will be needed to determine these dimensions. We start with the following elementary properties.

Lemma 2

Consider $M^{(\alpha ,\beta )} = (V^\alpha +Q^\beta )$, and positive integers $\alpha _0, \alpha , \beta _0,\beta ,\nu$. Then the following holds:

• (i) $V^{\alpha _0}V^{\alpha } = V^{\alpha _0 + \alpha }$ and $Q^{\beta _0}Q^{\beta } = Q^{\beta _0 + \beta }$.

• (ii) $V^{\alpha _0}Q^{\beta _0} \subseteq V^{\alpha }Q^{\beta }$ if $\alpha \le \alpha _0$ and $\beta \le \beta _0$.

• (iii) $M^{(\alpha _0,\beta _0)}M^{(\alpha ,\beta )} = M^{(\alpha _0 + \alpha ,\beta _0 + \beta )} + V^{\alpha _0}Q^\beta + V^{\alpha }Q^{\beta _0}$.

• (iv) $\text {dim}_\nu (M^{(\alpha ,\beta )}) = \text {dim}_\nu (Q^\beta ) + \text {dim}_\nu (V^\alpha ) - \text {dim}_\nu (Q^\beta \cap V^\alpha ).$

• (v) $\begin{aligned}&\text {dim}_\nu (M^{(\alpha _0,\beta _0)}M^{(\alpha ,\beta )}) = \text {dim}_\nu (M^{(\alpha _0 + \alpha ,\beta _0 + \beta )}) + \text {dim}_\nu (V^{\alpha _0}Q^\beta ) \\&+ \text {dim}_\nu (V^{\alpha }Q^{\beta _0}) - \text {dim}_\nu (M^{(\alpha _0 + \alpha ,\beta _0 + \beta )}\cap V^{\alpha _0}Q^\beta ) \\&- \text {dim}_\nu (M^{(\alpha _0 + \alpha ,\beta _0 + \beta )}\cap V^{\alpha }Q^{\beta _0}) - \text {dim}_\nu (V^{\alpha _0}Q^\beta \cap V^{\alpha }Q^{\beta _0}) \\&+ \text {dim}_\nu (M^{(\alpha _0 + \alpha ,\beta _0 + \beta )} \cap V^{\alpha _0}Q^\beta \cap V^{\alpha }Q^{\beta _0}). \end{aligned}$

Proof

Properties (i) – (iv) follow from the appropriate definitions in a straightforward manner; we give a brief sketch of property (v) here. From property (iii) we know that $M^{(\alpha _0,\beta _0)}M^{(\alpha ,\beta )}$ can be written as the sum of the three ideals $M^{(\alpha _0 + \alpha ,\beta _0 + \beta )}$, $V^{\alpha _0}Q^\beta$ and $V^{\alpha }Q^{\beta _0}$. We start by summing the dimension of each of these three ideals individually. Any polynomial belonging to exactly two of these subideals is now counted twice, which is why we subtract by the combinations intersecting two of these ideals. Lastly, a polynomial belonging to all three of the subideals will, at this point, have been counted thrice, and then subtracted thrice. Hence, we add the dimension of intersecting all three subideals.

The dimension dim$_\nu (V^\alpha )$ can be further inspected using the following result.

Lemma 3

Suppose that $v_1,\ldots ,v_k$ are k linearly independent linear forms in $\overline{B}(n)$. Then

$$\begin{aligned} \text {dim}_\nu (V^\alpha ) = \sum _{\begin{array}{c} i\ge \alpha , j \ge 0\\ i + j = \nu \end{array}} \left( {\begin{array}{c}k\\ i\end{array}}\right) \left( {\begin{array}{c}n - k\\ j\end{array}}\right) \end{aligned}$$

(13)

holds under the conventions that $\left( {\begin{array}{c}a\\ b\end{array}}\right) = 0$ if $b > a$, and $\left( {\begin{array}{c}a\\ 0\end{array}}\right) = 1$.

Proof

As $v_1,\ldots ,v_k$ are linearly independent, we can choose $n-k$ linear forms of $\overline{B}(n)$, $w_{k+1},\ldots ,w_n$, that constitute a change of variables

$$\begin{aligned} \overline{B}(n)\simeq \overline{B}' = \mathbb {F}_2[v_1,\ldots ,v_k,w_{k+1},\ldots w_n]/\langle v_1^2,\ldots , w_n^2\rangle . \end{aligned}$$

For any monomial $\gamma \in \overline{B}'$, we will define deg$_v(\gamma )$ as its degree in the $v_1,\ldots ,v_k$-variables, and deg$_w(\gamma )$ as its degree in the variables $w_{k+1},\ldots ,w_n$. The elements of $V^{\alpha }$ of (total) degree $\nu$, is now generated (in $\overline{B}'$ as an $\mathbb {F}_2$–vector space) by all monomials $\gamma$ such that deg$_v(\gamma ) \ge \alpha$ and deg$_v(\gamma )$ + deg$_w(\gamma ) = \nu$. The number of all such monomials are counted in Eq. (13).

When $q_1^h,\ldots ,q_t^h$ forms a $D_0$–Semi–regular system, we need only be concerned with the trivial syzygies when counting dim$_\nu (Q^1)$, for $\nu < D_0$. For the particular cases we are interested in, this amounts to dim$_3(Q^1) = tn$, dim$_4(Q^1) = t\left( {\begin{array}{c}n\\ 2\end{array}}\right) - [\left( {\begin{array}{c}t\\ 2\end{array}}\right) + t]$ and dim$_5(Q^1) = t\left( {\begin{array}{c}n\\ 3\end{array}}\right) - n[\left( {\begin{array}{c}t\\ 2\end{array}}\right) + t]$.

Lemma 4

Suppose that $(v_1,\ldots ,v_k,q_1,\ldots ,q_t)$ is $D_0$–semi–regular, and consider $1\le \alpha \le k$ and $1\le \beta \le t$. Then

$$\begin{aligned} (V^\alpha \cap Q^\beta )_\nu = (V^\alpha Q^\beta )_\nu , \end{aligned}$$

holds for all $\nu < D_0$.

Proof

(Sketch) The product of any pair of ideals is contained in their intersection. For the other direction, consider a non–trivial element $e \in (V^\alpha \cap Q^\beta )_\nu$. Then, for some polynomials $f_i$, $g_j$, we can write $e = \sum f_iq_{i_1}^h\cdots q_{i_\beta }^h \in Q_\nu ^\beta$, and $e = \sum g_jv_{j_1}\cdots v_{j_\alpha } \in V_\nu ^\alpha$, which yields the syzygy

$$\begin{aligned} \sum f_i(q_{i_1}^h\cdots q_{i_\beta }^h) + \sum g_j(v_{j_1}\cdots v_{j_\alpha })^h = 0. \end{aligned}$$

By assumption, all syzygies of degree $< D_0$ of $(v_1,\ldots ,v_k,q_1^h,\ldots ,q_t^h)$ will be generated by the field and Koszul syzygies of the $v_i$– and $q_j^h$–polynomials. It follows that (after possibly reducing by syzygies generated by only $q_1^h,\ldots ,q_t^h$) we have $f_i\in V^{\alpha }$. Similarly, we have $g_j\in Q^\beta$. In particular, $e\in V^\alpha Q^\beta$.

A general characterisation of the ideal $V^\alpha Q^\beta$ is trickier. We are content with discussing some special cases of its dimension, which will be of interest to us.

Example 1

Suppose that $(v_1,\ldots ,v_k,q_1,\ldots ,q_t)$ is $D_0$–semi–regular, and let $1\le \alpha \le k$ and $1\le \beta \le t$.

• (a) The generators of $V^\alpha Q^\beta$ are of degree $\alpha \,+\, 2\beta$, hence dim$_\nu (V^\alpha Q^\beta ) = 0$ for all $\nu < \alpha + 2\beta$. (This also holds without the $D_0$–semi–regularity assumption).

• (b) Suppose furthermore that $D_0 > \alpha + 2\beta + 1$. Then dim$_{(\alpha + 2\beta + 1)}(V^\alpha Q^\beta ) = \left( {\begin{array}{c}t\\ \beta \end{array}}\right) \text {dim}_{\alpha + 1}(V^\alpha )$. To see this, note that $\langle V^\alpha Q^\beta \rangle _{\alpha + 2\beta + 1}$ is generated by elements of the form $v_{l_1}\ldots v_{l_\alpha }q_{c_1}\ldots q_{c_\beta }x_r$, where $1\le l_1< \ldots < l_\alpha \le k$, $1\le c_1< \ldots < c_\beta \le t$ and $1\le r\le n$. The semi–regularity assumption assures that there will be no cancellations (save for the ones already accounted for in $\text {dim}_{\alpha + 1}(V^\alpha )$).

• (c) Suppose furthermore that $D_0 > \alpha + 2\beta + 2$, then dim$_{(\alpha + 2\beta + 2)}(V^\alpha Q^\beta ) = \left( {\begin{array}{c}t\\ \beta \end{array}}\right) \text {dim}_{\alpha + 2}(V^\alpha ) - \left( {\begin{array}{c}k\\ \alpha \end{array}}\right) \big [\left( {\begin{array}{c}t\\ \beta \end{array}}\right) t - \left( {\begin{array}{c}t\\ \beta + 1\end{array}}\right) \big ]$. The reasoning is similar to (b), with the difference that $\text {dim}_{\alpha + 2}(V^\alpha )$ will now include the polynomials of the form $q_c^h(v_{l_1}\ldots v_{l_{\alpha }})^h$. There are $\left( {\begin{array}{c}k\\ \alpha \end{array}}\right) \big [\left( {\begin{array}{c}t\\ \beta \end{array}}\right) t - \left( {\begin{array}{c}t\\ \beta + 1\end{array}}\right) \big ]$ combinations of these that will reduce to 0 over $\overline{B}(n)$ (when multiplied with the combinations $q_{c_1}^h\ldots q_{c_\beta }^h$).

3.3 Dimension of $\mathcal {P}_{M^{(\alpha ,\beta )}M^{(2,1)}}$

As noted in Sect. 3.1, we want $\mathcal {P}_{M^{(\alpha ,\beta )}M^{(2,1)}}$ to be $M^{(\alpha ,\beta )}M^{(2,1)}\langle \mathcal {P}^h\rangle$, modulo the polynomials of the form $\psi ^{\mathcal {P}^h}(ms)$, for $ms\in \mathcal {S}(\mathcal {F})_{M^{(\alpha ,\beta )}M^{(2,1)}}$. Computing the dimension of $(M^{(\alpha ,\beta )}M^{(2,1)}\langle \mathcal {P}^h\rangle )_\nu$ directly might be difficult, seeing that $\mathcal {P}^h$ depends on $M^{(2,1)}$. To tackle this, we start with the assumption that the cancellations in $M^{(\alpha ,\beta )}M^{(2,1)}\langle \mathcal {P}^h\rangle$ are only generated by the ‘generic’ cancellations, and cancellations coming from the underlying structure, depending on $\mathcal {F}$. By ‘generic’ cancellations we mean those generated by the Koszul– or field syzygies in either the $p_i^h$– or $m_j$–polynomials. The assumption furthermore implies that the second type of cancellations will lie in the image of $\psi ^{\mathcal {P}^h}(\mathcal {S}(\mathcal {F})_{M^{(\alpha ,\beta )}M^{(2,1)}})$. Let $\mathcal {G}_{SR}$ be a system of homogeneous quadratic polynomials, of the same size and number of variables as $\mathcal {P}^h$, such that $\{V^1,Q^1,\mathcal {G}_{SR}\}$ forms a semi–regular system. With the assumption outlined above, we have

$$\begin{aligned} \text {dim}_\nu (\mathcal {P}_{M^{(\alpha ,\beta )}M^{(2,1)}}) = \text {dim}_\nu (M^{(\alpha ,\beta )}M^{(2,1)}\mathcal {G}_{SR}) - \text {dim}_\nu (\mathcal {S}(\mathcal {F})_{M^{(\alpha ,\beta )}M^{(2,1)}}). \end{aligned}$$

(14)

Indeed, any would–be cancellations that are over–counted in the term $\text {dim}_\nu (M^{(\alpha ,\beta )}M^{(2,1)}\mathcal {G}_{SR})$ would be subtracted in $- \text {dim}_\nu (\mathcal {S}(\mathcal {F})_{M^{(\alpha ,\beta )}M^{(2,1)}})$.

$\mathcal {S}(\mathcal {F})_{M^{(\alpha ,\beta )}M^{(2,1)}}$ requires knowledge of the underlying central map, $\mathcal {F}$, and will be dealt with in the next section. Computing the dimensions of the product ideal $M^{(\alpha ,\beta )}M^{(2,1)}\mathcal {G}_{SR}$ has many similarities with the work that was done in the previous subsection. In particular, the dimension at degree $\nu$ is zero if the degrees of all of its generators are $> \nu$. We conclude with the following short example, which covers the other cases that will be the most relevant to us.

Example 2

Let $\mathcal {G}_{SR}$ be a system of d homogeneous quadratic polynomials over $\overline{B}(n)$, such that $\{V^1,Q^1,\mathcal {G}_{SR}\}$ forms a semi–regular system. Then

$$\begin{aligned} \text {dim}_\nu (M^{(2,1)}\mathcal {G}_{SR}) = n\big [\text {dim}_{\nu - 2}(Q^1) + \text {dim}_{\nu - 2}(V^2)\big ], \end{aligned}$$

holds for $\nu = 4,5$.

4 Number of Degree Fall Polynomials in the Dob Encryption Scheme

There are several ways to construct a central map $\mathcal {F}:\mathbb {F}_{2}^d\rightarrow \mathbb {F}_{2}^d$. For big–field schemes, the idea is to fix an isomorphism $\phi :\mathbb {F}_2^d \rightarrow \mathbb {F}_{2^d}$ between the vector space over the base field and the extension field, and choose two random invertible $d\times d$-matrices over $\mathbb {F}_2$, called S and T. $\mathcal {F}$ is then constructed as the composition $\mathcal {F}=S\circ \phi ^{-1}\circ F\circ \phi \circ T$, where $F(X)\in \mathbb {F}_{2^d}[X]$, max$_{w_2}(F)=2$, and such that $F(X) = Y$ is easy to solve for any given Y. In particular, this ensures that $\mathcal {F}$ is a system of d quadratic polynomials, and ciphertexts can easily be decrypted with the knowledge of the secret S, T and F. There are two main ways in the literature to construct F with these properties:

• 1. $F(X)=X^e$, where $w_2(e) = 2$. This is the case for $C^{*}$ [21].

• 2. $F(X)=\sum _{i=0}^t c_iX^{e_i}$, where we have $w_2(e_i)\le 2$ for all i, and each $e_i$ is bounded by a relatively small constant b. This is used in HFE [24].

Indeed, both $C^*$ and HFE have been suggested with the ip–modification, known as PMI an ipHFE, respectively [8, 12]. These schemes were broken in [14, 17], by specialised attacks recovering the kernel of the linear forms of the ip–modification. Nevertheless, a later version of the $C^{*}$ variant, PMI$+$ [9], also added the $``+"$ modification in order to thwart this attack, and remains unbroken. We note that ipHFE, PMI and PMI$+$ all fits into the framework presented in Sect. 3, and the techniques presented here can be used to understand their resistance against algebraic attacks (recall that the $``+"$ modification does not increase the security versus algebraic attacks). A comprehensive study of these schemes are beyond the scope of this work, as we focus on a newer construction that utilizes both the ip– and $Q_+$–modification.

4.1 The Dob Encryption Scheme

The Two–Face family, introduced in [20], presents a third way to construct a function F(X). Writing $Y=F(X)$, we get the polynomial equation

$$\begin{aligned} E_1(X,Y) = Y + F(X) = 0. \end{aligned}$$

When F has the Two–Face property, it can be transformed into a different polynomial $E_2(X,Y)=0$, which has low degree in X and have 2–weight at most 2 for all exponents in X. The degree of $E_2$ in Y can be arbitrary. Given Y, it is then easy to compute an X that satisfies $E_2(X,Y)=0$, or equivalently, $Y=F(X)$.

For a concrete instantiation, the authors of [20] suggest the polynomial

$$\begin{aligned} F(X) = X^{2^m+1}+X^3+X, \end{aligned}$$

(15)

where $d=2m-1$. Dobbertin showed in [13] that F is a permutation polynomial. In [20], based on the results of [13], it is further pointed out that

$$\begin{aligned} E_2(X,Y) = X^9+X^6Y+X^5+X^4Y+X^3(Y^{2^m}+Y^2)+XY^2+Y^3=0 \end{aligned}$$

holds for any pair $Y=F(X)$. Note that F itself has high degree in X, but the highest exponent of X found in $E_2$ is 9 and all exponents have 2–weight at most 2.

The public key $\mathcal {F}$ associated with Eq. (15) under the composition described at the beginning of Sect. 4 is called nude Dob, and was observed in [20] to be weak. More precisely, experiments show that the associated multivariate system has solving degree three. Indeed, in Appendix D of [33] is is shown that this is the case for any d.

The (full) Dob encryption scheme is made by extending nude Dob with the two modifications, $Q_+$ and ip, as described at the beginning of Sect. 3. The public key is the d quadratic polynomials $\mathcal {P}$, constructed according to Eq. (6). The secret key consists of $S,T,H_{ip}$ and $H_{Q_+}$. The plaintext space of the scheme is $\mathbb {F}_2^d$ and encryption is done by evaluating $y=\mathcal {P}(x)$, producing the ciphertext y.

To decrypt, the receiver of a ciphertext y guesses on the values of $v_i(x)$ and $q_j(x)$ for all $1\le i\le k$ and $1\le j\le t$, and computes the corresponding values of the polynomials in $H_{ip}$ and $H_{Q_+}$. These values are added to y, removing the effect of the modifiers when the guess is correct. The resulting value $y'$ is then the ciphertext of the nude Dob. This can be decrypted by first multiplying $y'$ with $S^{-1}$, resulting in Y from the central mapping, which is then inverted using $E_2$ and multiplied with $T^{-1}$ to recover the candidate plaintext $x_0$. The initial guess is then verified by checking if all $v_i(x_0)$ and $q_j(x_0)$ indeed evaluate to the guessed values.

In order for decryption to have an acceptable time complexity, the size of the modifications, k and t, can not be too large. To decrypt a ciphertext one must on the average do $2^{k+t-1}$ inversions of $\mathcal {P}$ before the correct plaintext is found. In [20] it is suggested to use $k=t=6$ for 80–bit security.

For the remainder of this work, we let $\mathcal {F}$ and $\mathcal {P}$ denote the public keys of nude Dob and the (full) Dob encryption scheme, respectively.

4.2 Syzygies of the Unmodified Dob Scheme

The goal of this subsection is to estimate the dimension of $\mathcal {S}(\mathcal {F})_\nu$, for $\nu = 3,4,5$. We start by inspecting F (Eq. (15)) over the extension field $\mathbb {F}_{2^{d}}[X]/\langle X^{2^{d}} + X\rangle$. Note that max$_{w_2}(F)=2$, and consider the following polynomials:

$$\begin{aligned} G_1 = XF \qquad \quad \text {and} \qquad \quad G_2 = (X^{2^m} + X^2)F. \end{aligned}$$

(16)

One finds that $G_1$ and $G_2$ are both products of F and a polynomial of 2–weight one, but the resulting polynomials still have max$_{w_2}(G_i)=2$. They are then examples of polynomials satisfying Eq. (5) from Sect. 2.1, and will correspond to 2d degree fall polynomials at degree three, down to quadratic polynomials. They form all the syzygies we expect at degree three, hence we set

$$\begin{aligned} \text {dim}_3(\mathcal {S}(\mathcal {F})) = 2d. \end{aligned}$$

(17)

Recall that it was noted in [20] that experiments of nude Dob had a solving degree of three, though the authors did not provide a proof that this is always the case. The presence of $G_1$ and $G_2$ ensures that the first fall degree of nude Dob is three. A complete proof that the solution of nude Dob can be found by only considering polynomials of degree three is a little more involved, and is provided in Appendix D of [33].

Things get more complicated for dimensions $\nu > 3$. While we expect the two polynomials $G_1$ and $G_2$ to generate a significant part of the syzygies, we also expect there to be other generators, as well as cancellations to keep track of. Due to the complexity of fully characterizing the higher degree parts of $\mathcal {S}(\mathcal {F})$, we instead found an expression for its dimension at degrees $\nu = 4,5$ experimentally. The experimental setup is further described at the end of this subsection. Note that the formulas we present in this subsection will be a multiple of d. This strongly suggests that all the syzygies of the system come from its extension field structure. These relations could then, in principle, be written out analytically as was the case for $\nu = 3$. In particular, this makes it reasonable to expect the formulas to continue to hold for larger values of d (i.e., beyond our experimental capabilities).

In the subsequent formulas we introduce the following notation, which will be useful to us later. Whenever counting the syzygies that can be generated from syzygies of lower degree, we will multiply by n (the number of variables in an associated multivariate system), as opposed to d. For instance, let $(g_{i,1}\ldots ,g_{i,d})$, $1\le i \le d$ denote the d multivariate syzygies associated with $G_1$. Then $x_j(g_{i,1}\ldots ,g_{i,d})$, $1\le j\le n$ are syzygies at $\nu = 4$, and we will count all of these as³ nd. For the Dob encryption scheme we of course have $n = d$, so this distinction may seem unnecessary at the moment, but later, in Sect. 5, we will also consider the case $n < d$ as an attacker may fix certain variables.

For $\nu = 4$, we find the following expression:

$$\begin{aligned} \text {dim}_4(\mathcal {S}(\mathcal {F})) = (2n-1)d, \end{aligned}$$

(18)

where we note that the term 2nd has been generated by $G_1$ and $G_2$, as described above.

For $\nu = 5$, we have

$$\begin{aligned} \text {dim}_5(\mathcal {S}(\mathcal {F})) = \bigg (2\left( {\begin{array}{c}n\\ 2\end{array}}\right) - n - 2d - 20\bigg )d. \end{aligned}$$

(19)

Once more, some of these terms can be understood from the syzygies of lower degrees. The contribution from the polynomials $G_1$ and $G_2$ from $\nu = 3$ will now be the $2\left( {\begin{array}{c}n\\ 2\end{array}}\right) d$ term. The term ‘$-d$’ from $\nu = 4$ will now cause the ‘$-nd$’ term.

Experimental Setup. The experiments used to test Eq. (18) and Eq. (19) have been done as follows. The public polynomials of nude Dob are first generated, and we consider their upper homogeneous part, $\mathcal {F}^h$, over $\overline{B}(d)$. Dim$_\nu (\mathcal {S}(\mathcal {F}))$ is computed as the dimension of the kernel of the homogeneous Macaulay matrix $\overline{M}_\nu (\mathcal {F}^h)$, minus dim$_\nu (\mathcal {T}(\mathcal {F}^h))$. For $\nu = 4,5$ we tested all odd d, $25 \le d \le 41$, all matching the values predicted by Eq. (18) and Eq. (19).

4.3 Degree Fall Polynomials of the (modified) Dob Scheme

We now have all the tools needed to write out explicit formulas for (variants of) the estimates $N_\nu ^{(\alpha ,\beta )}$, $\nu \le 5$, for the Dob scheme. The approach for the formulas is as follows. Equation (11) is used as a foundation, and dim$_\nu (\mathcal {S}(\mathcal {F}))$ is given according to Sect. 4.2. For the dimension of the modifiers, and $\mathcal {P}_{M^{(\alpha ,\beta )}M^{(2,1)}}$, we will combine the results discussed in Sect. 3.2 and Sect. 3.3. In particular, we will assume that the chosen modifying polynomials $\{v_1,\ldots ,v_k,q_1,\ldots ,q_t\}$ form a $(\nu + 1)$–semi–regular system. The dimensions that are not covered by combining the results discussed so far, will be commented on separately. For the convenience of the reader, the non–trivial dimensions have been marked with an overbrace in the equations. The exceptions are Eq. (24) and Eq. (25), which are covered in greater depth in Appendix B of [33]. Recall also our convention that $\left( {\begin{array}{c}a\\ b\end{array}}\right) = 0,$ if $b > a$, and $\left( {\begin{array}{c}a\\ 0\end{array}}\right) = 1$.

$\varvec{\nu = 3.}$ At this degree we only consider $N^{(0,0)}$.

$$\begin{aligned} \begin{aligned} N^{(0,0)}_3&= \overbrace{2d}^{\text {dim}_3(\mathcal {S}(\mathcal {F}))} - \overbrace{\bigg ( (n-k)\left( {\begin{array}{c}k\\ 2\end{array}}\right) + \left( {\begin{array}{c}k\\ 3\end{array}}\right) \bigg )}^{\text {dim}_3(V^2)} - \overbrace{nt}^{\text {dim}_3(Q^1)}. \end{aligned} \end{aligned}$$

(20)

$\varvec{\nu = 4.}$

$$\begin{aligned} \begin{aligned} N^{(0,0)}_4&= \overbrace{(2n - 1)d}^{\text {dim}_4(\mathcal {S}(\mathcal {F}))} + \overbrace{d\bigg (t + \left( {\begin{array}{c}k\\ 2\end{array}}\right) \bigg )}^{\text {dim}_4(\mathcal {P}_{M^{(2,1)}})} - \overbrace{\bigg ( t\left( {\begin{array}{c}n\\ 2\end{array}}\right) - \left( {\begin{array}{c}t\\ 2\end{array}}\right) -t \bigg )}^{\text {dim}_4(Q^1)} \\&- \overbrace{\bigg (\left( {\begin{array}{c}k\\ 2\end{array}}\right) \left( {\begin{array}{c}n-k\\ 2\end{array}}\right) + \left( {\begin{array}{c}k\\ 3\end{array}}\right) (n-k) + \left( {\begin{array}{c}k\\ 4\end{array}}\right) \bigg )}^{\text {dim}_4(V^2)} + \overbrace{t\left( {\begin{array}{c}k\\ 2\end{array}}\right) }^{\text {dim}_4(Q^1\cap V^2)}. \end{aligned} \end{aligned}$$

(21)

At $\nu = 4$, we also consider the estimate $N_4^{(1,0)}$, i.e., multiplying everything with the k linear forms from the ip–modifier. In particular, this means that $(\mathcal {S}(\mathcal {F})_{M^{(1,0)}})_4$ is spanned by the combinations $v_j^h(g_{i,1}\ldots ,g_{i,d})$, $1\le j \le k$ and $1\le i \le 2d$, where we recall that $(g_{i,1}\ldots ,g_{i,d})$ denote the 2d multivariate syzygies associated with $G_1$ and $G_2$ (Eq. (16))

$$\begin{aligned} \begin{aligned} N_4^{(1,0)}&= \overbrace{2kd}^{\text {dim}_4\left( \mathcal {S}(\mathcal {F})_{M^{(1,0)}}\right) } - \overbrace{\bigg (\left( {\begin{array}{c}k\\ 3\end{array}}\right) (n-k) + \left( {\begin{array}{c}k\\ 4\end{array}}\right) \bigg )}^{\text {dim}_4(V^3)} \\&- \overbrace{t\bigg (k(n-k) + \left( {\begin{array}{c}k\\ 2\end{array}}\right) \bigg )}^{\text {dim}_4(Q^1V^1)}. \end{aligned} \end{aligned}$$

(22)

$\varvec{\nu = 5.}$ At degree 5, $\mathcal {S}(\mathcal {F})_{M^{(2,1)}}$ (in Eq. (14)) is no longer trivial. Indeed, it will now consist of the possible combinations $v_{j_1}^hv_{j_2}^h(g_{i,1}\ldots ,g_{i,d})$ and $q_j^h(g_{i,1}\ldots ,g_{i,d})$.

$$\begin{aligned} \begin{aligned} N^{(0,0)}_5&= \overbrace{\bigg (2\left( {\begin{array}{c}n\\ 2\end{array}}\right) - n - 2d - 20\bigg )d}^{\text {dim}_5(\mathcal {S}(\mathcal {F}))} - \overbrace{\bigg ( t\left( {\begin{array}{c}n\\ 3\end{array}}\right) - n\left( {\begin{array}{c}t\\ 2\end{array}}\right) - tn\bigg )}^{\text {dim}_5(Q^1)} \\&- \overbrace{\bigg (\left( {\begin{array}{c}k\\ 2\end{array}}\right) \left( {\begin{array}{c}n-k\\ 3\end{array}}\right) + \left( {\begin{array}{c}k\\ 3\end{array}}\right) \left( {\begin{array}{c}n-k\\ 2\end{array}}\right) + \left( {\begin{array}{c}k\\ 4\end{array}}\right) (n-k) + \left( {\begin{array}{c}k\\ 5\end{array}}\right) \bigg )}^{\text {dim}_5(V^2)} \\&+ \overbrace{t\bigg ( \left( {\begin{array}{c}k\\ 2\end{array}}\right) (n-k) + \left( {\begin{array}{c}k\\ 3\end{array}}\right) \bigg )}^{\text {dim}_5(Q^1\cap V^2)} \\&+ \overbrace{ntd + d\bigg (\left( {\begin{array}{c}k\\ 2\end{array}}\right) (n-k) + \left( {\begin{array}{c}k\\ 3\end{array}}\right) \bigg ) - 2dt - 2d\left( {\begin{array}{c}k\\ 2\end{array}}\right) }^{\text {dim}_5\left( \mathcal {P}_{M^{(2,1)}}\right) }. \end{aligned} \end{aligned}$$

(23)

As mentioned above, it is a bit more involved to derive $N_5^{(1,1)}$ and $N_{5}^{(2,1)}$, and we will refer to Appendix B of [33] for more details. It would also appear that our assumptions are slightly off for these two estimates, as our experiments consistently yield 4d more degree fall polynomials than we are able to predict (see Remark 3, Appendix B of [33] for more details). We present the experimentally adjusted versions in Eqs. (24) and (25):

$$\begin{aligned} \begin{aligned} N_5^{(1,1)}&= d\bigg (k(2n - k - 2) + t(2 + k) + \left( {\begin{array}{c}k\\ 3\end{array}}\right) + 4\bigg ) - \left( {\begin{array}{c}t\\ 2\end{array}}\right) n - \left( {\begin{array}{c}k\\ 3\end{array}}\right) \left( {\begin{array}{c}n-k\\ 2\end{array}}\right) \\&- \left( {\begin{array}{c}k\\ 5\end{array}}\right) - \left( {\begin{array}{c}k\\ 4\end{array}}\right) (n-k) - t\bigg (k\left( {\begin{array}{c}n-k\\ 2\end{array}}\right) + \left( {\begin{array}{c}k\\ 2\end{array}}\right) (n-k) - kt\bigg ). \end{aligned} \end{aligned}$$

(24)

$$\begin{aligned} \begin{aligned} N_{5}^{(2,1)}&= 2d\bigg (\left( {\begin{array}{c}k\\ 2\end{array}}\right) + t + 2\bigg ) - \bigg (\left( {\begin{array}{c}k\\ 4\end{array}}\right) (n-k) + \left( {\begin{array}{c}k\\ 5\end{array}}\right) \bigg ) \\&- t\bigg (\left( {\begin{array}{c}k\\ 2\end{array}}\right) (n-k) + \left( {\begin{array}{c}k\\ 3\end{array}}\right) \bigg ) - \left( {\begin{array}{c}t\\ 2\end{array}}\right) n. \end{aligned} \end{aligned}$$

(25)

5 Experimental Results on Degree Fall Polynomials

In the previous section we developed the theory on how to estimate the number of first fall polynomials, ending up with several formulas. This section is focused on the accuracy of these formulas, and how they can be used by an attacker. Note that since we are interested in the unique structure of the Dob encryption scheme, we will always assume that ‘generic’ degree fall polynomials do not interfere. More specifically, when inspecting a system of d polynomials in n variables at degree $\nu$, we assume that d and n is chosen such that $D_{reg}(d,n) > \nu$.

5.1 Fixing Variables

The formulas separate d, the size of the field extension, and n, the number of variables. While the Dob encryption scheme uses $d = n$, an attacker can easily create an overdetermined system with $n < d$ by fixing some variables. This approach, known as the hybrid method, can be viewed as a trade–off between exhaustive search and Gröbner basis techniques, and its benefits are well–known for semi–regular sequences [3]. From Eqs. (20) to (25), we find that for the relevant choices of parameters (d, t, k), a greater difference between n and d can increase the number of degree fall polynomials. This means that a hybrid method will have a more intricate effect on a Dob system, than what we would expect from random systems. To a certain extent, an attacker can “tune" the number of degree fall polynomials, by choosing the amount of variables to fix. Of course, if the intent is to find a solution of the polynomial system through a Gröbner basis, this comes at the added cost of solving the system $2^{r}$ times, where r is the number of fixed variables, but in Sect. 6 we will present a different attack that circumvents this exponential factor.

Finally, one could ask whether it is reasonable to expect Eqs. (20) to (25) to be accurate after fixing a certain number of variables. It is, for instance, possible that different degree fall polynomials will cancel out, as certain variables are fixed. However, if past experience with the hybrid method is any indicator, such cancellations are very rare, and we see no reason that the extension field structure increases the probability for such cancellations to happen. As we will see in Sect. 5.3 this is supported by the experiments we have run; the formulas remain precise, even as n is varied.

5.2 Using the Degree Fall Formulas

We briefly recall how the formulas found in Sect. 4.3 relate to the public polynomials of a Dob encryption scheme. Let $\mathcal {P}$ be the polynomial system associated with a Dob scheme of fixed parameters (d, n, t, k) (where n is as described in Sect. 5.1). We expect the non–trivial dimension (i.e., the dimension of the part that is not generated by $\mathcal {T}(\mathcal {F})$) of the kernel of $\overline{M}_\nu (\mathcal {P})$ to be given by the maximal of the formulas $N_\nu ^{(\alpha ,\beta )}$, for $\nu = 3,4,5$.

If a step–wise algorithm such as F$_4$ is used, we expect the formulas to predict the number of degree falls polynomials, but only at the first fall degree. Suppose, for instance, that $N_3 = 0$, but $N_4 > 0$. Then this algorithm runs a second step at degree 4, using the newly found degree fall polynomials. This means that there are effectively more available polynomials in the system when (if) a step of degree 5 is performed, and in this case we do not expect the formulas we have for $N_5$ to be accurate.

Note in particular that if all the formulas we have are non–positive, an attacker is likely required to go up to step degree $\ge 6$ in order to observe first fall polynomials.

5.3 Experimental Results

We have run a number of experiments with the Dob system of varying parameters (d, n, t, k). A subset of them is presented in Table 2, and the rest can be found in Appendix G of [33]. Gröbner bases of the systems were found using the F$_4$ algorithm implemented in the computational algebra system Magma. The script used for the experiments is available at [19].

In Table 2 we use the following notation. ‘$D_{ff}$’ is the experimentally found first fall degree. ‘N (predicted)’ is the number of first fall polynomials as predicted by the equations in Sect. 4.3. ‘N (Magma)’ is the number of first fall polynomials read from the verbose output of Magma, written as ‘$\text {degree} : \{ \# \text {degree fall polynomials at this degree}\}$’. The solving degree $D_{solv}$ was found experimentally by Magma. This has been measured as the degree where the most time consuming step of the algorithm took place. In the instances where the algorithm did not run to completion due to memory constraints, we give $D_{solv}$ as $\ge X$, where X is the degree of the step where termination occurred. The degree of regularity for semi–regular systems of the same size, $D_{reg}(d,n)$, is also given. ‘Step Degrees’ lists the degrees of the steps that are being performed by F$_4$ up until linear relations are found. Once a sufficient number of linear relations are found, Magma restarts F$_4$ with the original system, as well as these linear relations. This restart typically needs a few rounds before the entire basis is found, but its impact on the running time of the algorithm is negligible, which is why we have chosen to exclude it when listing the step degrees. For convenience, the step where first fall polynomials are found is marked in and the solving step marked in . is used to mark the steps where these two coincide.

Table 2. Degree fall polynomials for Dob encryption schemes of various parameters.

A first observation is that in all experiments we find that ‘N (predicted)’ matches ‘N (Magma)’. We also find that fixing variables affects the cross–over point between the formulas $N^{(\alpha ,\beta )}_\nu$, as for instance seen in the rows 6 and 7. We note that $N_\nu ^{(0,0)}$ tend to be dominant when $n<< d$, and that $N_5^{(2,1)}$ only seems to have an impact when k is large and t is small.

For the majority of cases we observe that $D_{ff} = D_{solv}$ or $D_{solv} + 1$, but one should be careful in drawing any conclusions from this, seeing that our experiments are in practice limited to computations of $D < 6$. The relation between n and $D_{solv}$ is also noteworthy. For instance, in row 9 we have $d = 57$ and $n = 38$; $D_{ff}$ is 5, but $D_{solv} \ge 6$. In row 10 we fix one more variable, $n = 37$ (while keeping everything else as before), and find $D_{solv} = 5$.

Impact on Known Attacks. The solving degree of big field schemes are often estimated using the first fall degree. In cases where $D_{solv}> D_{ff}$, we observed instances where it is beneficial for an attacker to fix (a few) variables in order to lower the $D_{solv}$ for each guess. Without a better understanding of $D_{solv}$ and how it is affected by fixing variables, it seems that the approximation $D_{ff} \approx D_{solv}$ is conservative, yet reasonable, when estimating the complexity of direct/hybrid attacks against Dob system.

Another attack that may greatly benefit from the detailed formulas for degree fall polynomials obtained in Sect. 3, is an adapted version of the distinguishing attack that was proposed for HFEv- (Section 5 in [11]). An attacker fixes random linear forms, and distinguishes between the cases where (some of) the fixed linear forms are in the span of $(v_1,\ldots ,v_k)$, and when none of them are, by the use of Gröbner basis techniques. Indeed, if one of the fixed linear forms are in this span, the number of degree fall polynomials will be the same as for a system with $k - 1$ ip linear forms. Hence, a distinguisher based on the formulas presented here will work even without a drop in first fall degree, making the attack more versatile.

The deeper understanding for how the modifiers work allows for an even more efficient attack on the Dob scheme, which we now present.

6 A New Attack on the Dob Encryption Scheme

In the previous two sections we have studied how degree fall polynomials can occur in the Dob scheme, and have verified the accuracy of our resulting formulas through experiments. In this section we will show how all these insights can be combined to a novel attack. In Sect. 6.1, we shall see that adding an extra polynomial to the system can leak information about the modification polynomials. We will see how this information can be used to retrieve (linear combinations of) the secret ip linear forms, and the homogeneous quadratic part of the $Q_+$ modification, in Sects. 6.2 and 6.3. We investigate how Gröbner basis algorithms perform with this extra information in Sect. 6.4, and finally discuss the complexity of the entire attack in Sect. 6.5.

6.1 Adding an Extra Polynomial

In Sect. 3.1 we discussed how products of the modifiers and public polynomials affect the number of degree fall polynomials, through $\mathcal {P}_{M^{(2,1)}}$. One would also expect a similar effect to take place when adding a random polynomial to the system.

Consider a set of parameters for the Dob scheme, where the number of first fall polynomials is determined by $N_\nu ^{(0,0)}$, for some $\nu > 3$. Let $\mathcal {P}$ be the public key of this scheme, and consider a randomly chosen homogeneous polynomial $p_R$ of degree $\nu - 2$. As it is unlikely that the randomly chosen $p_R$ has any distinct interference with $\mathcal {P}$, we expect $(\langle p_R \rangle \cap M^{(2,1)})_\nu$ to be generated by the possible combinations $p_Rq_i^h$, and $p_R(v_jv_l)^h$. Furthermore, since the generators of $\mathcal {S}(\mathcal {F})$ have degree at least 3, we do not expect any collision between $\psi ^{\mathcal {P}^h}(\mathcal {S}(\mathcal {F}))$ and $\langle p_R\rangle$ at degree $\nu$ (cf. Sect. 3.3). From these considerations, we estimate the number of degree fall polynomials for the system $\{ \mathcal {P},p_R\}$ at degree $\nu$ to be:

$$\begin{aligned} N_\nu (\{ \mathcal {P},p_R\}) = N_\nu ^{(0,0)}(\mathcal {P}) + t + \left( {\begin{array}{c}k\\ 2\end{array}}\right) . \end{aligned}$$

(26)

We ran a few experiments that confirm this intuition, the details are given in Table 3. First, we confirmed that the degree fall polynomials of $\mathcal {P}$ were indeed given by $N^{(0,0)}_\nu (\mathcal {P})$, before applying Magma’s implementation of the F$_4$ algorithm on the system $\{\mathcal {P},p_R\}$. Recall also our convention that $\left( {\begin{array}{c}0\\ 2\end{array}}\right) = 0$ when applying Eq. (26).

Table 3. First fall polynomials of Dob encryption schemes with an added, randomly chosen polynomial $p_R$.

With all this in mind, assume for the moment that $d = n$, and consider a homogeneous Macaulay matrix of $\{\mathcal {P}^h,p_R\}$ at degree $\nu$, $\overline{M}_\nu (\{\mathcal {P}^h,p_R\})$. Any element in the (left) kernel of this matrix can in general be written as:

$$\begin{aligned} h_Rp_R + \sum _{i = 1}^d h_ip_i^h = 0, \end{aligned}$$

(27)

for some homogeneous quadratic polynomials $h_i\in \overline{B}(d)_{\nu - 2}$, $1\le i\le d$, and $h_R \in \overline{B}(d)_2$. From the discussion above, we expect that the only way $p_R$ contributes to these kernel elements is through the trivial syzygies, multiplications with $p_i^h$ or $p_R$, and through multiplying with the generators of $M^{(2,1)}$. It follows that any polynomial $h_R$, from Eq. (27), will be in the span of⁴

$$\begin{aligned} \mathcal {H} := \{ p_1^h,\ldots ,p_d^h,p_R,q_1^h,\ldots ,q_t^h,(v_1v_2)^h,\ldots , (v_{k-1}v_k)^h\}. \end{aligned}$$

(28)

Hence, given enough kernel elements of $\overline{M}_\nu (\{\mathcal {P}^h,p_R\})$, a set of generators of Span($\mathcal {H}$) can be found. In the next subsection we will generalise this observation to the case where a number of variables are fixed, i.e. $n < d$.

6.2 Gluing Polynomials

Let $W_\eta$ denote a non-empty subset of r variables, i.e. $W_{\eta } = \{ x_{\eta _1},\ldots ,x_{\eta _r} \}$ for integers $1\le \eta _1< \ldots < \eta _{r} \le d$. For $n = d - r$, there is a natural projection map associated to $W_\eta$, $\pi _{W_\eta }: B(d)\rightarrow B(d)/W_\eta \simeq B(n)$, that fixes the variables in $W_\eta$ to 0. For any polynomial system $\mathcal {R}$ over B(d), we will also write $\pi _{W_\eta }(\mathcal {R})$ to mean the system consisting of all polynomials in $\mathcal {R}$ under $\pi _{W_\eta }$. Suppose now that the number of first fall polynomials of a Dob system $\mathcal {P}$ is given by $N_\nu ^{(0,0)}$, after fixing r variables to 0, i.e., $n = d - r$. Let $W_\eta$ be the set of variables we fix. Following a similar line of reasoning as in Sect. 6.1, we find that $\pi _{W_\eta }(h_R)$ from a kernel element of the Macaulay matrix associated with $\pi _{W_\eta }(\{P^h,p_R\})$ will no longer be in the span of $\mathcal {H}$, but rather lie in the span of $\pi _{W_\eta }(\mathcal {H})$. To ease notation, we will write $\mathcal {H}_\eta = \pi _{W_\eta }(\mathcal {H})$. A natural question is whether we can recover $\mathcal {H}$, by using different variable sets $W_1,\ldots , W_\rho$, and finding generators for the associated polynomial sets $\mathcal {H}_1,\ldots ,\mathcal {H}_\rho$. We answer this question positively in this subsection.

Let $\widetilde{W}_\eta := \{x_1,\ldots ,x_d\}\setminus W_\eta$ denote the complement of $W_\eta$, and note that $\mathcal {H}_\eta$ only contains information about the set of monomials $A(W_\eta ) := \{x_ix_j | x_i,x_j\in \widetilde{W}_\eta \}$. In order to guarantee that the family $\mathcal {H}_1,\ldots ,\mathcal {H}_\rho$ can give complete information about $\mathcal {H}$ we need to ensure that for any choice of $1\le i<j\le d$, we have $x_i,x_j\in \widetilde{W}_\eta$ for at least one $1\le \eta \le \rho$. In other words, the sets $\widetilde{W}_1,\ldots ,\widetilde{W}_\rho$ must cover all possible quadratic monomials.

In practice, both d and the size r of the variable sets will be determined by the chosen Dob parameters⁵. This naturally leads to the following problem:

Definition 3

(The (Quadratic) (r,d)–Covering Problem). For integers $1< r < d - 1$, find the smallest number $\rho$ of variable sets, each of size r, such that

$$\begin{aligned} A(W_1)\cup \ldots \cup A(W_\rho ) = \{ x_ix_j | 1 \le i < j \le d\}. \end{aligned}$$

Appendix E of [33] presents a constructive solution to this problem, which provides a good upper bound for $\rho$ that is sufficient for our use case. The upper bound is given by the following lemma

Lemma 5

The (Quadratic) (r,d)–Covering Problem is upper bounded by

$$\begin{aligned} \rho \le \left( {\begin{array}{c}\Bigl \lceil \frac{d}{\lfloor (d-r)/2\rfloor }\Bigr \rceil \\ 2\end{array}}\right) . \end{aligned}$$

We illustrate the strategy for recovering $\mathcal {H}$ in the simple case when $d = 3r$. In this particular case, the method above yields $\rho = 3$, where $W_1$, $W_2$ and $W_3$ are pairwise, disjoint variable sets. We may write the following matrix:

Here $W_i *W_j$, $i,j\in \{1 ,2 ,3 \}$, is understood as a list of the monomials $x_ax_b$ where $x_a\in W_i$ and $x_b\in W_j$ (under any fixed ordering and $a\ne b$), and we write $H_l$ to mean the rows associated with a fixed set of generators for $\mathcal {H}_l$. A 0 in the matrix means that the respective submatrix is the zero matrix, whereas $*$ denotes that the submatrix may take non-zero values. By construction, if the submatrix whose rows are $H_l$, and columns are $W_i *W_j$, is denoted by $*$, then it forms a set of generators for $\mathcal {H}$ restricted to the monomials in $W_i*W_j$. In particular, the submatrix with columns $W_3 *W_3$ and rows $H_1$ spans the same row-space as the submatrix with columns $W_3 *W_3$ and rows $H_2$. We will use this observation to construct a new matrix, denoted $H_1 \cap _{W_3} H_2$, that combine the useful information from $H_1$ and $H_2$ in the following procedure.

• 1. Since $\{ p_1^h,\ldots ,p_d^h,p_R \}$ are known, we start by finding $t + \left( {\begin{array}{c}k\\ 2\end{array}}\right)$ vectors in the row space of $H_2$ that are linearly independent of $\pi _{W_2}(\{p_1^h,\ldots ,p_d^h,p_R \})$. Denote the set of these vectors $Y_2$.

• 2. If $|W_3 *W_3 |>> d + t + \left( {\begin{array}{c}k\\ 2\end{array}}\right) + 1$, then for each vector $y_i\in Y_2$, we can expect a unique vector $z_i$ in the row space of $H_1$, such that $y_i + z_i$ is 0 along the columns associated with $W_3 *W_3$. Find such an $z_i$ for each $y_i\in Y_2$ through Gaussian elimination.

• 3. We now have $t + \left( {\begin{array}{c}k\\ 2\end{array}}\right)$ pairs $(y_i,z_i)$ that are used to define the $(t + \left( {\begin{array}{c}k\\ 2\end{array}}\right) )\times \left( {\begin{array}{c}d\\ 2\end{array}}\right)$ matrix $(H_1 \cap _{W_3} H_2)$ over $\mathbb {F}_2$ in the following manner. For each row index $i_0$ and column index $j_0$, we define the entry at $[i_0,j_0]$ to be

  $$\begin{aligned} (H_1 \cap _{W_3} H_2)[i_0,j_0] = {\left\{ \begin{array}{ll} y_{i_0}[j_0], \text { if }j_0\text { is associated with a monomial in }W_3 *W_3\\ y_{i_0}[j_0] + z_{i_0}[j_0], \text { otherwise}.\end{array}\right. } \end{aligned}$$

The above procedure uses the common information found in the columns of $W_3 *W_3$ to combine vectors from $H_1$ and $H_2$. We may think of this as “gluing" polynomials along $W_3 *W_3$, hence the name of the technique. Now consider the following matrix.

Note in particular that the polynomials associated with $(H_1 \cap _{W_3} H_2)$ forms a set of generators for $\pi _{_{W_1 *W_2}}(\mathcal {H})$. In order to recover the information of the monomials in $W_1 *W_2$, we need only glue the vectors of $(H_1 \cap _{W_3} H_2)$, with combinations from the row space of $H_3$, using the same procedure as described above. Since both $(H_1 \cap _{W_3} H_2)$ and $H_3$ may take non–zero values at $W_1 *W_1$ and $W_2 *W_2$, we expect the gluing to result in $t + \left( {\begin{array}{c}k\\ 2\end{array}}\right)$ unique polynomials if $|(W_1 *W_1)\cup (W_2 *W_2)|>> d + t + \left( {\begin{array}{c}k\\ 2\end{array}}\right) + 1$. By construction, all of the resulting $t + \left( {\begin{array}{c}k\\ 2\end{array}}\right)$ polynomials associated with $(H_1 \cap _{W_3} H_2) \cap _{W_1} H_3$ will be in the span of $\langle p_1^h,\ldots ,p_d^h,p_R,q_1^h,\ldots ,q_t^h,\ldots (v_iv_j)^h\ldots \rangle$, but none of them in the span of $\langle p_1^h,\ldots ,p_d^h,p_R\rangle$. Hence we define $\mathcal {G}$ to be the set consisting of the polynomials $\{p_1^h,\ldots ,p_d^h,p_R\}$, as well as the polynomials associated with $(H_1 \cap _{W_3} H_2) \cap _{W_1} H_3$, and note that $\mathcal {G}$ is, by construction, a system of polynomials that are linearly equivalent to $\mathcal {H}$.

As a proof of concept, we implemented retrieving $\mathcal {G}$ from a toy example of the Dob scheme, with $d = 45$, $t = 6$ and $k = 0$, using the method described above. The interested reader can find more details by consulting Example 3, Appendix C in [33].

The General Case. In the case of a general family of variable sets $W_1,\ldots ,W_\rho$, we will not be able to set up the straightforward matrices that was shown above. The gluing process can still be done in a similar, iterative manner. For instance, the submatrix associated with $\mathcal {H}_\eta$ will have 0 for each monomial $x_ix_j$ where $x_i$ or $x_j\in W_\eta$, and $*$ otherwise. As above, we expect to be able to glue $\mathcal {H}_\eta$ with $\mathcal {H}_\psi$ if the number of their common $*$–monomials exceeds $d + t + \left( {\begin{array}{c}k\\ 2\end{array}}\right) + 1$.

6.3 Retrieving the Linear Forms from ip

Suppose now that a set of generators $\mathcal {G}$ for Span$(\mathcal {H})$ has been found, as described in Sect. 6.2. The goal is to recover k linear forms that are generators for $\langle v_1,\ldots ,v_k\rangle$. In order to simplify our arguments we will assume $k\ge 5$. The special cases $2\le k\le 4$ does not provide more security, and are dealt with in Remark 1, [33].

Consider the kernel of the homogeneous Macaulay matrix $\overline{M}_3(\mathcal {G})$. From the definition of $\mathcal {H}$ (Eq. (28)), we find that Span($\mathcal {H}$) contains all the homogeneous nude Dob–polynomials $f_1^h,\ldots ,f_d^h$, as well as all the combinations $(v_iv_j)^h$, $1\le i < j\le k$. Each polynomial $(v_iv_j)^h$ generates the two kernel elements $v_i(v_iv_j)^h$ and $v_j(v_iv_j)^h$ (which are trivial when working over $\overline{B}(d)$). The nude Dob–polynomials will generate the 2d kernel elements associated with the degree fall polynomials discussed in Sect. 4.2. We would like to separate these two types of kernel elements. To this end, we suggest constructing a smaller system, $\mathcal {G}'$, by removing three polynomials from $\mathcal {G}$, that are in the span of $\{p_1^h,\ldots , p_d^h\}$. Indeed, the idea is that this will work as a self–imposed minus modifier, which will remove the effect of the Dob–polynomials of $\mathcal {G}$ at degree 3.

On the other hand, some kernel elements generated by combinations of the $(v_iv_j)^h$–elements can still be observed for $\mathcal {G}'$ at degree 3. More specifically, suppose $\mathcal {G}'$ was created from $\mathcal {G}$ by removing $p_1^h,p_2^h$ and $p_3^h$. Then Span($\mathcal {G}'$) may not necessarily contain $(v_1v_j)^h$ itself, for any $2\le j\le k$, but it will contain the combination $(v_1v_j)^h + b_{1,j}p_1^h + b_{2,j}p_2^h + b_{3,j}p_3^h$, for some $b_{1,j},b_{2,j},b_{3,j}\in \mathbb {F}_2$. By considering these equations for all j, and eliminating $p_1^h,p_2^h$ and $p_3^h$, we find that Span($\mathcal {G}'$) will contain a polynomial $z_1 = \sum _{j = 2}^k a_j(v_1v_j)^h$, where $a_2,\ldots ,a_k \in \mathbb {F}_2$ are not all 0, using the assumption that $k\ge 5$. The polynomial $v_1z_1$ will subsequently be reduced to 0 over $\overline{B}(d)$. Similarly, we are guaranteed to find polynomials $z_2,\ldots ,z_k$. We assume that these are the only contributors to the kernel. In particular, this means that each kernel element of $\overline{M}_3(\mathcal {G}')$ can be written as $\sum l_ig_i = 0$, with $g_i\in \mathcal {G}'$, and each $l_i$ a linear form in Span($\{ v_1,\ldots , v_k \}$). It follows that an attacker can retrieve a basis $v_1^*,\ldots ,v_k^*$ of $\langle v_1,\ldots , v_k\rangle$, by determining k linearly independent $l_i$’s from these kernel elements.

The retrieval of $\mathcal {G}$ and $v_1^*,\ldots ,v_k^*$, as described in this subsection, has been implemented and verified on the toy example with parameters $d = 63$, $t = 1$ and $k = 4$. This is further described in Example 4, Appendix C of [33].

6.4 Solving the Extended Dob System

Assume now that an attacker has followed the steps described in the previous subsections, and has recovered a system $\mathcal {G}$ (Sect. 6.2), as well as a basis $\{v_1^*,\ldots ,v_k^*\}$ that generates $\langle v_1,\ldots ,v_k\rangle$ (Sect. 6.3). Now fix a set of generators $q_1^*,\ldots ,q_k^*$ for the polynomials that are in Span($\mathcal {G}$), but not in

$$\begin{aligned} \text {Span}(\{p_1^h,\ldots ,p_d^h,p_R,(v_i^*v_j^*)^h | 1\le i < j \le k\}). \end{aligned}$$

With all this information, we consider the associated extended Dob system, $\mathcal {P}_E$, defined by:

$$\begin{aligned} \mathcal {P}_E := \{p_1,\ldots ,p_d,p_R,q_1^*,\ldots ,q_t^*,v_1^*,\ldots ,v_k^*\}. \end{aligned}$$

(29)

For any given ciphertext, an attacker with access to an extended Dob system can guess constant values for the polynomials $p_R,q_1^*,\ldots ,q_t^*,v_1^*,\ldots ,v_k^*$, and check the guess by finding a Gröbner basis for $\mathcal {P}_E$.

Remark 1

A system $\mathcal {P}_E$ that is independent of the randomly chosen polynomial $p_R$ can be obtained by running the steps described in Sects. 6.2 and 6.3 for two different elements $p_R$, and combine the results. More information can be found by consulting Remark 2 in [33].

In order to get a better understanding of solving extended Dob systems, we introduce the following modification for multivariate schemes.

Definition 4

For a polynomial system $\mathcal {P}'$, we define the modification $\mathcal {L}_{+}$ by choosing $l_0$ linear forms, and appending linear combinations of them to each polynomial in $\mathcal {P}'$.

Consider an extended Dob system, $\mathcal {P}_E$, where all coefficients have been guessed correctly. Since $q_i^*$ does not contain any information about the linear part of the $q_i$–polynomials, it follows that Span($\mathcal {P}_E$) will contain a Dob system that is only modified with the $\mathcal {L}_+$–modification, where $l_0 = t$. Moreover, this Dob system has d equations and $d-k$ variables⁶. The problem of estimating the complexity of finding a solution to $\mathcal {P}_E$, can then be reduced to that of estimating the complexity of finding a Gröbner basis for Dob with the $\mathcal {L}_+$–modification. While a thorough analysis of this $\mathcal {L}_+$–modification is beyond the scope of this work, we point out a couple of immediate properties.

Firstly, seeing that the first fall degree only depends on the upper homogeneous part of a polynomial system, it is unaffected by the $\mathcal {L}_+$–modification. In particular, we expect 2d degree fall polynomials at degree 3, as in the case for nude Dob (Sect. 4.2). Secondly, if running an algorithm such as F$_4$, a second batch of degree fall polynomials will emerge at the first step of degree 4. To see this, note that Dob with the $\mathcal {L}_+$–modification can be written over the quotient ring $\mathbb {F}_{2^{d}}[X]/\langle X^{2^{d}} + X\rangle$ as

$$\begin{aligned} F_{\mathcal {L}_+}(X) = X(X^{2^{m}} + X^2) + L(X) + C_E, \end{aligned}$$

(30)

where $C_E$ is a constant in $\mathbb {F}_{2^{d}}$, and $L(X) = \sum _{i = 1}^m c_iX^{2^{i}}$, with $c_i\in \mathbb {F}_{2^{d}}$, is a polynomial of binary weight one. $XF_{\mathcal {L}_+}$ is one of the combinations that induce degree fall polynomials at degree 3, and $X^4XF_{\mathcal {L}_+}$ will correspond to cubic⁷ (multivariate) polynomials found at the second step of degree 3. Upon running a subsequent step at degree 4, the polynomial $L(X)X^4XF_{\mathcal {L}_+}$ will correspond to d multivariate cubic polynomials, and would hence be counted as degree fall polynomials.

We ran a few experiments for extended Dob systems, $\mathcal {P}_E$, the results of which can be found in Appendix F of [33].

6.5 Complexity of the Attack

The attack proposed in this section has two main parts. The first step is to construct an extended Dob system, $\mathcal {P}_E$. In the second step, an attacker solves this system for a particular ciphertext. Suppose an attacker fixes $d - n$ variables in order to find $\rho$ polynomial systems $\mathcal {H}_1,\ldots ,\mathcal {H}_\rho$ from the kernel elements of Macualay matrices of degree $D_0 \ge 3$. The gluing operations, determining the linear forms $v_1^*,\ldots ,v_k^*$, and the quadratic forms $q_1^*,\ldots ,q_t^*$ only involve Macaulay matrices of degree at most three. Hence, we expect the first step to be dominated by recovering generators for the polynomial systems $\mathcal {H}_i$. While the optimal choice of attack parameters may depend on the parameters of the Dob encryption scheme, as a rule of thumb it seems best to first minimize $D_0$, then n, and lastly $\rho$. In practice, minimizing n involves choosing the smallest n such that $D_{reg}(d,n)>D_0$, for a fixed d. Kernel elements of the resulting sparse, homogeneous Macaulay matrix can be found using a variant of the Wiedemann algorithm [30] (see also [6] for an implementation of a version adapted to the XL algorithm). Section VI of [30] shows that one kernel vector can be retrieved after three iterations with probability $>0.7$, and as a simplification we estimate the complexity of finding a sufficient number of kernel elements in each of the $\rho$ Macaulay matrices as $\frac{3}{0.7}\left( t + \left( {\begin{array}{c}k\\ 2\end{array}}\right) \right) \left( {\begin{array}{c}n\\ D_0\end{array}}\right) ^2\left( {\begin{array}{c}n\\ 2\end{array}}\right)$. Recall from Remark 1 that the first step is performed twice if the attacker wishes to remove the effect of $p_R$ from $\mathcal {P}_E$; let $\delta = 1$ denote if this is the case, and $\delta = 0$ otherwise. It follows that the total attack complexity can be estimated as

$$\begin{aligned} \mathcal {C}_{\text {Attack}} = \text {max}\bigg \{2^\delta \rho \frac{3}{0.7}\left( t + \left( {\begin{array}{c}k\\ 2\end{array}}\right) \right) \left( {\begin{array}{c}n\\ D_0\end{array}}\right) ^2\left( {\begin{array}{c}n\\ 2\end{array}}\right) ,\mathcal {C}_{\mathcal {P}_E,\delta }\bigg | \delta \in \{ 0,1 \} \bigg \}, \end{aligned}$$

(31)

where $\mathcal {C}_{\mathcal {P}_E,\delta }$ denotes the complexity of finding a solution for $\mathcal {P}_E$ (with or without $p_R$, depending on $\delta$). While we do not have a general estimate for the complexity this second step, we discuss how to estimate it in the case of the 80–bit secure parameter set proposed in Sect. 2.4 of [20], in the following.

Security of the Suggested Parameters. Let $d = 129$, and $t = k = 6$ for the Dob encryption scheme. Using Eqs. (3) and (21) we find that it is not possible to choose an n such that $N_4^{(0,0)}$ is positive, and $D_{reg}(129,n)>4$. For degree 5, we find that $n = 50$ is the smallest number such that $N_5^{(0,0)}$ is positive, and $D_{reg}(129,50)> 5$. Indeed, for this choice of parameters, we get:

$$\begin{aligned} N_5^{(0,0)}(129,50,6,6) = 64024, \end{aligned}$$

which is exactly the number of degree fall polynomials observed in the last row of Table 2. For this choice of parameters, $\rho$ is upper bounded by 15, due to Lemma 5. In this case we can do even better, and use $\rho = 11$, as described in Appendix E of [33]. Choosing $\delta = 1$, we find that the first step requires about $2^{63}$ operations. For step two, we note from the experiments we ran, provided in Table 4 Appendix F of [33], that the extended Dob system with modifications $t = k = 6$ has a solving degree of 4 in all the experiments we can run. Conjecturing that this behaviour extends to $d = 129$, we estimate the complexity of step two to be $\mathcal {C}_{\mathcal {P}_E,1} = 2^{12}\left( {\begin{array}{c}123\\ 4\end{array}}\right) ^\omega$, where the factor $2^{12}$ is the cost of finding the correct constants for $q_1^*,\ldots ,q_6^*$ and $v_1^*,\ldots ,v_6^*$. We have also used $123 = 129 - 6$ as the number of variables in this system, seeing that 6 variables are eliminated by the linear forms $v_i^*$.

Using $\omega = 2.4$, step two is estimated at $2^{67}$. Using Strassen’s algorithm with $\omega = 2.8$ (a rather pessimistic choice for an attacker as it assumes that it is not possible to take advantage of the sparse matrix structure of the systems), the estimate is $2^{77}$ for step two. Either option leads to a time complexity below the proposed 80–bit security.

7 Conclusions

We have presented an analysis on the security provided by the $Q_+$ and ip modifications against algebraic attacks. The theory was then applied to the Dob encryption scheme, along with a novel attack on this construction. Not only does the attack break the suggested parameter set, but the effectiveness of how crucial information regarding the modifications can be retrieved allows us to conclude that the Dobbertin permutation seems unsuited for use in encryption schemes. The reader may consult Section 7 in [33] for a more in–depth discussion on this. We emphasize that this work has not covered the Dob signature scheme, nor the generalized central maps introduced in [20]; their security remains an open question.

There are several directions where the ideas presented here may inspire future work. Firstly, the modifications are treated as ideals, whose dimensions can be examined. If different types of modifications, such as minus and vinegar, can be included in this framework, it could lead to a deeper understanding of the security of an even larger subclass of big–field schemes. Secondly, the attack introduces new tools for the cryptanalysis of multivariate schemes. The gluing technique allows an attacker to collect useful information after fixing a number of variables. As there is no need for correct guesses, the exponential factor usually associated with hybrid methods is avoided. Furthermore, the technique does not rely on heuristic assumptions on the relation between the first fall and solving degrees.

In light of this, we believe that security analyses of big–field multivariate schemes ought not only focus on the first fall degree directly, but also how this degree changes when fixing variables. Cryptographers wishing to design encryption schemes by adding limited modification to an otherwise weak polynomial system should be particularly aware of the effect presented in this work.