Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt'98

In 1 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 7 and broken in 1984 in 8). 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 ² n ⁴ 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 1 is insecure.