1
$\begingroup$

There is something intriguing me about this cryptosystem. That is :

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ If you keep it hidden, then how are you going to decrypt? Or are you thinking about violating Kerckhoffs's Principle? $\endgroup$
    – Ruben De Smet
    Jan 24, 2019 at 18:53
  • $\begingroup$ By hidden, I mean hidden from the public. The party that holds the secret key knows the code used $\endgroup$
    – Younes
    Jan 24, 2019 at 19:02
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ruben De Smet
    Jan 25, 2019 at 11:14
  • $\begingroup$ 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)$. $\endgroup$
    – Younes
    Jan 25, 2019 at 13:00
  • $\begingroup$ The $n$ in Ruben De Smet's comment was referring to the number of possible codes, not of the parameters used to describe codes. $\endgroup$
    – Ella Rose
    Jan 25, 2019 at 15:47

1 Answer 1

Reset to default
1
$\begingroup$

But the matrix is permuted, which is the operation enabling the trapdoor to operate.

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).

Knowing the code (say Goppa) and its parameters is important since these determine the strength implied by the length, dimension, and minimum distance of the code.

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Younes
    Jan 25, 2019 at 13:12
  • $\begingroup$ You would also need to ensure that your randomly chosen code is not somehow weak and does not somehow enable attacks. Judging by how many broken McEliece variants there are, I'd say the prospects there do not look good. This could easily make the system weaker for a relatively paltry gain in security when it actually succeeds. $\endgroup$
    – Ella Rose
    Jan 25, 2019 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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