Theoretical Backgrounds of Applied Discrete Mathematics

On cryptanalytic invertibility of discrete functions

I. A. Pankratova, A. D. Sorokoumova

Tomsk State University, Tomsk, Russia

Abstract: The function $g(x_1,\ldots,x_n)$ is invertible with respect to the variable $x_k$ of type $K_1\ldots K_n$, where $k\in\{1,\ldots,n\}$, $K_i\in\{\exists,\forall\}$ and $K_k=\forall$, if there exists a recovery function $f$ such that the invertibility condition is true:
\begin{equation*} K_1x_1\ldots K_nx_n \big(f(g(x_1,\ldots,x_n))=x_k\big). \end{equation*}
Criteria for cryptanalytic invertibility of functions $g:D_1\times D_2\times D_3\to D$ are proven: 1) a function $g$ is invertible with respect to the variable $x_1$ of the type $\forall\forall\exists$ iff there is a mapping $\varphi:D_1\times D_2\to D_3$ such that the following condition is satisfied:
$$\forall a,c\in D_1 \forall b,d\in D_2 \big(a\neq c\ \Rightarrow\ g(a,b,\varphi(a,b))\neq g(c,d,\varphi(c,d))\big);$$
2) a function $g$ is invertible with respect to the variable $x_1$ of the type $\forall\exists\forall$ iff there is a mapping $\varphi:D_1\to D_2$ such that the following condition is satisfied:
$$\forall a,c\in D_1 \forall b,d\in D_3 \big(a\neq c\ \Rightarrow\ g(a,\varphi(a),b)\neq g(c,\varphi(c),d)\big);$$
3) a function $g$ is invertible with respect to the variable $x_3$ of the type $\forall\exists\forall$ iff there is a mapping $\varphi:D_1\to D_2$ such that the following condition is satisfied:
$$\forall a,c\in D_1 \forall b,d\in D_3 \big(b\neq d\ \Rightarrow\ g(a,\varphi(a),b)\neq g(c,\varphi(c),d)\big);$$
4) a function $g$ is invertible with respect to the variable $x_2$ of the type $\exists\forall\forall$ iff there is $a\in D_1$ such that the following condition is satisfied ($G^{(a,b)}=\{g(a,b,x_3):x_3\in D_3\}$):
$$\forall b,d\in D_2 \big(b\neq d\ \Rightarrow\ G^{(a,b)}\cap G^{(a,d)}=\emptyset\big);$$
5) a function $g$ is invertible with respect to the variable $x_2$ of the type $\exists\forall\exists$ iff there are $a\in D_1$ and a mapping $\varphi:D_2\to D_3$ such that the following condition is satisfied:
$$\forall b,d\in D_2 \big(b\neq d\ \Rightarrow\ g(a,b,\varphi(b))\neq g(a,d,\varphi(d))\big).$$
Algorithms for constructing a recovery function and generating invertible functions are formulated too.

Keywords: cryptanalytic invertibility, invertibility criterion, recovery function.

UDC: 519.7

DOI: 10.17223/20710410/69/3