expressiveness.tex

\section{Expressiveness}
\label{sec:expressiveness}

A major advantage of ARX cipher family is the expressiveness
\footnote{The content is inspired by a question on StackExchange:
\url{https://crypto.stackexchange.com/questions/51412/}}.
With only three primitives, ARX cipher is able to perform almost all confusion and
diffusion techniques. Theoretically, it is shown that $\textit{ARX}(n)$ primitives
can simulate all permutations over $\mathbb{Z}_{2^n}$, hence replace the S-box in
block cipher constructions. A more general conclusion states that, $\textit{ARX}(n)$
can represent all functions $\mathbb{Z}_{2^n}^m\rightarrow\mathbb{Z}_{2^n}$ for any
positive integer $m$.

\subsection{Simulating Permutations}

A \textit{permutation} of the finite set $X$ is a bijective function $\pi:\textit{X}\rightarrow X$.
Such $\pi$ is called a permutation over $X$. In other word, permutation is the
rearrangement of a finite sequence. It is trivial to see that all permutations can be
generated by solely swapping operations on any other permutation. The swapping on a
finite sequence is defined as follow:

\begin{definition}
Let sequence $X=(x_1,x_2,\cdots,x_n)$, \textit{swapping} two elements $x_i$, $x_j$ in
$X$ resulting another sequence $X'=(x'_1,x'_2,\cdots,x'_n)$ such that:
\begin{align*}
x_i &= x'_j \\
x_j &= x'_i \\
x_k &= x'_k\ \mathrm{for}\ k\notin\{i,j\}
\end{align*}
\end{definition}

Many block ciphers adopt permutations as the nonlinear components, which also called
the \textit{S-boxes} \cite{stinson2005cryptography}. ARX cipher obtains its nonlinearity
from the modular addition, which is able to form (or \textit{simulate}) more complicated
nonlinear components. A nice property of ARX family states that, it can simulate all
permutations over the message space:

\begin{theorem}
\label{thm:perm}
For all permutations $\pi$ over $\mathbb{Z}_{2^n}$, $\pi\in\textit{ARX}(n)$.
\end{theorem}

Given arbitrary permutation, say that, the permutation in natural ordering, it is able to
generate any desired permutation by a pile of swapping operations on specific pairs of
permutation elements. Then, by showing swapping can be realized by ARX operations,
Theorem \ref{thm:perm} can be proven:

\begin{proof}
We proof this by construction, that is, we will construct a function $\sigma$ such that
$\sigma\textit{(X)}$ swaps two particular elements in the permutation $X$. Note that
$\sigma$ doesn't consider the positions of the elements being swapped, however, since all
elements in a permutation are unique, this definition does not introduce any ambiguity.

The problem can therefore be simplified as, constructing an ARX function $\sigma$ such
that, for input pair $(a,b)$, there are $\sigma(a)\textit{=}b$, $\sigma(b)\textit{=}a$,
and $\sigma(x)\textit{=}x$ for $x\notin\{a,b\}$. Denote this function by $f_{a,b}(x)$.
Given multiple such functions, their composition is thus a permutation over the domain.

Without loss of generality, let $a\neq b$. For simplicity, let $x-y=x+(2^n-y)$, and
$\mathrm{r}^{-b}(x)=\mathrm{r}^{n-b}(x)$ (the right rotation). We then construct
$f_{a,b}(x)$ by the following routine:

\begin{enumerate}
\setlength\partopsep{0em}
\setlength\topsep{0em}
\setlength\itemsep{0em}
\setlength\parskip{0em}
\item let $a'=0$, $b'=b-a$, the base function $f_0(x)\textit{=}x-a$
\item find the integer $i$ such that $\mathrm{r}^{-i}(b')$ is an odd number, set
$b'=\mathrm{r}^{-i}(b')$ and function $f_1(x)\textit{=}\mathrm{r}^{-i}(f_0(x))$, denoted
by $f_1\textit{=}\mathrm{r}^{-i}(f_0)$
\item \label{enum:loopcond} loop Step \ref{enum:loop} for $b'\neq1$, otherwise, go to
Step \ref{enum:loopout}
\item \label{enum:loop} let $b'=(b'\oplus1)-1$, function $f_i\textit{=}(f_{i-1}\oplus1)-1$
\item \label{enum:loopout} let $f_k=f_{i}+2^n-2$, and the auxiliary function
$g(x)=\mathrm{r}^1(\mathrm{r}^{-1}(x+2)-1)$
\item output function $\sigma=f_k^{-1}(g(f_k))$ as $f_{a,b}$
\end{enumerate}

\noindent Here we take $f_i$ as the last function when the looping condition at Step
\ref{enum:loopcond} no longer holds. Also notice that $g(x)$ is equivalent to swapping
function $f_{2^n-2,2^n-1}(x)$. The inverse function $f_k^{-1}$ can be easily calculated
since $f_k$ is a composition of ARX primitives.

To see $\sigma$ swap $(a,b)$, calculate the following functions:

\begin{equation*}
\setlength{\abovedisplayshortskip}{0em}
\setlength{\abovedisplayskip}{0em}
\begin{split}
f_0(a) &= 0\\
f_1(a) &= 0\\
f_i(a) &= 0\\
f_k(a) &= 2^n-2\\
g(f_k(a)) &= 2^n-1\\
\end{split}
\quad\quad
\begin{split}
f_0(b) &= b-a\\
f_1(b) &= (b-a)/2^i\\
f_i(b) &= 1\\
f_k(b) &= 2^n-1\\
g(f_k(b)) &= 2^n-2\\
\end{split}
\end{equation*}

\noindent Notice that $f_k(b)=2^n-1$ indicates the inverse function $f_k^{-1}(2^n-1)=b$,
hence $\sigma(a)=f_k^{-1}(g(f_k(a)))=b$. Similarly, there are $\sigma(b)=a$.

For $x\notin\{a,b\}$, there are $f_k(x)\notin\{2^n-2,2^n-1\}$ and thus $g(x)=x$. It
follows that $\sigma(x)=f_k^{-1}(g(f_k(x)))=f_k^{-1}(f_k(x))=x$ hence complete the proof.
\end{proof}

A Python3 implementation of the above construction is presented in Appendix
\ref{ssec:permarx}, it shows that this construction is feasible at software level.

\subsection{Completeness of \textbf{\textit{ARX}(n)}}

A more general statement regarding the expressiveness of ARX ciphers is given as:

\begin{theorem}
\label{thm:func}
For all function $f:\mathbb{Z}_{2^n}\rightarrow\mathbb{Z}_{2^n}$, $f\in\textit{ARX}(n)$.
\end{theorem}

Formally, it is said that ARX operations are functionally complete in the set of
functions over $\mathbb{Z}_{2^n}$ \cite{khovratovich2010rotational}. Khovratovich and
Nikoli{\'c} give a proof by construction for this theorem\footnote{the proof here does
not strictly follow the origin, as it has several mistakes and is in different notation}:

\begin{proof}
Given a sequence $X=x_1x_2\cdots x_n$, the task is to compute all functions $F(X)$ via
ARX primitives.

Firstly, let $$s_i(X)=\mathrm{r}^1\Bigg(\sum^{2^{n-1}}\mathrm{r}^i(X)\Bigg)$$ which
moves the $i$-th bit of X to the rightmost while keeps all other bits 0. To see this,
note that the innermost $\mathrm{r}^i(X)=x_{i+1}...x_nx_1...x_i$, adding itself by
$2^{n-1}$ times is equivalent to applying left-shifting by $n-1$ bits, that results
in $x_i$ at the leftmost while all other bits are $0$s. In other word, $s_i(X)=00...0x_i$.

Then define function $$M_k(X,Y)=\mathrm{r}^{-1}\Bigg(\sum^2\mathrm{r}^{-1}(s_k(X)+s_k(Y))\Bigg)$$
for two sequences $X$ and $Y$. $M_k$ compute the product of two bits $x_k$ and $y_k$,
\ie, $M_k(X,Y)=x_ky_k$. This is equivalent to the bitwise-and of $x_k$ and $y_k$.
The innermost sum $s_k(X)+s_k(Y)=00...0(x_ky_k)(x_k\oplus y_k)$. By rotating it by 1
bit and multiplying by 2, the product $x_ky_k$ is left at the $n\textrm{-}1$-th bit.

Next, compute the equivalence trial $$j_C(X)=\begin{cases}
1\textrm{ , if }X=C=c_1c_2...c_n\\
0\textrm{ , otherwise}\\
\end{cases}$$ the function can be realized by function $M_k$ and constant 1, that is,
$j_C(X)=\Big[\bigoplus_{i=1}^nM_i(X,C)\Big]\oplus1$.

Finally, let function $J_{C_1,C_2}(X)=C_2\cdot j_{C_1}(X)$, that evaluates to $C_2$ if
$X=C_1$ and to 0 for other values. The output function is $f=J_{\textit{X}, F(\textit{X})}$
\end{proof}

Actually, Khovratovich and Nikoli{\'c} even proof that all functions can be realized by
only $AR(n)$. This is proofed by the fact that xor can be realized with $AR$ operations.
The reader may refer \cite{khovratovich2010rotational} for the complete proof of this
statement.