caa a22 4500 47580743X CHVBK 20180406123751.0 cr unu---uuuuu 170329e20000601xx s 000 0 eng 10.1023/A:1008341625464 doi (NATIONALLICENCE)springer-10.1023/A:1008341625464 Patarin Jacques Bull SC&T - 68, route de Versailles -, 78431, Louveciennes Cedex -, France aut Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt'98 [Elektronische Daten] [Jacques Patarin] 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 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 1 is insecure. Kluwer Academic Publishers, 2000 Public key signatures nationallicence public key encryption nationallicence multivariate polynomials nationallicence cryptanalysis nationallicence candidate trapdoor permutation nationallicence exponentiation over a finite field nationallicence Designs, Codes and Cryptography Kluwer Academic Publishers 20/2(2000-06-01), 175-209 0925-1022 20:2<175 2000 20 10623 https://doi.org/10.1023/A:1008341625464 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1023/A:1008341625464 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Patarin Jacques Bull SC&T - 68, route de Versailles -, 78431, Louveciennes Cedex -, France aut NATIONALLICENCE 773 0- Designs, Codes and Cryptography Kluwer Academic Publishers 20/2(2000-06-01), 175-209 0925-1022 20:2<175 2000 20 10623 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer