Dimension of the linearization equations of the Matsumoto-Imai cryptosystems

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

*Corresponding author for this work

Research output: Chapter in Book or Report/Conference proceedingConference Proceedingpeer-review

6 Citations (Scopus)

Abstract

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
Pages242-251
Number of pages10
ISBN (Print)3540354816, 9783540354819
DOIs
Publication statusPublished - 2006
Externally publishedYes
EventInternational Workshop on Coding and Cryptography, WCC 2005 - Bergen, Norway
Duration: 14 Mar 200518 Mar 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

Conference

ConferenceInternational Workshop on Coding and Cryptography, WCC 2005
Country/TerritoryNorway
CityBergen
Period14/03/0518/03/05

Fingerprint

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

Cite this