On the additive differential probability of ARX construction

INTRODUCTION

ARX ciphers are constructed by the modular addition, bit rotation, and XOR operations (ARX). Examples include the block cipher SPECK ^[1], Sparx ^[2], the stream cipher Salsa20 ^[3], ChaCha20 ^[4], the cryptographic permutations Alzette ^[5], Sparkle ^[6], the MAC (Message Authentication Code) Chaskey ^[7], the PRF (Pseudo-random function) Siphash ^[8], the SHA-3 finalists BLAKE^[9], and Skein^[10]. The ARX design has the following three advantages. Firstly, diffusion and confusion can be provided by the modulo additions, making it possible to avoid the table look-ups to look up the table compared with the S-box based SPN designs, which strengthens the resilience against timing side-channel attacks. Secondly, since modulo additions can be natively supported in modern CPUs, the ARX ciphers have fast software implementations due to the native support of the modulo additions in modern CPUs. Finally, the code size of describing an ARX primitive is very simple and small, incurring minimal costs, making it suitable for application scenarios the cases where the memory footprint is highly constrained.

Differential Cryptanalysis of ARX Primitives. Among all the cryptanalyses ^[11–17] for symmetric cryptography, Differential Cryptanalysis ^{[16, 17]} is one of the most important techniques to analyze the cryptographic primitives. Thus, both in the design and cryptanalysis of ARX ciphers, the differential properties of ARX constructions are of great importance. The first algorithm for computing the differential probabilities of modulo additions efficiently was first proposed in 2001 ^[18]. Later, for the additive differential probabilities of XOR, Lipmaa et al. ^[19] give the first algorithm for computing it efficiently. In 2011, Velichkov et al. ^[20] presented an algorithm for computing the additive differential probabilities of ARX constructions efficiently. However, the algorithm is only suitable for some ARX constructions involving only one bit rotation, such as Skein ^[3]. For other ARX constructions, such as Alzette ^[5] (see Figure 1), we must consider a new algorithm.

Figure 1. The round function of Alzette, where $$ x $$ is the input of the left branch, and $$ y $$ is the input of the right branch

Contribution. Inspired by the work of Niu et al. ^[21] on calculating the rotational differential-linear correlation of the modulo addition for modulo additions, we use a delicate artful partition of $$ \mathbf{F}_2^m \times \mathbf{F}_2^m $$ into subsets, where the elements in each subset fulfill certain equations. The method is extremely efficient, and the. The time complexity of computing the additive differential probabilities of ARX constructions: $$ (x \boxplus y) \lll d \oplus y \lll e $$ is, can be estimated by the complexity of $$ 4n $$$$ n $$$$ 8 \times 8 $$ matrix multiplications. It can be summarized as follows, with factor $$ 4 $$.

Theorem Organization. For $$ \alpha',\beta, \gamma \in \mathbf{F}_2^n $$ and ARX construction $$ ARX(x,y,d,e) $$, which is illustrated in Fig 5, if we let $$ \alpha= \alpha' \boxplus^{n} \beta $$, then $$ \Pr[(\alpha',\beta) \rightarrow {\gamma}]^{ARX} $$ can be calculated as:

where $$ \mathbf{e}_i $$ denotes the $$ i $$-th unit vector,

and

Section 2 briefly introduces some notations and preliminaries on modulo addition, ARX structures, and additive differential probability. The partition of $$ \mathbf{F}_2^n \times \mathbf{F}_2^n $$ and its properties are described in section 3. In section 4, we show that the calculation of additive differential probability of ARX structures can be divided into three parts. Then, in section 5, we give the method to calculate the additive differential probability of ARX structures. Finally, we conclude our work in section 6.

NOTATIONS AND PRELIMINARIES

For a finite set $$ \mathbf{D} $$, $$ \# \mathbf{D} $$ denotes the number of elements. Let $$ \mathbf{F}_2=\{0,1\} $$ be the binary field. We denote by $$ x_i $$ the $$ i $$-th bit of a vector $$ \mathbf{x}=(x_{n-1}, \cdots, x_{0}) \in \mathbf{F}_2^n $$. In addition, $$ \lceil \mathbf{x} \rceil^{(t)}=(x_{n-1}, \cdots, x_{n-t}) $$ denotes the most significant $$ t $$ bits of $$ \mathbf{x} $$. $$ \lfloor \mathbf{x} \rfloor^{(t)}=(x_{t-1}, \cdots, x_{0}) $$ denotes the least significant $$ t $$ bits of $$ \mathbf{x} $$. $$ [x]_{a}^b=(x_{b}, \cdots, x_{a}) $$ denotes the substring of $$ \mathbf{x} $$ form $$ (a-1) $$-bit to $$ (b-1) $$-bit. Concrete values in $$ \mathbf{F}_2^n $$ are specified in hexadecimal or binary notations. For example, we use $$ \mathbf{0x3F21} $$ to denote the binary string $$ 0011111100100001 $$. And let $$ 1^n $$ denote the binary string $$ 111 \cdots 1111 $$, and $$ 0^n $$ denote the binary string $$ 000 \cdots 000 $$. Rotation of $$ \mathbf{x} $$ by $$ t $$ bits is denoted by $$ \mathbf{x} \lll t $$. Let $$ M_i $$ for $$ 0 \le i <n $$ be the $$ k \times k $$ matrices, and we use $$ \prod_{i=0}^nM_i $$ to denote the product with the specified order $$ M_{n-1}\cdots M_0 $$. For any $$ n>0 $$, the function $$ \delta:\mathbf{F}_2^n \rightarrow \{0,1\} $$ is defined as $$ \delta^{(n)}(x)=\begin{cases} 1 & x=0^n \\ 0 & others \end{cases} $$. Let $$ \mathbf{e}_i $$ denote the i-th unit vector.

Modulo Addition with an Initial Carry Bit and Additive Differential Probability

Let $$ \boxplus_b^{(n)}:\mathbf{F}_2^n \times \mathbf{F}_2^n \rightarrow \mathbf{F}_2^n $$ be the operation mapping $$ (x,y)\in \mathbf{F}_2^n \times \mathbf{F}_2^n $$ to

$$ x \boxplus_b^{(n)} y= x+y+b\,\textbf{mod}\,2^n $$

where $$ b \in \mathbf{F}_2 $$. For convenience, we use $$ x\boxplus y $$ to denote $$ x+y\,\textbf{mod}\,2^n $$.

For $$ (x,y) \in \mathbf{F}_2^n \times \mathbf{F}_2^n $$, the carry vector of $$ (x,y) $$ with initial carry bit $$ b \in \mathbf{F}_2 $$ is defined to be a $$ (n+1) $$-bit vector $$ \mathscr{c}_b(\mathbf{x},\mathbf{y})=(c_n,c_{n-1},\cdots,c_0) $$ such that

$$ \begin{equation*} c_i=\begin{cases} b, & i=0 \\ x_{i-1}y_{i-1} \oplus x_{i-1}c_{i-1} \oplus y_{i-1}c_{i-1} & 1 \le i \le n. \end{cases}. \end{equation*} $$

We call $$ \mathscr{c}_b(\mathbf{x},\mathbf{y})_n $$ the most significant carry of $$ x \boxplus_b^{(n)} y $$, denoted as $$ \hat{\mathscr{c}}_b(\mathbf{x},\mathbf{y}) $$, which is illustrated in Figure 2. Under such notations, $$ x \boxplus_b^{(n)} y= x \oplus y \oplus \lfloor\mathscr{c}_b({x},{y})\rfloor^{n} $$. Moreover,

$$ \mathscr{c}_b(\lfloor\mathbf{x}\rfloor^k,\lfloor\mathbf{y}\rfloor^k)=\lfloor\mathscr{c}_b(\mathbf{x},\mathbf{y})\rfloor^{k+1} $$

Figure 2. The $$ \hat{\mathscr{c}}_b(\mathbf{x},\mathbf{y}) $$.

is a $$ (k+1) $$-bit vector. Let $$ \boxminus^{(n)}:\mathbf{F}_2^n \times \mathbf{F}_2^n \rightarrow \mathbf{F}_2^n $$ be the operation mapping $$ (x,y)\in \mathbf{F}_2^n \times \mathbf{F}_2^n $$ to

$$ x \boxminus^{(n)} y= x-y\,\textbf{mod}\,2^n $$

Then, $$ \boxminus $$ has the following relationship with $$ \boxplus_b^{(n)} $$:

Theorem 0.1.

$$ \label{modminus} x \boxminus^{(n)} y = x \boxplus_1^{(n)} (y \oplus 1^n) $$

Partitions of $$ \mathbf{F}_2^k \times \mathbf{F}_2^k $$

Definition 0.1.Given $$ (a,b) \in \mathbf{F}_2^2 $$, $$ (u,v) \in \mathbf{F}_2^2 $$, and $$ (\alpha,\beta) \in \mathbf{F}_2^n \times \mathbf{F}_2^n $$, for $$ 1 \le k \le n $$, we use $$ \mathbf{D}^{(k)}_{\begin{matrix} u \lhd a\\ v \lhd b \end{matrix}}(\alpha,\beta) \subseteqq \mathbf{F}_2^k \times \mathbf{F}_2^k $$ to denote the set

$$ \{(\mathbf{x},\mathbf{y}) \in \mathbf{F}_2^k \times \mathbf{F}_2^k:\left(\hat{\mathscr{c}}_a(\mathbf{x},\lfloor\alpha\rfloor^{(k)}), \hat{\mathscr{c}}_b(\mathbf{y},\lfloor\beta\rfloor^{(k)}) \right)=(u,v)\}. $$

In fact, it represents a solution set of some equations, which is illustrated in Figure 3.

Figure 3. The equivalent form of the set $$ \mathbf{D}^{(k)}_{\begin{matrix} u \lhd a\\ v \lhd b \end{matrix}}(\alpha,\beta) $$.

Under the notation, we have

$$ \mathbf{D}^{(n)}_{\begin{matrix} u \lhd a\\ v \lhd b \end{matrix}}(\alpha,\beta)=\{(\mathbf{x},\mathbf{y}) \in \mathbf{F}_2^n \times \mathbf{F}_2^n:\left(\hat{\mathscr{c}}_a(\mathbf{x},\alpha), \hat{\mathscr{c}}_b(\mathbf{y},\beta) \right)=(u,v)\}. $$

and $$ \mathbf{D}^{(1)}_{\begin{matrix} u \lhd a\\ v \lhd b \end{matrix}}(\alpha_i,\beta_i)=\{({x},{y}) \in \mathbf{F}_2 \times \mathbf{F}_2:\left(\hat{\mathscr{c}}_a({x},\alpha_i), \hat{\mathscr{c}}_b({y},\beta_i) \right)=(u,v)\}\subseteqq \mathbf{F}_2 \times \mathbf{F}_2 $$, which is the solution of

$$ \begin{equation*} \begin{cases} x\alpha_i \oplus \alpha_i a \oplus xa =u \\ y\beta_i \oplus \beta_i b \oplus yb=v \end{cases}. \end{equation*} $$

The set $$ \mathbf{D}^{(n)}_{\begin{matrix} u \lhd a\\ v \lhd b \end{matrix}}(\alpha,\beta) $$ has the following property:

Lemma 0.1.For any fixed $$ (a,b) \in \mathbf{F}_2^2 $$ and $$ (\alpha,\beta) \in \mathbf{F}_2^n \times \mathbf{F}_2^n $$,

$$ \mathbf{F}_2^n \times \mathbf{F}_2^n= \bigcup\limits_{(u,v)\in \mathbf{F}_2^2}\mathbf{D}^{(n)}_{\begin{matrix} u \lhd a\\ v \lhd b \end{matrix}}(\alpha,\beta) $$

and $$ (u,v)=(u',v') $$ if and only if

$$ \mathbf{D}^{(n)}_{\begin{matrix} u \lhd a\\ v \lhd b \end{matrix}}(\alpha,\beta) \bigcap \mathbf{D}^{(n)}_{\begin{matrix} u' \lhd a\\ v' \lhd b \end{matrix}}(\alpha,\beta) \neq\varnothing. $$

Lemma 0.2.Let $$ \mathbf{D}^{(t)}_{\begin{matrix} b \lhd u\\ v \lhd 0 \end{matrix}}||\mathbf{D}^{(n-t)}_{\begin{matrix} u \lhd 0\\ a \lhd v \end{matrix}}(\alpha,\beta) $$ be the set of all $$ (\mathbf{x},\mathbf{y})\in \mathbf{F}_2^n \times \mathbf{F}_2^n $$ such that

(1) $$ \begin{equation} \begin{cases} & (\lfloor\mathbf{x} \rfloor^{t} , \lfloor \mathbf{y} \rfloor^{t})\in \mathbf{D}^{(t)}_{\begin{matrix} b \lhd u\\ v \lhd 0 \end{matrix}} (\lfloor\alpha \rfloor^{t} , \lfloor \beta \rfloor^{t}) \\ &(\lceil\mathbf{x} \rceil^{n-t} , \lceil \mathbf{y} \rceil^{n-t}) \in \mathbf{D}^{(n-t)}_{\begin{matrix} u \lhd 0\\ a \lhd v \end{matrix}} (\lceil\alpha \rceil^{n-t} , \lceil \beta \rceil^{n-t}) \end{cases} \end{equation} $$

which is illustrated in Figure 4. Then, the necessary and sufficient condition for

(2) $$ \mathbf{D}^{(t)}_{\begin{matrix} b \lhd u\\ v \lhd 0 \end{matrix}}||\mathbf{D}^{(n-t)}_{\begin{matrix} u \lhd 0\\ a \lhd v \end{matrix}}(\alpha,\beta) \bigcap \mathbf{D}^{(t)}_{\begin{matrix} b' \lhd u'\\ v' \lhd 0 \end{matrix}}||\mathbf{D}^{(n-t)}_{\begin{matrix} u' \lhd 0\\ a' \lhd v' \end{matrix}}(\alpha,\beta) \neq\varnothing $$

Figure 4. The equivalent form of the set $$ \mathbf{D}^{(t)}_{\begin{matrix} b \lhd u\\ v \lhd 0 \end{matrix}}||\mathbf{D}^{(n-t)}_{\begin{matrix} u \lhd 0\\ a \lhd v \end{matrix}}(\alpha,\beta) $$.

is $$ (u,v,a,b)=(u',v',a',b') $$. Moreover, we have

$$ \bigcup\limits_{(a,b)\in \mathbf{F}_2^2}\bigcup\limits_{(u,v)\in \mathbf{F}_2^2}\mathbf{D}^{(t)}_{\begin{matrix} b \lhd u\\ v \lhd 0 \end{matrix}}||\mathbf{D}^{(n-t)}_{\begin{matrix} u \lhd 0\\ a \lhd v \end{matrix}}(\alpha,\beta)=\mathbf{F}_2^n \times \mathbf{F}_2^n. $$

Proof. Equation 2 implies that

$$ \begin{equation*} \begin{cases} & \mathbf{D}^{(t)}_{\begin{matrix} b \lhd u\\ v \lhd 0 \end{matrix}} (\lfloor\alpha \rfloor^{t} , \lfloor \beta \rfloor^{t}) \bigcap \mathbf{D}^{(t)}_{\begin{matrix} b' \lhd u'\\ v' \lhd 0 \end{matrix}} (\lfloor\alpha \rfloor^{t} , \lfloor \beta \rfloor^{t}) \neq\varnothing \\ & \mathbf{D}^{(n-t)}_{\begin{matrix} u \lhd 0\\ a \lhd v \end{matrix}} (\lceil\alpha \rceil^{n-t} , \lceil \beta \rceil^{n-t}) \bigcap \mathbf{D}^{(n-t)}_{\begin{matrix} u' \lhd 0\\ a' \lhd v' \end{matrix}} (\lceil\alpha \rceil^{n-t} , \lceil \beta \rceil^{n-t})\neq\varnothing \end{cases} \end{equation*} $$

which implies $$ v=v' $$, $$ a=a' $$ and $$ u=u' $$, $$ b=b' $$ according to 0.1.

The second part of the lemma comes from the fact that any elements in $$ \mathbf{F}_2^n \times \mathbf{F}_2^n $$ must satisfy Equation 2 for some $$ (u,v,a,b) $$. □

The ARX construction

The ARX construction $$ \mathbf{F}_2^{2n} \rightarrow \mathbf{F}_2^{n} $$ is defined as:

$$ ARX(x,y,d,e)= \left((x \boxplus^{n} y )\lll d \right) \oplus y \lll e $$

which is illustrated in Figure 5, where $$ x,y \in \mathbf{F}_2^n $$, $$ 0 \le e,\; d <n $$.

Figure 5. The ARX construction $$ ARX(x,y,d,e) $$.

Remark 0.1.In FSE 2011 ^[20], the ARX construction $$ \mathbf{F}_2^{2n} \rightarrow \mathbf{F}_2^{2n} $$ is defined as:

$$ ARX(x,y,d,e)= \left((x \boxplus^{n} y )\lll d \right) \oplus y $$

Compared with the ARX construction $$ ARX(x,y,d,e) $$, there are two rotations before $$ \oplus $$ instead of one, namely $$ ARX(x,y,d,0) $$. We must point out that the ARX construction defined in FSE 2011 ^[20] is not suitable for some ARX ciphers, such as Alzette ^[5] or Speck ^[1].

The additive difference

Definition 0.2.Given a vectorial Boolean function $$ F:\mathbf{F}_2^n \rightarrow \mathbf{F}_2^m $$, the probability of additive difference with input difference $$ \alpha \in \mathbf{F}_2^n $$ and output difference $$ \beta \in \mathbf{F}_2^m $$ is defined as

$$ \Pr[\alpha \rightarrow {\beta}]^{F}=\frac{1}{2^n} \#\{x\in \mathbf{F}_2^n: F(x \boxplus^{(n)}\alpha) \boxminus^{n} F(x) =\beta \} $$

If we define the function $$ f:\mathbf{F}_2^{2n} \rightarrow \mathbf{F}_2^{2n} $$ as:

$$ f(x,y,d,e)= (x \lll d) \oplus (y \lll e) $$

which is illustrated in Figure 6. Then, for $$ ARX(x,y,d,e) $$, its probability of additive difference with input difference $$ (\alpha, \beta) \in \mathbf{F}_2^{2n} $$ and output difference $$ \gamma \in \mathbf{F}_2^n $$ has the following relationship:

$$ \Pr[(\alpha',\beta) \rightarrow {\gamma}]^{ARX}=\Pr[(\alpha,\beta) \rightarrow {\gamma}]^{f} $$

Figure 6. The function $$ f $$.

where $$ \alpha= \alpha' \boxplus^{n} \beta $$, $$ 0 \le e \le d <n $$.

PARTITION OF $$ \mathbf{F}_2^n \times \mathbf{F}_2^n $$

In order to know the probability of additive difference of the function $$ f(x,y) $$ with input difference $$ (\alpha, \beta) \in \mathbf{F}_2^{2n} $$ and output difference $$ \gamma \in \mathbf{F}_2^n $$, we need to know the number of solutions of the equation:

Firstly, we define the function value $$ \lambda^k(x,y,\alpha,\beta)_{a,b,c}:\mathbf{F}_2^{4k} \rightarrow \mathbf{F}_2^{k} $$ with three initial bits $$ a $$, $$ b $$, $$ c $$ as:

where $$ x,y,\alpha,\beta \in \mathbf{F}_2^k $$, and it can generate three carry bits:

which is illustrated in Figure 7.

Figure 7. The function $$ \lambda^k(x,y,\alpha, \beta)_{a,b,c} $$. On the right side, it is the simple form of $$ \lambda^k(x,y,\alpha, \beta)_{a,b,c} $$, where $$ \alpha $$, $$ x $$, $$ \beta $$, $$ y $$ represent the input, $$ a $$, $$ b $$, $$ c $$ represent the three initial bits, and $$ u $$, $$ v $$, $$ c $$ represent three carry bits.

Then, we define a subset of $$ \mathbf{D}^{(k)}_{\begin{matrix} u \lhd a\\ v \lhd b \end{matrix}}(\alpha,\beta) $$ :

Definition 0.3.Given $$ (a,b,c) \in \mathbf{F}_2^3 $$, $$ (u,v,s) \in \mathbf{F}_2^3 $$, and $$ (\alpha,\beta) \in \mathbf{F}_2^n \times \mathbf{F}_2^n $$, for $$ 1 \le k \le n $$, we use $$ \mathbf{S}^{(k)}_{\begin{matrix} u \lhd a\\ v \lhd b \\ s \lhd c\end{matrix}}(\alpha,\beta) \subseteqq \mathbf{D}^{(k)}_{\begin{matrix} u \lhd a\\ v \lhd b \end{matrix}}(\alpha,\beta) $$ to denote the set

For the set $$ \mathbf{S}^{(k)}_{\begin{matrix} u \lhd a\\ v \lhd b \\ s \lhd c\end{matrix}}(\alpha,\beta) $$, we have the following property:

Lemma 0.3.For any fixed $$ (a,b,u,v) \in \mathbf{F}_2^4 $$, $$ c \in \mathbf{F}_2 $$ and $$ (\alpha,\beta) \in \mathbf{F}_2^n \times \mathbf{F}_2^n $$,

and $$ s=s' $$, $$ v=v' $$, $$ u=u' $$ if and only if

For the function $$ g(x,y)^{(\alpha, \beta)}=f(x \boxplus^{n} \alpha,y \boxplus^{n} \beta,d,e) \boxminus^{n} f(x,y,d,e) $$, it can be repressed as bit level:

where $$ g_0=1 $$ and for $$ 1 \le i \le n $$, $$ g_i $$ is defined as:

Then, according to the expression of $$ g(x,y)^{(\alpha, \beta)} $$ in bit level, we have:

Lemma 0.4.

where

and

It is illustrated in Figure 8:

Figure 8. The equivalent form of $$ g(x,y)^{(\alpha, \beta)} $$. For instance, $$ 0 $$, $$ n-d-1 $$ behind the $$ \alpha $$ and $$ x $$ represent the substring of $$ \alpha $$ and $$ x $$ from $$ 1 $$-bit to $$ n-d $$ bit.

Lemma 0.5.For $$ d \ge e $$, let $$ \mathbf{S}^{(n-d)}_{\begin{matrix} a \lhd 0\\ b \lhd w \\ s \lhd z \end{matrix}}||\mathbf{S}^{(d-e)}_{\begin{matrix} u \lhd h\\ w \lhd 0 \\ z \lhd c \end{matrix}}||\mathbf{S}^{(e)}_{\begin{matrix} h \lhd a\\ v \lhd b \\ c \lhd 1 \end{matrix}}(\alpha,\beta) $$ be the set of all $$ (\mathbf{x},\mathbf{y})\in \mathbf{F}_2^n \times \mathbf{F}_2^n $$ such that

which is illustrated in Figure 9. Then, the necessary and sufficient condition for

Figure 9. The equivalent form of the set $$ \mathbf{S}^{(n-d)}_{\begin{matrix} a \lhd 0\\ b \lhd w \\ s \lhd z \end{matrix}}||\mathbf{S}^{(d-e)}_{\begin{matrix} u \lhd h\\ w \lhd 0 \\ z \lhd c \end{matrix}}||\mathbf{S}^{(e)}_{\begin{matrix} h \lhd a\\ v \lhd b \\ c \lhd 1 \end{matrix}}(\alpha,\beta) $$.

is $$ (a,h,u,b,v,w,c,z,s)=(a',h',u',b',v',w',c',z',s') $$. Moreover, we have

Proof. Equation 4 implies that

According to Lemma 0.2, we have $$ (h,u,w,v)=(h',u',w',v') $$. And $$ a=a' $$, $$ b=b' $$ according to Definition 0.2. Furthermore, $$ (c,z,s)=(c',z',s') $$.

The second part of the lemma comes from the fact that any elements in $$ \mathbf{F}_2^n \times \mathbf{F}_2^n $$ must satisfy Equation 4 for some $$ (a,h,u,b,v,w,c,z,s) $$. □

METHODS

Lemma 0.6.For the probability of additive difference of the function $$ f(x,y) $$ with input difference $$ (\alpha, \beta) \in \mathbf{F}_2^{2n} $$ and output difference $$ \gamma \in \mathbf{F}_2^n $$, $$ d \ge e $$, we have

where

and

Proof. According to Lemma 0.5, the $$ g(x,y)^{(\alpha,\beta)} $$ can be divided into three parts, which is illustrated in Figure 10. Then, we have:

Figure 10. $$ g(x,y)^{(\alpha,\beta)} $$.

Due to Lemma 0.3, it can be written as

□

How to calculate the $$ \Psi(a,b,w,z) $$, $$ \Phi(w,z,h,c) $$ and $$ \chi(h,c,a,b) $$

In this part, we will demonstrate how to calculate the $$ \Psi(a,b,w,z) $$, $$ \Phi(w,z,h,c) $$ and $$ \chi(h,c,a,b) $$.

For $$ (s,v,u,c,b,a) \in \mathbf{F}_2^6 $$, let

$$ \pi(\alpha_t,\beta_t,\gamma_t)_{4s+2v+u,4c+2b+a}=\sum\limits_{(x,y) \in \mathbf{S}^{(1)}_{\begin{matrix} u \lhd a\\ v \lhd b \\ s \lhd c\end{matrix}}(\alpha_t,\beta_t) } \delta^{(1)}(\alpha_t \oplus \beta_t \oplus a \oplus b \oplus c \oplus \gamma_t\oplus 1) =\delta^{(1)}(\alpha_t \oplus \beta_t \oplus a \oplus b \oplus c \oplus \gamma_t\oplus 1)\, \#\mathbf{S}^{(1)}_{\begin{matrix} u \lhd a\\ v \lhd b \\ s \lhd c\end{matrix}}(\alpha_t,\beta_t) $$

and matrix $$ M_{\alpha_t,\beta_t,\gamma_t}=(d'_{4s+2v+u,\;4c+2b+a})_{8\times8} $$ where

$$ d'_{4s+2v+u,\;4c+2b+a}=\frac{1}{4}\pi(\alpha_t,\beta_t,\gamma_t)_{4s+2v+u,\;4c+2b+a}. $$

Then, there are eight possible matrices:

$$ \begin{align*} & M_{000}=\frac{1}{4}\begin{pmatrix} 0 1 1 0 0 0 0 0 \\ 0 1 0 0 0 0 0 0 \\ 0 0 1 0 0 0 0 0 \\ 0 0 0 0 0 0 0 0 \\ 0 1 1 0 4 0 0 1 \\ 0 1 0 0 0 0 0 1 \\ 0 0 1 0 0 0 0 1 \\ 0 0 0 0 0 0 0 1 \\ \end{pmatrix} M_{001}=\frac{1}{4}\begin{pmatrix} 4 0 0 1 0 1 1 0\\ 0 0 0 1 0 1 0 0\\ 0 0 0 1 0 0 1 0\\ 0 0 0 1 0 0 0 0\\ 0 0 0 0 0 1 1 0\\ 0 0 0 0 0 1 0 0\\ 0 0 0 0 0 0 1 0\\ 0 0 0 0 0 0 0 0\\ \end{pmatrix} M_{010}=\frac{1}{4}\begin{pmatrix}1 0 0 0 0 0 0 0\\ 0 0 0 0 0 0 0 0\\ 1 0 0 1 0 0 0 0\\ 0 0 0 1 0 0 0 0\\ 1 0 0 0 0 1 0 0\\ 0 0 0 0 0 1 0 0\\ 1 0 0 1 0 1 4 0\\ 0 0 0 1 0 1 0 0\\ \end{pmatrix} M_{011}=\frac{1}{4}\begin{pmatrix} 0 1 0 0 1 0 0 0\\ 0 1 0 0 0 0 0 0\\ 0 1 4 0 1 0 0 1\\ 0 1 0 0 0 0 0 1\\ 0 0 0 0 1 0 0 0\\ 0 0 0 0 0 0 0 0\\ 0 0 0 0 1 0 0 1\\ 0 0 0 0 0 0 0 1\\ \end{pmatrix} \\ & M_{100}=\frac{1}{4}\begin{pmatrix} 1 0 0 0 0 0 0 0\\ 1 0 0 1 0 0 0 0\\ 0 0 0 0 0 0 0 0\\ 0 0 0 1 0 0 0 0\\ 1 0 0 0 0 0 1 0\\ 1 0 0 1 0 4 1 0\\ 0 0 0 0 0 0 1 0\\ 0 0 0 1 0 0 1 0\\ \end{pmatrix} M_{101}=\frac{1}{4}\begin{pmatrix} 0 0 1 0 1 0 0 0\\ 0 4 1 0 1 0 0 1\\ 0 0 1 0 0 0 0 0\\ 0 0 1 0 0 0 0 1\\ 0 0 0 0 1 0 0 0\\ 0 0 0 0 1 0 0 1\\ 0 0 0 0 0 0 0 0\\ 0 0 0 0 0 0 0 1\\ \end{pmatrix} M_{110}=\frac{1}{4}\begin{pmatrix} 0 0 0 0 0 0 0 0\\ 0 1 0 0 0 0 0 0\\ 0 0 1 0 0 0 0 0\\ 0 1 1 0 0 0 0 0\\ 0 0 0 0 1 0 0 0\\ 0 1 0 0 1 0 0 0\\ 0 0 1 0 1 0 0 0\\ 0 1 1 0 1 0 0 4\\ \end{pmatrix} M_{111}=\frac{1}{4}\begin{pmatrix} 1 0 0 0 0 0 0 0\\ 1 0 0 0 0 1 0 0\\ 1 0 0 0 0 0 1 0\\ 1 0 0 4 0 1 1 0\\ 0 0 0 0 0 0 0 0\\ 0 0 0 0 0 1 0 0\\ 0 0 0 0 0 0 1 0\\ 0 0 0 0 0 1 1 0\\ \end{pmatrix} \end{align*} $$

In addition, let

$$ F^{(k)}_{(a,b,c)}(\lfloor\alpha \rfloor^k, \lfloor\beta \rfloor^k,\lfloor\gamma \rfloor^k, \lfloor x\rfloor^k, \lfloor y \rfloor^k) =\delta^{(k)}\left( \lambda^k(\lfloor x\rfloor^k, \lfloor y \rfloor^k,\lfloor\alpha \rfloor^k, \lfloor\beta \rfloor^k)_{(a,b,c)} \oplus \lfloor\gamma \rfloor^k \right) $$

For $$ 1 \le k \le n $$, let $$ \mathbf{V}^k=(d^k_{4s+2v+u})_{1\times8} $$ be the column vector, where

$$ d_{4s+2v+u}=\frac{1}{2^{2k}}\sum\limits_{(\lfloor x\rfloor^k,\lfloor y \rfloor^k) \in \mathbf{S}^{(k)}_{\begin{matrix} u \lhd a\\ v \lhd b \\ s \lhd c\end{matrix}} (\lfloor\alpha \rfloor^k,\lfloor\beta \rfloor^k)} F^{(k)}_{(a,b,c)}(\lfloor\alpha \rfloor^k, \lfloor\beta \rfloor^k,\lfloor\gamma \rfloor^k, \lfloor x\rfloor^k,\lfloor y \rfloor^k) $$

Lemma 0.7.For $$ 1 \le k \le n $$, $$ \mathbf{V}^{k+1}=M_{\alpha_k,\beta_k,\gamma_k}\;\mathbf{V}^k $$ and $$ \mathbf{V}^{1}=M_{\alpha_0,\beta_0,\gamma_0}\mathbf{e}_{4c+2b+a} $$.

Proof. For $$ a',b',c' \in \mathbf{F}_2 $$, we have:

$$ \begin{align*} &\sum\limits_{(\lfloor x\rfloor^{k+1},\lfloor y \rfloor^{k+1}) \in \mathbf{S}^{(k+1)}_{\begin{matrix} a' \lhd a\\ b' \lhd b \\ c' \lhd c\end{matrix}} (\lfloor\alpha \rfloor^{k+1},\lfloor\beta \rfloor^{k+1})} F^{(k+1)}_{(a,b,c)}(\lfloor\alpha \rfloor^{k+1}, \lfloor\beta \rfloor^{k+1},\lfloor\gamma \rfloor^{k+1}, \lfloor x\rfloor^{k+1},\lfloor y \rfloor^{k+1}) \\ =& \sum\limits_{i,j,z \in \mathbf{F}_2}\; \sum\limits_{(\lfloor x\rfloor^{k+1},\lfloor y \rfloor^{k+1}) \in \mathbf{S}^{(1)}_{\begin{matrix} a' \lhd i\\ b' \lhd j \\ c' \lhd z\end{matrix} } (\alpha_{k+1},\beta_{k+1}) ||\mathbf{S}^{(k)}_{\begin{matrix} i \lhd a\\ j \lhd b \\ z \lhd c\end{matrix} } (\lfloor\alpha \rfloor^{k},\lfloor\beta \rfloor^{k}) } F^{(k+1)}_{(a,b,c)}(\lfloor\alpha \rfloor^{k+1}, \lfloor\beta \rfloor^{k+1},\lfloor\gamma \rfloor^{k+1}, \lfloor x\rfloor^{k+1},\lfloor y \rfloor^{k+1})\\ \end{align*} $$

And the $$ F^{(k+1)}_{(a,b,c)}(\lfloor\alpha \rfloor^{k+1}, \lfloor\beta \rfloor^{k+1},\lfloor\gamma \rfloor^{k+1}, \lfloor x\rfloor^{k+1},\lfloor y \rfloor^{k+1}) $$ can be divided into two parts, which is illustrated in Figure 11.

Figure 11. $$ F^{(k+1)}_{(a,b,c)}(\lfloor\alpha \rfloor^{k+1}, \lfloor\beta \rfloor^{k+1},\lfloor\gamma \rfloor^{k+1}, \lfloor x\rfloor^{k+1},\lfloor y \rfloor^{k+1}) $$.

Thus,

$$ \begin{align*} &\sum\limits_{(\lfloor x\rfloor^{k+1},\lfloor y \rfloor^{k+1}) \in \mathbf{S}^{(k+1)}_{\begin{matrix} a' \lhd a\\ b' \lhd b \\ c' \lhd c\end{matrix}} (\lfloor\alpha \rfloor^{k+1},\lfloor\beta \rfloor^{k+1})} F^{(k+1)}_{(a,b,c)}(\lfloor\alpha \rfloor^{k+1}, \lfloor\beta \rfloor^{k+1},\lfloor\gamma \rfloor^{k+1}, \lfloor x\rfloor^{k+1},\lfloor y \rfloor^{k+1}) \\ =& \sum\limits_{i,j,z \in \mathbf{F}_2} \left( \sum\limits_{(x,y) \in \mathbf{S}^{(1)}_{\begin{matrix} a' \lhd i\\ b' \lhd j \\ c' \lhd z\end{matrix}}(\alpha_k,\beta_k) } \delta^{(1)}(\alpha_k \oplus \beta_k \oplus i \oplus j \oplus z \oplus \gamma_k) \right) \cdot \left(\sum\limits_{(\lfloor x\rfloor^{k},\lfloor y \rfloor^{k}) \in \mathbf{S}^{(k)}_{\begin{matrix} i \lhd a\\ j \lhd b \\ z \lhd c\end{matrix} } (\lfloor\alpha \rfloor^{k},\lfloor\beta \rfloor^{k}) } F^{(k)}_{(a,b,c)}(\lfloor x\rfloor^{k}, \lfloor y \rfloor^{k},\lfloor\alpha \rfloor^{k}, \lfloor\beta \rfloor^{k},\lfloor\gamma \rfloor^{k} ) \right) \\ =& 2^{k+1}\sum\limits_{i,j,z \in \mathbf{F}_2} \pi(\alpha_k,\beta_k,\gamma_k)_{4c'+2b'+a',\;4z+2j+i}\cdot d^{k}_{4z+2j+i} \\ \end{align*} $$

Thus, for $$ 1 \le k \le n $$, we have $$ \mathbf{V}^{k+1}=M_{\alpha_k,\beta_k,\gamma_k}\;\mathbf{V}^k $$.

For $$ \mathbf{V}^{1}=M_{\alpha_0,\beta_0,\gamma_0}\mathbf{e}_{4c+2b+a} $$, it holds from the definition of $$ \mathbf{V}^{1} $$ and $$ M_{\alpha_0,\beta_0,\gamma_0} $$. □

Then, according to Lemma 0.7, we have:

Lemma 0.8.

$$ \psi(a,b,w,z)=\sum\limits_{s \in \mathbf{F}_2} \mathbf{e^T_{4s+2b+a}} \;\prod\limits_{i=d}^{n-1}M_{\alpha_{n-d+i\;\textbf{mod}\;n},\beta_{n-e+i\;\textbf{mod}\;n}, \gamma_{i}}\; \mathbf{e_{4z+2w}} $$

Lemma 0.9.

$$ \psi(w,z,h,c)=\sum\limits_{u \in \mathbf{F}_2} \mathbf{e^T_{4z+2w+u}} \;\prod\limits_{i=e}^{d-1}M_{\alpha_{n-d+i\;\textbf{mod}\;n},\beta_{n-e+i\;\textbf{mod}\;n}, \gamma_{i}}\; \mathbf{e_{4c+h}} $$

Lemma 0.10.

$$ \chi(h,c,a,b)=\sum\limits_{v \in \mathbf{F}_2} \mathbf{e^T_{4c+2v+h}} \;\prod\limits_{i=0}^{e-1}M_{\alpha_{n-d+i\;\textbf{mod}\;n},\beta_{n-e+i\;\textbf{mod}\;n}, \gamma_{i}}\; \mathbf{e_{4+2b+a}} $$

RESULT

According to the lemma in the previous section, we can get the calculation of additive differential probability of ARX construction $$ \Pr[(\alpha',\beta) \rightarrow {\gamma}]^{ARX} $$, which is the main result of our paper:

Theorem 0.2.For $$ \alpha,\beta, \gamma \in \mathbf{F}_2^n $$, when $$ d\ge e $$, the $$ \Pr[(\alpha,\beta) \rightarrow {\gamma}]^{f} $$ ($$ \Pr[(\alpha',\beta) \rightarrow {\gamma}]^{ARX} $$, $$ \alpha= \alpha' \boxplus^{n} \beta $$) can be calculated as:

when $$ d \le e $$, the $$ \Pr[(\alpha,\beta) \rightarrow {\gamma}]^{f} $$ ($$ \Pr[(\alpha',\beta) \rightarrow {\gamma}]^{ARX} $$, $$ \alpha= \alpha' \boxplus^{n} \beta $$) can be calculated as:

where

Proof. When $$ d \ge e $$, according to Lemma 0.6, Lemma 0.8, Lemma 0.9, and Lemma 0.10, we have:

When $$ d \le e $$, the proof is similarity. □

DISCUSSION

In this paper, we study the additive differential probabilities of ARX construction: $$ (x \boxplus y) \lll d \oplus y \lll e $$. By using an artful partition of $$ \mathbf{F}_2^m \times \mathbf{F}_2^m $$ into subsets, where the elements in each subset fulfill certain equations, we give a method for calculating the additive differential probabilities of ARX constructions. The time complexity of this method is equal to the complexity of $$ 4n $$$$ 8 \times 8 $$ matrix multiplications.

DECLARATIONS