What is the impact of the distinguisher for the high-rate Goppa codes (as published in "A Distinguisher for High Rate McEliece Cryptosystems") on the CFS signature scheme and the McEliece/Niederreiter cryptosystems?

It seems that the distinguisher strongly affects the CFS scheme, forcing its parameters to increase (if one hopes for a provably secure signature) to such an extent that the CFS scheme becomes totally impractical.

On the other hand, the distinguisher does not seem to affect the security of the McEliece cryptosystem at all. Why is that?

  • $\begingroup$ I would guess that McEliece PKE does not use high-rate Goppa codes. $\;$ $\endgroup$ – user991 Nov 23 '13 at 7:21

Why the CFS signature is affected

Let us review the structure of the CFS signature, which is strongly related to the Niederreiter PKE scheme.

In the Niederreiter PKE scheme, a public key is $H \in \mathbb{F}^{n \times k}$, which is a scrambled parity-check matrix of the Goppa codes. A plaintext is a decodable error; for example, we set $S = \{\vec{e} \in \mathbb{F}^n \mid H_w(\vec{e}) \leq t \}$ for some $t$ as a plaintext space. A ciphertext is a decodable syndrome of $\vec{e}$, that is, $\vec{c} = F_H(\vec{e}) = H \cdot \vec{e} \in \mathbb{F}^{k}$.

This mapping is not surjective. In other words, there are several undecodable syndromes. The ratio of undecodable syndromes is in proportion to the ratio of the code. The higher a ratio of code is, the lower a ratio of undecodable syndromes. Therefore, the practical CFS signature requires the code to be high-rate.

The security proof of the CFS signature scheme goes as follows:

  1. The original security game.
  2. Exploit the random oracle in order to remove inversion. In each query, choose $\vec{e}$ and define the hash value $RO(i,m) \gets F_H(\vec{e})$.
  3. Replace the public key from a scrambled parity-check matrix $H$ to a random matrix $H_{\mathrm{random}}$.
  4. Now, we reduce the game to the syndrome decoding problem.

In several parameter settings, the high-rate code distinguisher falsify the argument at Step 3.

Why the McEliece/Niederreiter encryption is less affected

A one-line answer is that the above PKE schemes can be constructed from low-rate codes.

In the PKE schemes, a decryptor has no need to be able to decrypt any ciphertexts. Hence, we can employ relatively low-rate codes, on which the high-rate distinguisher you referred fails.


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.