Paper 2022/525

Breaking Goppa-Based McEliece with Hints

Abstract

We consider the McEliece cryptosystem with a binary Goppa code $$ specified by an irreducible Goppa polynomial $$ and Goppa points $$. Since $$ together with the Goppa points allow for efficient decoding, these parameters form McEliece secret keys. Such a Goppa code $$ is an $$-dimensional subspace of $$, and therefore $$ has co-dimension $$. For typical McEliece instantiations we have $$. 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.