Cryptanalytic invertibility of two-argument functions

N. Yu. Berdnikova ; I. A. Pankratova

Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 67-71

Résumé

Tests of cryptanalytic invertibility of all possible types for functions $g: D_1\times D_2\to D$ are proposed. Let $G_a=\{g(a,x_2): x_2\in D_2\}$ for any $a\in D_1$. Then: 1) function $g$ is invertible with respect to the variable $x_1$ of the type $\forall\forall$ iff $\forall a, b\in D_1$ ($a\ne b\Rightarrow G_a\cap G_b=\varnothing$); 2) function $g$ is invertible with respect to the variable $x_1$ of the type $\forall\exists$ iff there exists a mapping $\varphi$ such that the mapping $a\mapsto g(a, \varphi(a))$ is injective; 3) function $g$ is invertible with respect to the variable $x_2$ of the type $\exists\forall$ iff $|G_a|=|D_2|$ for some value $a\in D_1$. Algorithms for constructing a recovering function and generating invertible functions are formulated; some estimates of the number of invertible functions are given.

Détail

Keywords: cryptanalytic invertibility, invertibility test, recovering function.