The Matsumoto-Imai public key scheme was developed to provide very fast signatures. It is based on substitution polynomials over GF(2m). This paper shows in two ways that the Matsumoto-Imai public key scheme is very easy to break. In the faster of the two attacks the time to cryptanalyze the scheme is about proportional to the binary length of the public key. This shows that Matsumoto and Imai greatly overestimated the security of their scheme.
|Original language||English (US)|
|Title of host publication||Advances in Cryptology|
|Subtitle of host publication||Proceedings of EUROCRYPT 1984 - A Workshop on the Theory and Application of Cryptographic Techniques|
|Editors||Ingemar Ingemarsson, Norbert Cot, Thomas Beth|
|Number of pages||8|
|State||Published - 1985|
|Event||Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1984 - Paris, France|
Duration: Apr 9 1984 → Apr 11 1984
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Other||Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1984|
|Period||4/9/84 → 4/11/84|
Bibliographical notePublisher Copyright:
© 1985, Springer-Verlag Berlin Heidelberg.