Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleCryptanalysis of the hidden matrix cryptosystem.
Author(s) Faug`ere Jean-Charles, Antoine Joux, Ludovic Perret, Joana Treger
TypeBook, Chapter in Book, Conference Proceeding
AbstractIn this paper, we present an efficient cryptanalysis of the so-called HM cryptosystem which was published at Asiacrypt’1999, and one perturbed version of HM. Until now, this scheme was exempt from cryptanalysis. We first present a distinguisher which uses a differential property of the public key. This distinguisher permits to break one perturbed version of HM. After that, we describe a practical message-recovery attack against HM using Gröbner bases. The attack can be mounted in few hundreds seconds for recommended parameters. It turns out that algebraic systems arising in HM are easier to solve than random systems of the same size. Note that this fact provides another distinguisher for HM. Interestingly enough, we offer an explanation why algebraic systems arising in HM are easy to solve in practice. Briefly, this is due to the apparition of many new linear and quadratic equations during the Gröbner basis computation. More precisely, we provide an upper bound on the maximum degree reached during the Gröbner basis computation (a.k.a. the degree of regularity) of HM systems. For 𝔽2, which is the initial and usual setting of HM, the degree of regularity is upper-bounded by 3. In general, this degree of regularity is upper-bounded by 4. These bounds allow a polynomial-time solving of the system given by the public equations in any case. All in all, we consider that the HM scheme is broken for all practical parameters.
URL http://link.springer.com/chapter/10.1007%2F978-3-642-14712-8_15
PublisherBerlin: Springer
Translation No
Refereed No