Paper 2022/525

Breaking Goppa-Based McEliece with Hints

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,\dots ,{\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 $$ entries of the Goppa point vector $$ allows to recover the Goppa polynomial $$ and the remaining entries in polynomial time. Hence, in case $$ 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 $$ on input $$ Goppa points, we recover the remaining $$ Goppa points in $$ and the degree-$$ Goppa polynomial $$ in $$ secs. For \textsc{ClassicMcEliece} with $$ on input $$ Goppa points, we recover the remaining $$ Goppa points in $$ and the degree-$$ Goppa polynomial $$ in $$ secs. Our results also extend to the case of erroneous Goppa points, but in this case our algorithms are no longer polynomial time.

Note: A new section (Section 3.5) on "Reconstruction from Goppa Polynomial and t(m − 2) + 1 Points" is added. Minor editoria changes.