×

On multivariate public keys based on a pair of transformations with density gap. (English) Zbl 1413.94053

Summary: We propose an algorithm of generation of the stable families of bijective polynomial maps \(f(n)\) of the \(n\)-dimensional affine space over a commutative ring \(K\) together with their inverse transformations. All maps are given in a standard basis, in which their degrees and densities are calculated. The method allows us to generate transformations \(f(n)\) of the linear density with degree given by the prescribed linear function \(d(n)\) and with exponential density for \(f(n)^{-1}\). In the case of \(K = F_q\), we can select \(f(n)\) of the exponential order. The scheme of generation of public keys of multivariate cryptography of the form \(g(n) = T_1f(n)T_2\), where \(T_1\) is a monomial linear transformation of \(K^n\), and the degree of \(T_2\) is equal to 1, is proposed. The estimates of complexity show that the time of execution of the encryption rule coincides with the time of computation of the value of a quadratic multivariate map. The decryption procedure based on the knowledge of a generation algorithm is even faster. The security rests on the idea of the insufficiency of adversary’s computational resources to restore the inverse map with exponential density and unbounded degree and on the absence of the known general polynomial algorithms to solve this task.

MSC:

94A60 Cryptography
05C85 Graph algorithms (graph-theoretic aspects)
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI