Algebraic Cryptanalysis of McEliece Variants with Compact Keys -- Toward a Complexity Analysis

A new algebraic approach to investigate the security of the McEliece cryptosystem has been proposed by Faugere-Otmani-Perret-Tillich in Eurocrypt 2010. This paper is an extension of this work. The McEliece’s scheme relies on the use of error-correcting codes. It has been proved that the private key of the cryptosystem satisfies a system of bi-homogeneous polynomial equations. This property is due to the particular class of codes considered which are alternant codes. These highly structured algebraic equations allowed to mount an efficient key-recovery attack against two recent variants of the McEliece cryptosystems that aim at reducing public key sizes by using quasi-cyclic or quasi-dyadic structures. Thanks to a very recent development due to Faugere-Safey el Din-Spaenlehauer on the solving of bihomogeneous bilinear systems, we can estimate the complexity of the FOPT algebraic attack. This is a first step toward providing a concrete criterion for evaluating the security of future compact McEliece variants.