Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt'98
In [7] Matsumoto and Imai developed a new public key scheme, called C-*, for enciphering or signing. (This scheme is completely different from and should not be mistaken with another scheme of Matsumoto and Imai developed in 1983 in [11] and broken in 1984 in [12]). No attacks have been published as yet for this scheme. However, in this paper, we will see that-for almost all keys-almost every cleartext can be found from its ciphertext after only approximately m(2) n(4) log n computations, where m is the degree of the chosen field K and mn is the number of bits of text. Moreover, for absolutely all keys that give a practical size for the messages, it will be possible to find almost all cleartexts from the corresponding ciphertexts after a feasible computation. Thus the algorithm of [7] is insecure.
cryptanalysis public key signatures public key encryption multivariate polynomials candidate trapdoor permutation exponentiation over a finite field