Cryptanalytic invertibility of three-argument functions

I. A. Pankratova ; A. D. Sorokoumova

Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 44-48

Résumé

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.

Détail

Keywords: cryptanalytic invertibility, invertibility test, recovering function.

Bibliographie

[1] Agibalov G. P., “Cryptanalytical finite automaton invertibility with finite delay”, Prikladnaya diskretnaya matematika, 2019, no. 46, 27–37 | MR | Zbl

[2] Agibalov G. P., “Problems in theory of cryptanalytical invertibility of finite automata”, Prikladnaya diskretnaya matematika, 2020, no. 50, 62–71 | MR | Zbl

[3] Agibalov G. P., “Cryptanalytic concept of finite automaton invertibility with finite delay”, Prikladnaya diskretnaya matematika, 2019, no. 44, 34–42 | MR | Zbl

[4] Fomichev V. M., Metody diskretnoi matematiki v kriptologii, Dialog-MIFI, M., 2010, 424 pp.

[5] Berdnikova N. Yu., Pankratova I. A., “Kriptoanaliticheskaya obratimost funktsii dvukh argumentov”, Prikladnaya diskretnaya matematika. Prilozhenie, 2021, no. 14, 67–71