On Multivariate Cryptosystems Based on Computable Maps with Invertible Decomposition

Abstract

Let K be a commutative ring and K^n be a space over K of dimension n. Weintroduce 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 theinvertible 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 withthe 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 specialwalks in the algebraically dened extremal graphs A(n;K) and D(n;K) of increasing girth.