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.
ePrint: https://eprint.iacr.org/2022/525
See all topics related to this paper.
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.
For more information, see the rules for Resource Topics .