Paper 2022/525
Decoding McEliece with a Hint  Secret Goppa Key Parts Reveal Everything
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.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. SCN2022
 Keywords
 McEliece Partial Key Recovery Goppa code structural attack
 Contact author(s)

elenakirshanova @ gmail com
alex may @ rub de  History
 20220630: revised
 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 = {Decoding McEliece with a Hint  Secret Goppa Key Parts Reveal Everything}, howpublished = {Cryptology ePrint Archive, Paper 2022/525}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/525}}, url = {https://eprint.iacr.org/2022/525} }