Asymmetric cryptosystems on Boolean functions

G. P. Agibalov ; I. A. Pankratova

Prikladnaâ diskretnaâ matematika, no. 2 (2018), pp. 23-33.

Résumé

Here, we define an asymmetric substitution cryptosystem combining both a public key cipher and a signature scheme with the functional keys. A public key in the cryptosystem is a vector Boolean function $f(x_1,\dots,x_n)$ of a dimension $n$. This function is obtained by permutation and negation operations on variables and coordinate functions of a bijective vector Boolean function $g(x_1,\dots,x_n)=(g_1(x_1,\dots,x_n),\dots,g_n(x_1,\dots,x_n))$. The function $g$ is called a generating function of the cryptosystem. For each $i\in\{1,\dots,n\}$, its coordinate function $g_i(x_1,\dots,x_n)$ is assumed to be specified in a constructive way and to have a polynomial (in $n$) complexity. A private key of the cryptosystem is the function $f^{-1}$, that is, the inverse of $f$. The existence of $f^{-1}$ follows from the bijectiveness of $g$ and preserving this property by permutation and negation operations. Function $g$ and its coordinates $g_1,\dots,g_n$ are public parameters of the cryptosystem. (A variant of the cryptosystem allows to include them into the private key). Of course, the permutation and negation operations by which a public key is computed from the generating function must be secret as private exponents in RSA and ElGamal cryptosystems. A block $P$ of a plaintext is encrypted to a block $C$ of a ciphertext by the rule $C=f(P)$, and $C$ is decrypted to $P$ by the rule $P=f^{-1}(C)$. A signature on a message $M$ is computed as $S = f^{-1}(P)$, and its validation is proved by verifying the equality $M=f(S)$. This cryptosystem is believed to resist classical and quantum computers attacks. Its security is based on the difficulty of inverting large bijective vector Boolean functions. Cryptanalysis of the cryptosystem shows that its computational complexity can reach the value O$(n!2^n)$.

Détail

Keywords: vector Boolean functions, invertibility, asymmetric substitution cryptosystem
Mots-clés : cryptanalysis.

Bibliographie

[1] Tao R., Finite Automata and Application to Cryptography, Springer, Berlin–Heidelberg, 2009, 411 pp.

[2] Agibalov G. P., “Substitution block ciphers with functional keys”, Prikladnaya Diskretnaya Matematika, 2017, no. 38, 57–65 | DOI | MR

[3] Agibalov G. P., “Methods for solving systems of polynomial equations over a finite field”, Vestnik TSU. Prilozhenie, 2006, no. 17, 4–9

[4] Agibalov G. P., “Logical equations in cryptanalysis of key stream generators”, Vestnik TSU. Prilozhenie, 2003, no. 6, 31–41