Asymmetric cryptosystems on Boolean functions | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 40. DOI: 10.17223/20710410/40/3

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\,... ,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\,..., x_n) = = (gi(x\,... ,x_n),... ,g_n(xi,... ,x_n)). The function g is called a generating function of the cryptosystem. For each i e {1,..., n}, its coordinate function gi(x\,..., 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 /^_1, that is, the inverse of /. The existence of f~^l follows from the bijectiveness of g and preserving this property by permutation and negation operations. Function g and its coordinates gi,...,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 С of a ciphertext by the rule С = f(P), and С is decrypted to P by the rule P = f~^l(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 0(n!2^ra).