TY - GEN

T1 - A distinguisher for high rate McEliece cryptosystems

AU - Faugère, Jean Charles

AU - Gauthier-Umaña, Valérie

AU - Otmani, Ayoub

AU - Perret, Ludovic

AU - Tillich, Jean Pierre

N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.

PY - 2011

Y1 - 2011

N2 - The Goppa Code Distinguishing (GCD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. Up to now, it is widely believed that the GCD problem is a hard decisional problem. We present the first technique allowing to distinguish alternant and Goppa codes over any field. Our technique can solve the GCD problem in polynomial-time provided that the codes have rates sufficiently large. The key ingredient is an algebraic characterization of the key-recovery problem. The idea is to consider the dimension of the solution space of a linearized system deduced from a particular polynomial system describing a key-recovery. It turns out that experimentally this dimension depends on the type of code. Explicit formulas derived from extensive experimentations for the value of the dimension are provided for generic random, alternant, and Goppa code over any alphabet. Finally, we give explanations of these formulas in the case of random codes, alternant codes over any field and binary Goppa codes.

AB - The Goppa Code Distinguishing (GCD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. Up to now, it is widely believed that the GCD problem is a hard decisional problem. We present the first technique allowing to distinguish alternant and Goppa codes over any field. Our technique can solve the GCD problem in polynomial-time provided that the codes have rates sufficiently large. The key ingredient is an algebraic characterization of the key-recovery problem. The idea is to consider the dimension of the solution space of a linearized system deduced from a particular polynomial system describing a key-recovery. It turns out that experimentally this dimension depends on the type of code. Explicit formulas derived from extensive experimentations for the value of the dimension are provided for generic random, alternant, and Goppa code over any alphabet. Finally, we give explanations of these formulas in the case of random codes, alternant codes over any field and binary Goppa codes.

UR - http://www.scopus.com/inward/record.url?scp=83655202691&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=83655202691&partnerID=8YFLogxK

U2 - 10.1109/ITW.2011.6089437

DO - 10.1109/ITW.2011.6089437

M3 - Conference contribution

AN - SCOPUS:83655202691

SN - 9781457704376

T3 - 2011 IEEE Information Theory Workshop, ITW 2011

SP - 282

EP - 286

BT - 2011 IEEE Information Theory Workshop, ITW 2011

T2 - 2011 IEEE Information Theory Workshop, ITW 2011

Y2 - 16 October 2011 through 20 October 2011

ER -