Paper 2022/525
Breaking GoppaBased 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 $(ntm)$dimensional subspace of $\mathbb{F}_2^n$, and therefore $C$ has codimension $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 $3488769=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 $81921665=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.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. SCN2022
 Keywords
 McEliecePartial Key RecoveryGoppa code structural attack
 Contact author(s)

elenakirshanova @ gmail com
alex may @ rub de  History
 20230109: last of 2 revisions
 20220510: received
 See all versions
 Short URL
 https://ia.cr/2022/525
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/525, author = {Elena Kirshanova and Alexander May}, title = {Breaking GoppaBased 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} }