# 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