On the Restoration of Historical Matsumoto-Imai Cryptosystem and Other Schemes in Terms of Noncommutative Cryptography

Matsumoto-Imai Cryptosystem was one of the first public keys developed in terms of Multivariate Cryptography. The famous effective cryptanalysis of this system and various attempts to modify the broken public key make a valuable impact on Algebraic Cryptography. The paper presents the idea of combining multivariate encryption with the secure protocol of Noncommutative Cryptography. The new cryptosystem is constructed in terms of the intersection of Noncommutative and Multivariate Cryptographies. The encryption process is a combination of Eulerian transformation of the vector space and the quadratic multivariate map of the Imai-Matsumoto public key. The complexity of the computation of ciphertext is O(n3). The theoretical cost of the protocol is also O(n3). It allows Alice to deliver the standard form of the used quadratic map in time O(n3). So new cryptosystem has the same computational complexity as the original Matsumoto-Imai public key. The protocol is implemented with the platform of semigroup of Eulerian transformations of the variety (F*q)n, q = 2s. Its security rests on the postquantum intractability of the word decomposition problem in this semigroup. The cryptosystem is included in the class of protocol-based systems defined over the general commutative ring K with nontrivial multiplicative group K*. Explicit constructions of such cryptosystems are given for each K.