Breaking Goppa-based McEliece with hints

We consider the McEliece cryptosystem with a binary Goppa code C ⊂ F 2 n specified by an irreducible Goppa polynomial g ( x ) ∈ F 2 m [ X ] and Goppa points ( α 1, …, α n ) ∈ F 2 m n. Since g ( x ) together with the α i 's allow for efficient decoding, these parameters form McEliece secret keys. Such a Goppa code C is an ( n − t m ) -dimensional subspace of F 2 n, and therefore C has co-dimension tm. For typical McEliece instantiations we have t m ≈ n 4. We show that given more than tm elements of the Goppa points allows to recover the Goppa polynomial g ( x ) and the remaining entries in polynomial time. Hence, in case t m ≈ n 4, roughly a fourth of a McEliece secret key is sufficient to recover the full key efficiently. Let us give an illustrative numerical example. For ClassicMcEliece with ( n, t, m ) = ( 3488, 64, 12 ) on input 64 ⋅ 12 + 1 = 769 Goppa points, we recover the remaining 3488 − 769 = 2719 Goppa points in F 2 12 and the degree-64 Goppa polynomial g ( x ) ∈ F 2 12 [ x ] in 60 secs. Our results also extend to the case of erroneous Goppa points, but in this case our algorithms are no longer polynomial time.

Authors

• Elena Kirshanova
• Alexander May

Keywords

No keywords are indexed for this paper.