### 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, \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.

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

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. SCN2022
Keywords
McEliecePartial Key RecoveryGoppa code structural attack
Contact author(s)
elenakirshanova @ gmail com
alex may @ rub de
History
2023-03-09: last of 3 revisions
See all versions
Short URL
https://ia.cr/2022/525 CC BY

BibTeX

@misc{cryptoeprint:2022/525,
author = {Elena Kirshanova and Alexander May},
title = {Breaking Goppa-Based McEliece with Hints},
howpublished = {Cryptology ePrint Archive, Paper 2022/525},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/525}},
url = {https://eprint.iacr.org/2022/525}
} Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.