Paper 2022/525
Decoding McEliece with a Hint  Secret Goppa Key Parts Reveal Everything
Elena Kirshanova and Alexander May
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 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 $1$ minute. For 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 $5$ minutes. 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
 Preprint.
 Keywords
 McEliecePartial Key RecoveryGoppa code structural attack
 Contact author(s)

elenakirshanova @ gmail com
alex may @ rub de  History
 20220510: received
 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} }