Suppose a challenger creates a McEliece encryption system where there is a public key consisting of a matrix $G$ representing some linear code, and a number $t$ for the number of errors.

Then the adversary takes two messages $m_0$ and $m_1$ and uses the public key matrix $G$ to find $c_0=Gm_0$ and $c_1=Gm_1$. Then the adversary sends $m_0$ and $m_1$ to the challenger.

Then the challenger picks $b$ at random and creates $c=Gm_b+e$, and $e$ has at most $t$ errors. Then they send $c$ to the adversary. The adversary calculates: $$e_0=c-c_0=Gm_b+e-Gm_0=G(m_b-m_0)+e$$ $$e_1=c-c_1=Gm_b+e-Gm_1=G(m_b-m_1)+e$$ Since $m_b$ is one of the two messages, then either $e_0=e$ or $e_1=e$. The adversary knows when this happens because $e$ has $t$ or fewer non-zero terms. Further, the other $e_i$ will consist of a non-zero codeword plus the error. Since the minimum distance of the code is greater than or equal to $2t+1$, then this codeword will have at least $2t+1$ non-zero terms; when $e$ is subtracted from this, there will be at least $t+1$ non-zero terms, so the adversary is sure that this was not the message. Hence, the adversary has a 100% chance of correctly guessing $b$.

Does this attack work? Is there some other aspect to the McEliece system that I don't know about that stops this attack?

  • $\begingroup$ This indeed looks like a valid attack that has already published been 2008 (PDF) with a counter measure to make McEliece IND-CPA: randomly pad the message and ignore the defined amount of trailing bits. $\endgroup$ – SEJPM Mar 4 '16 at 16:12
  • $\begingroup$ Thanks, that's exactly what I was looking for! I'll accept this as an answer if you post it as such. $\endgroup$ – Sam Jaques Mar 5 '16 at 17:10

Does this attack work?

Yes, it works.
However, "textbook" McEliece was never claimed to be IND-CPA.
In fact, it was already published in 2008 by Nojima et. al. in "Semantic Security for the McEliece Cryptosystem without Random Oracles" (PDF).

They also propose a mitigation in the paper, which is to simply front-pad the message with sufficiently many random bits and later simply ignore those bits at decryption.

  • $\begingroup$ Funfact: I found the linked paper in the german Wikipedia entry for McEliece and it does not appear in the english version. $\endgroup$ – SEJPM Mar 5 '16 at 19:34
  • $\begingroup$ I'm certainly no expert on McEliese, but why would one use a random prefix when you could have a strong random permutation instead? That's like reinventing the PKCS#1v1.5 RSA padding. $\endgroup$ – CodesInChaos Mar 17 '16 at 16:46
  • $\begingroup$ @CodesInChaos a) you wouldn't use McEliece like this anyways (it's not IND-CCA secure) b) this is the simplest way to make McEliece IND-CPA (not necessarily the best) C) merely applying a PRP (or something like that) wouldn't make McEliece IND-CPA because it's lacking randomness and the PRP won't change that. $\endgroup$ – SEJPM Mar 17 '16 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.