Details:
Title  Cryptanalysis of the hidden matrix cryptosystem.  Author(s)  Faug`ere JeanCharles, Antoine Joux, Ludovic Perret, Joana Treger  Type  Book, Chapter in Book, Conference Proceeding  Abstract  In this paper, we present an efficient cryptanalysis of the socalled 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 messagerecovery 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 upperbounded by 3. In general, this degree of regularity is upperbounded by 4. These bounds allow a polynomialtime 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.  ISBN  9783642147111/pbk 
URL 
http://link.springer.com/chapter/10.1007%2F9783642147128_15 
Language  English  Pages  241254  Publisher  Berlin: Springer  Year  2010  Edition  0  Translation 
No  Refereed 
No 
