Dimension of the linearization equations of the Matsumoto-Imai cryptosystems

Adama Diene, Jintai Ding, Jason E. Gower, Timothy J. Hodges, Zhijun Yin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)


The Matsumoto-Imai (MI) cryptosystem was the first multivariate public key cryptosystem proposed for practical use. Though MI is now considered insecure due to Patarin's linearization attack, the core idea of MI has been used to construct many variants such as Sflash, which has recently been accepted for use in the New European Schemes for Signatures, Integrity, and Encryption project. Linearization attacks take advantage of the algebraic structure of MI to produce a set of equations that can be used to recover the plaintext from a given ciphertext. In our paper, we present a solution to the problem of finding the dimension of the space of linearization equations, a measure of how much work the attack will require.

Original languageEnglish
Title of host publicationCoding and Cryptography - International Workshop, WCC 2005, Revised Selected Papers
PublisherSpringer Verlag
Number of pages10
ISBN (Print)3540354816, 9783540354819
Publication statusPublished - 2006
Externally publishedYes
EventInternational Workshop on Coding and Cryptography, WCC 2005 - Bergen, Norway
Duration: Mar 14 2005Mar 18 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3969 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


OtherInternational Workshop on Coding and Cryptography, WCC 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Dimension of the linearization equations of the Matsumoto-Imai cryptosystems'. Together they form a unique fingerprint.

Cite this