1
$\begingroup$

In the McEliece cryptosystem, is choice of the code known to the attacker? And if a structural attack succeeded and the attacker found the generator matrix of the code, how did the attacker decode the encrypted message?

$\endgroup$
5
  • $\begingroup$ Did you read my answer? Comments? $\endgroup$ – kodlu Aug 1 '20 at 1:58
  • $\begingroup$ Thanks for your answer. Please excuse me for my English. You said that "the code is known (via G) ti everyone", but if G is known there is no reason to mask the code, do you agree? $\endgroup$ – Paul Aug 19 '20 at 9:35
  • $\begingroup$ Hi Paul, what happens is that by the masking via permutation and matrix multiplication an equivalent code is produced, with similar properties to the original code. So the equivalent decoding problem looks like it is for a random code, and since decoding a random code is difficult, the strength resides in the multiplication and permutation, they are trapdoor information available only to the authorized decoder. $\endgroup$ – kodlu Aug 19 '20 at 9:38
  • $\begingroup$ Ok, i agree. the attacker know exactly the matrix G, but He don't know S and P, is this true? $\endgroup$ – Paul Aug 19 '20 at 10:41
  • $\begingroup$ $G$ is NOT publicly known. $\endgroup$ – cisnjxqu Apr 8 at 16:14
0
$\begingroup$

The "seed" code is known (via $G$) to everyone including the attacker, but the actual code used is unknown. The seed code coordinates are permuted on the right ($P$) after an invertible transformation $S$ applied on the left, forming a trapdoor. $S,P$ are secret. If the permuted generator matrix is $\hat{G}$ we have $$ \hat{G}=SGP. $$

If the attacker finds the (unpermuted) generator matrix, then they can just decode as explained in the next paragraph.

If the received ciphertext is $c=c'\oplus e,$ where $e$ is the noise vector added for security, and $c'=m\hat{G},$ the legitimate recipient can do $$ \hat{c}=cP^{-1}, $$ and can decode $\hat{c}$ to $\hat{m}$ using the standard decoding algorithm for the code. Finally she can compute $$ m=\hat{m}S^{-1}. $$ You can check in a routine way this works.

Edit: To clarify where the security comes from, the masking via permutation and matrix multiplication produces an equivalent “pseudorandom” code with similar properties to the original code.

So the equivalent decoding problem looks like a decoding problem for a random code, and since decoding a random code is difficult, the strength resides in the multiplication and permutation, they are trapdoor information available only to the authorized decoder.

Note that the noise added must not be beyond the correction capability of the code. If it was, the legitimate receiver might decode to the wrong codeword even with the trapdoor information or fail to decode to the correct codeword.

$\endgroup$
1
  • $\begingroup$ $G$ is NOT known to the adversary. However, $\hat{G}$ is. $\endgroup$ – cisnjxqu Apr 8 at 16:13

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.