# How is McEliece chosen plaintext secure?

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?

• 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. – SEJPM Mar 4 '16 at 16:12
• Thanks, that's exactly what I was looking for! I'll accept this as an answer if you post it as such. – 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.

• Funfact: I found the linked paper in the german Wikipedia entry for McEliece and it does not appear in the english version. – SEJPM Mar 5 '16 at 19:34
• 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. – CodesInChaos Mar 17 '16 at 16:46
• @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. – SEJPM Mar 17 '16 at 16:58