RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2021 Issue 14, Pages 67–71 (Mi pdma564)

This article is cited in 1 paper

Mathematical Methods of Cryptography

Cryptanalytic invertibility of two-argument functions

N. Yu. Berdnikova, I. A. Pankratova

Tomsk State University

Abstract: 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.

Keywords: cryptanalytic invertibility, invertibility test, recovering function.

UDC: 519.7

DOI: 10.17223/2226308X/14/14



© Steklov Math. Inst. of RAS, 2024