This article is cited in 1 paper

Discrete Functions

Cryptanalytic invertibility of three-argument functions

I. A. Pankratova, A. D. Sorokoumova

Tomsk State University

Abstract: Tests of cryptanalytic invertibility for functions $g:D_1\times D_2\times D_3\to D$ are proposed: 1) function $g$ is invertible with respect to the variable $x_1$ of the type $\forall\forall\exists$ iff there is a mapping $\phi: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,\phi(a,b))\neq g(c,d,\phi(c,d))\big);$$
2) function $g$ is invertible with respect to the variable $x_1$ of the type $\forall\exists\forall$ iff there is a mapping $\phi: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,\phi(a),b)\neq g(c,\phi(c),d)\big);$$
3) function $g$ is invertible with respect to the variable $x_3$ of the type $\forall\exists\forall$ iff there is a mapping $\phi: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,\phi(a),b)\neq g(c,\phi(c),d)\big);$$
4) 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:
$$\forall b,d\in D_2 \forall y,z\in D_3 \big(b\neq d\ \Rightarrow\ g(a,b,y)\neq g(a,d,z)\big);$$
5) 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 $\phi: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,\phi(b))\neq g(a,d,\phi(d))\big).$$
Algorithms for constructing a recovering function and generating invertible functions are formulated too.

Keywords: cryptanalytic invertibility, invertibility test, recovering function.

UDC: 519.7

DOI: 10.17223/2226308X/17/11