Paper 2022/1537

On Extremal Algebraic Graphs and Multivariate Cryptosystems

Abstract

Multivariate rule x_i -> f_i, i = 1, 2, ..., n, f_i from K[x_1, x_2, ..., x_n] over commutative ring K defines endomorphism σ_n of K[x_1, x_2, ..., x_n] into itself given by its values on variables x_i. Degree of σ_n can be defined as maximum of degrees of polynomials f_i. We say that family σ_n, n = 2, 3, .... has trapdoor accelerator ^nT if the knowledge of the piece of information ^nT allows to compute reimage x of y = σ_n(x) in time O(n^2). We use extremal algebraic graphs for the constructions of families of automorphisms σ_n with trapdoor accelerators and (σ_n)^{−1} of large order. We use these families for the constructions of new multivariate public keys and protocol based cryptosystems of El Gamal type of Postquantum Cryptography. Some of these cryptosystems use as encryption tools families of endomorphisms σn of unbounded degree such that their restriction on the varieties (K^∗)^n are injective. As usual K^∗ stands for the multiplicative group of commutative ring K with the unity. Spaces of plaintexts and ciphertexts are (K^∗)^n and K^n. Security of such cryptosystem of El Gamal type rests on the complexity of word decomposition problem in the semigroup of Eulerian endomorphisms of K[x_1, x_2; ... , x_n].