# McEliece cryptosystem

Let $$(S, G, P)$$ be the secret key:
$$S$$ : invertible matrix
$$G$$ : generator matrix for some linear code $$C$$
$$P$$ : permutation matrix

And let $$G'= SGP$$ be the public key.

To encrypt $$m$$, we compute $$Enc(m) = mG'+e$$, with $$e$$ an error vector

The thing is, the basic idea about structural attacks, is that we brute-force the family of codes used (most likely, the code used is a binary Goppa code, but there are attempts to use other families, which are not yet broken).
So my question is, do we really need to reveal which family of code was used? wouldn't be more secure if we keep it hidden?

• If you keep it hidden, then how are you going to decrypt? Or are you thinking about violating Kerckhoffs's Principle? – Ruben De Smet Jan 24 at 18:53
• By hidden, I mean hidden from the public. The party that holds the secret key knows the code used – Younes Jan 24 at 19:02
• Even if you consider the used code as a part of the secret key, you would only enlarge the key space by a small factor (namely, the number of possible possible codes $n$). So you would effectively increase the strength of your scheme with $\log_2(n)$ bits. That's pretty small, considering you would need to implement $n$ different schemes. – Ruben De Smet Jan 25 at 11:14
• I think that, if the code $C$ used is $[n,k,t]$, then the key space will be enlarged by all codes coming from all different families of codes, which are $[n,k,t]$. I am not sure if this factor is $log(n)$. – Younes Jan 25 at 13:00
• The $n$ in Ruben De Smet's comment was referring to the number of possible codes, not of the parameters used to describe codes. – Ella Rose Jan 25 at 15:47

Thus, the permuted matrix 'hides' the actual matrix $$G$$. So your extra hiding is unnecessary. The attacker knows the set of permuted generator matrices, but not the actual matrix.
The dimensions are huge, as a comparison, say you know that an RSA asymmetric key of 4096 bits has 2098 1's but nothing else. That is a set of size $$\binom{4096}{2098}\approx 2^{0.999570 \times 4096}=2^{4094.23}$$ which is somewhat smaller than $$2^{4096}$$ but not by a significant multiplicative factor (less tha 2 bits weaker).
You could randomly choose a code, but then the advantage the legitimate decoder has, in terms of efficient decoding when in posession of $$P,G$$ and $$S$$ disappears.
• Let's say the code used $C$ is a Goppa code $[n,k,t]$. There are some attacks that literately brute force all Goppa codes $[n,k,t]$, and using the Support Splitting Algorithm, recover $G$ from $G'$. In these attacks, we use the fact that the code used is a Goppa code. So I think if the family was hidden, the attacker has to brute force codes that are $[n,k,t]$, even those that are not Goppa codes. – Younes Jan 25 at 13:12