# [Resource Topic] 2022/525: Decoding McEliece with a Hint - Secret Goppa Key Parts Reveal Everything

Welcome to the resource topic for 2022/525

Title:
Decoding McEliece with a Hint - Secret Goppa Key Parts Reveal Everything

Authors: Elena Kirshanova and Alexander May

Abstract:

We consider the McEliece cryptosystem with a binary Goppa code C \subset \mathbb{F}_2^n specified by an irreducible Goppa polynomial g(x) \in \mathbb{F}_{2^m}[X] and Goppa points (\alpha_1, \ldots, \alpha_n) \in \mathbb{F}_{2^m}^n. Since g(x) together with the Goppa points allow for efficient decoding, these parameters form McEliece secret keys. Such a Goppa code C is an (n-tm)-dimensional subspace of \mathbb{F}_2^n, and therefore C has co-dimension tm. For typical McEliece instantiations we have tm \approx \frac n 4. We show that given more than tm entries of the Goppa point vector (\alpha_1, \ldots, \alpha_n) allows to recover the Goppa polynomial g(x) and the remaining entries in polynomial time. Hence, in case tm \approx \frac n 4 roughly a fourth of a McEliece secret key is sufficient to recover the full key efficiently. Let us give some illustrative numerical examples. For \textsc{ClassicMcEliece} with (n,t,m)=(3488,64,12) on input 64\cdot 12+1=769 Goppa points, we recover the remaining 3488-769=2719 Goppa points in \mathbb{F}_{2^{12}} and the degree-64 Goppa polynomial g(x) \in \mathbb{F}_{2^{12}}[x] in 60 secs. For \textsc{ClassicMcEliece} with (n,t,m)=(8192,128,13) on input 128\cdot 13+1=1665 Goppa points, we recover the remaining 8192-1665=6529 Goppa points in \mathbb{F}_{2^{13}} and the degree-128 Goppa polynomial g(x) \in \mathbb{F}_{2^{13}}[x] in 288 secs. Our results also extend to the case of erroneous Goppa points, but in this case our algorithms are no longer polynomial time.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.