On Multivariate Cryptosystems Based on Computable Maps with Invertible Decomposition

Let K be a commutative ring and K^n be a space over K of dimension n. We introduce the concept of a family of multivariate maps f(n) of K^n into itself with invertible decomposition.If f(n) is computable in polynomial time then it can be used as the public rule and the invertible decomposition provides a private key in f(n) based public key infrastructure. Requirementsof polynomial ity of degree and density for f(n) allow to estimate the complexity of encryption procedurefor a public user. The concepts of a stable family and a family of increasing order are motivatedby the studies of discrete logarithm problem in the Cremona group. The statement on the existenceof families of multivariate maps of polynomial degree and polynomial density of increasing order with the invertible decomposition is proved. The proof is supported by explicite construction which canbe used as a new cryptosystem. The presented multivariate encryption maps are induced by special walks in the algebraically dened extremal graphs A(n;K) and D(n;K) of increasing girth.