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 $(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 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 $1$ minute. For 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 $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)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
McEliecePartial Key RecoveryGoppa code structural attack
Contact author(s)
elenakirshanova @ gmail com
alex may @ rub de
History
2022-05-10: received
Short URL
https://ia.cr/2022/525
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.