Differential biases, $c$-differential uniformity, and their relation to differential attacks

A block cipher is a symmetric encryption scheme that transforms an $n$-bit plaintext into an $n$-bit ciphertext using a secret key. Block ciphers (like AES) constitute the majority of all symmetric ciphers in use today, and are a staple of modern cryptography. A classical construction of block ciphers is iterative, meaning that the entire cipher is a sequence of (generally simple and almost identical) round functions, see Figure 1 for a schematic illustration. A standard choice for a round function is a Substitution-Permutation Network (SPN), which consisting of a linear layer, sometimes called the permutation part and a substitution layer (usually several so called S-boxes running in parallel), with a key addition in between the rounds, see Figure 2 for a conceptual visualization.

One of the most important attacks against block ciphers is the so-called differential attack introduced in [1], which also serves as a basis for more advanced attacks like boomerang attacks [2], rectangle attacks [3], or differential-linear attacks [4].

Let us briefly recall the main idea behind the classical differential attack. The attack uses that differences of plain texts propagate with different probabilities through the encryption process.

A cipher vulnerable to a differential attack has a (strongly) non-uniform distribution of differences that can then be exploited by a differential attack. The concept of difference used here is usually the XOR (i.e. addition in $\mathbb{F}_{2}^{n}$). The main reason for this is that the most standard design for SPNs uses key additions, i.e. the key is simply added to the message in between all rounds.

Clearly, we have $(x+\Delta+k)-(x+k)=(x+\Delta)-x$, so the key addition process does not impact the propagation of differences at all. Further, the differences are also not impacted by the linear layer of SPNs, so the only part that has direct influence is the S-box layer, which makes both analysis and design considerably easier. For a function $F\colon\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2}^{n}$, the differential attack thus considers the following distribution of probabilities, where $\Delta_{I}$, $\Delta_{O}$ are the differences of plain and cipher texts, respectively:

The main idea behind the differential attack is then that, because the key does not impact the propagation of differences, differences can be broken down over all rounds, so differential trails $(\Delta_{0},\dots,\Delta_{r})$ can be constructed which capture the probability that an input difference $\Delta_{0}$ propagates through an $r$-round block cipher to an output difference $\Delta_{r}$ via intermediate differences $\Delta_{i}$ after the $i$-th round. With the tacit assumption of uniformity, the differential analysis of the cipher can thus be broken down to analysing its constitutive rounds, which, in the case of an successful attack, allows the attacker to guess the key given enough plaintext - ciphertext pairs. To combat these differential attacks, the probabilities in Eq. (1) should be as uniform as possible.

As described above, the resistance of an SPN relies on its non-linear part, i.e. the choice of the S-box. The behaviour of an S-box $F$ with regard to differential attacks is measured by its Difference Distribution Table (DDT) and differential uniformity $\delta(F)$ which are defined as

The lower the differential uniformity of $F$, the better is its resistance against a differential attack.¹¹1Of course, the choice of the linear layer is also important for the resistance against a differential attack to maximize the number of active S-boxes. The best possible differential uniformity for S-boxes over binary finite fields is 2, those S-boxes are called almost perfect nonlinear (APN).

The basic idea of the differential attack can be transferred to another group operation that substitutes the role of the XOR/addition. For example, multiplicative differentials were considered in [5]. Instead of investigating the propagation on pairs $(x,x+\Delta)$, this kind of differential attack considers pairs $(x,\alpha\cdot x)$, where the multiplication is the multiplication in the ring $\mathbb{Z}_{n}$. These kind of attacks were motivated by a number of ciphers that did not just use a simple key addition, but instead relied on modular multiplication as a primitive operation. The authors of [6] use this motivation to consider a notion that tracks some statistical behaviour of the propagation of differences and is clearly inspired by the definition of the differential uniformity in (3). The definition uses a more general setting (not restricting to characteristic $2$), and uses the well known isomorphism (as vector spaces) of $\mathbb{F}_{p}^{n}$ and $\mathbb{F}_{p^{n}}$.

In characteristic $2$, the case $c=1$ clearly recovers the usual definition of DDT and differential uniformity in (2) and (3). Again, the function $F$ has minimal statistical bias if the $c$-differential uniformity is as low as possible. If a function $F$ achieves the minimal possible $c$-differential uniformity $1$, we call it perfect $c$-nonlinear (PcN).

The new notion of $c$-differential uniformity has led to much new research, counting more than a dozen papers in less than two years dedicated to it (see e.g. [8, 9, 10], and in particular the survey paper [11] and the references therein), usually focusing on determining the $c$-differential uniformity of functions $F\colon\mathbb{F}_{p^{n}}\rightarrow\mathbb{F}_{p^{n}}$ that have seen use or are possible candidates for S-boxes. Despite the considerable attention that the $c$-differentials have received, a practical analysis has so far been lacking.

We give a brief overview on function fields and Galois theory to the extent that is needed for this section. We broadly follow the notation from [17].

Let $\mathbb{F}_{q}(t)$ be the rational function field in the variable $t$ over the finite field of order $q$. A function field $F$ is an algebraic extension of $\mathbb{F}_{q}(t)$. The field of constants $k_{F}$ of $F$ is the subfield of elements of $F$ that are algebraic over $\mathbb{F}_{q}$.

A valuation ring $\mathcal{O}$ is a subring of $F$ that contains $\mathbb{F}_{q}$, is different from $F$, and such that if $x\not\in\mathcal{O}$, then $1/x\in\mathcal{O}$. A place $P$ is the unique maximal ideal of a valuation ring $\mathcal{O}$ and it is principal. The valuation ring attached whose maximal ideal is the place $P$ is denoted by $\mathcal{O}_{P}$.

Fix a place $P$. Each element $z\in F\setminus\{0\}$ can be uniquely written as $z=t^{n}u$, where $t$ is a prime element for a place $P$ and $u\in\mathcal{O}_{P}$ is invertible. We associate to $P$ a function $v_{P}:F\to\mathbb{Z}\cup\{\infty\}$, called valuation at $P$, defined as $v_{P}(z)=n$, if $z=t^{n}u\in F\setminus\{0\}$, and $v_{P}(z)=\infty$, if $z=0$.

An inclusion $F\subseteq L$ of function fields is said to be a function field extension, and we will denote it by $L:F$. The degree of $L:F$ is simply the integer $[L:F]:=\dim_{F}(L)$. If $P$ is a place of $F$, there are $Q_{1},\dots,Q_{\ell}$ places of $L$ above $P$, i.e. places of $L$ that contain $P$. The relative degree of $Q_{i}$ over $P$ is the integer $f(Q_{i}\mid P)=[\mathcal{O}_{Q_{i}}/Q_{i}:\mathcal{O}_{P}/P]$.

The ramification index $e(Q_{i}\mid P):=e$ of $Q_{i}$ over $P$ is a natural number such that

We say that $Q_{i}\mid P$ is ramified if $e(Q_{i}\mid P)>1$, and unramified if $e(Q_{i}\mid P)=1$. The fundamental equality for function field extensions states

A finite separable extension of fields $M\supseteq F$ is said to be Galois if $\operatorname{Aut}_{F}(M):=\{f\in\operatorname{Aut}(M):\;f(x)=x\;\forall x\in F\}$ has size $[M:F]$. Let us recall that every splitting field $M$ of a separable polynomial in $F[x]$ is a Galois extension of $F$. Moreover, every Galois extension of $F$ can be seen as a splitting field of some polynomial in $F[x]$.

The following result is useful to connect the action of the Galois group on the roots to the intermediate splitting of places. See [18, Satz 1].

It follows immediately that

Notice that if $M:K$ is a Galois extension of function fields over $\mathbb{F}_{q}$, then $kM:kK$ is Galois for any extension $k$ of $\mathbb{F}_{q}$ (including $k=\overline{\mathbb{F}}_{q})$. It is well known, see for example [17], that the geometric Galois group is generated by the inertia groups.

The following result can be deduced from [19].

The following corollary shows that we can deduce arithmetic information (splitting over $\mathbb{F}_{q}$) from geometric information (splitting over $\overline{\mathbb{F}}_{q}$, i.e. ramification).

The following result follows from [21, Proposition 1, Page 275].

As a notation, $\mathbb{P}^{r}(\mathbb{F}_{q})$ and $\mathbb{A}^{r}(\mathbb{F}_{q})$ denote the projective and the affine space of dimension $r\in\mathbb{N}$ over the finite field $\mathbb{F}_{q}$, $q$ a prime power. In the cases $r=2$ and $r=3$ we denote by $\ell_{\infty}:=\mathbb{P}^{2}(\mathbb{F}_{q})\setminus\mathbb{A}^{2}(\mathbb{F}_{q})$ and $H_{\infty}:=\mathbb{P}^{3}(\mathbb{F}_{q})\setminus\mathbb{A}^{3}(\mathbb{F}_{q})$ the line and the plane at infinity respectively. A variety and more specifically a curve, i.e. a variety of dimension 1, is described by a certain set of equations with coefficients in a finite field $\mathbb{F}_{q}$. We say that a variety $\mathcal{V}$ is absolutely irreducible if there are no varieties $\mathcal{V}^{\prime}$ and $\mathcal{V}^{\prime\prime}$ defined over the algebraic closure of $\mathbb{F}_{q}$ and different from $\mathcal{V}$ such that $\mathcal{V}=\mathcal{V}^{\prime}\cup\mathcal{V}^{\prime\prime}$. If a variety $\mathcal{V}\subset\mathbb{P}^{r}(\mathbb{F}_{q})$ is defined by homogeneous polynomials $F_{i}(X_{0},\ldots,X_{r})=0$, for $i=1,\ldots,s$, an $\mathbb{F}_{q}$-rational point of $\mathcal{V}$ is a point $(x_{0}:\ldots:x_{r})\in\mathbb{P}^{r}(\mathbb{F}_{q})$ such that $F_{i}(x_{0},\ldots,x_{r})=0$, for $i=1,\ldots s$. A point is affine if $x_{0}\neq 0$. The set of the $\mathbb{F}_{q}$-rational points of $\mathcal{V}$ is usually denoted by $\mathcal{V}(\mathbb{F}_{q})$. We denote by the same symbol homogenized polynomials and their dehomogenizations, if the context is clear. For a more comprehensive introduction to algebraic varieties and curves we refer to [22, 23].

In this paper we will mostly make use of hypersurfaces, i.e varieties in $\mathbb{P}^{r}(\mathbb{F}_{q})$ of dimension $r-1$, and specifically curves ($r=2$) and surfaces ($r=3$). Any hypersurface is defined by a unique homogeneous $f(X_{0},\ldots,X_{r})$ polynomial in $r+1$ variables. For the sake of convenience, for a hypersurface $\mathcal{W}:f(X_{0},\ldots,X_{r})=0$ we will also make use of its affine equation $f(1,X_{1}\ldots,X_{r})=0$.

Singular points of algebraic curves and surfaces can be investigated via the so-called Hasse derivative; see also [22, Page 148].

It can be seen that for any monomial $X_{1}^{j_{1}}\cdots X_{r}^{j_{r}}$ its $i=(i_{1},\ldots,i_{r})$-th Hasse derivative is

and vanishes if $i_{k}>j_{k}$ for some $k$; see also [25].

As a notation, if a polynomial $f$ is univariate, we denote its derivatives as $f^{\prime}$, $f^{\prime\prime}$, ….

Let $F(X,Y)\in\mathbb{F}_{q}[X,Y]$ be a polynomial defining an affine plane curve $\mathcal{C}$, let $P=(u,v)\in\mathbb{A}^{2}(\mathbb{F}_{q})$ be a point in the plane, and write

where $F_{i}$ is either zero or homogeneous of degree $i$.

The multiplicity of $P\in\mathcal{C}$, written as $m_{P}(\mathcal{C})$, is the smallest integer $m$ such that $F_{m}\neq 0$ and $F_{i}=0$ for $i<m$; the polynomial $F_{m}$ is the tangent cone of $\mathcal{C}$ at $P$. A linear divisor of the tangent cone is called a tangent of $\mathcal{C}$ at $P$. The point $P$ is on the curve $\mathcal{C}$ if and only if $m_{P}(\mathcal{C})\geq 1$. If $P$ is on $\mathcal{C}$, then $P$ is a simple point of $\mathcal{C}$ if $m_{P}(\mathcal{C})=1$, otherwise $P$ is a singular point of $\mathcal{C}$. A quick criterion to decide whether an affine point $P$ is singular is the following: $P$ is singular if and only if $F(P)=F^{(1,0)}(P)=F^{(0,1)}(P)=0$.

It is possible to define in a similar way the multiplicity of an ideal point of $\mathcal{C}$, that is a point of the curve lying on the line at infinity.

Given two plane curves $\mathcal{A}$ and $\mathcal{B}$ and a point $P$ on the plane, the intersection number $I(P,\mathcal{A}\cap\mathcal{B})$ of $\mathcal{A}$ and $\mathcal{B}$ at the point $P$ can be defined by seven axioms. We do not include its precise and long definition here. For more details, we refer to [26] and [22] where the intersection number is defined equivalently in terms of local rings and in terms of resultants, respectively.

Concerning the intersection number, the following two classical results can be found in most of the textbooks on algebraic curves.

Concerning surfaces in $\mathbb{P}^{3}(\mathbb{F}_{q})$, i.e. variety of dimension 2 defined by a homogeneous polynomial $F(X,Y,Z,T)\in\mathbb{F}_{q}[X,Y,Z,T]$, the same definitions for singular points and multiplicity hold. In particular a point $P$ is singular for a surface $\mathcal{S}:F(X,Y,Z,T)=0$ if and only if

The following is a simple result about the irreducibility of plane sections of absolutely irreducible surfaces. We include here its proof for the sake of clarity.

Finally, we include here references for estimates on the number of $\mathbb{F}_{q}$-rational points of algebraic varieties over finite fields. The most celebrated result is the Hasse-Weil Theorem.

If the curve $\mathcal{C}$ is singular, there is some ambiguity in defining what an $\mathbb{F}_{q}$-rational point of $\mathcal{C}$ actually is. Clearly, if $\mathcal{C}$ is non-singular, then there is a bijection between $\mathbb{F}_{q}$-rational places (or branches) of the function field associated with $\mathcal{C}$ and $\mathbb{F}_{q}$-rational points of $\mathcal{C}$. In the singular case, this is no more true. We refer the interested readers to [22, Section 9.6] where other relations are investigated. We point out that actually the bound (5) holds even for singular (absolutely irreducible) curves; [27, Corollary 2.5].

Concerning algebraic varieties of dimension larger than one, the first estimate on the number of $\mathbb{F}_{q}$-rational points was given by Lang and Weil [28] in 1954.