Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
I would guess that McEliece PKE does not use high-rate Goppa codes. $\;$ – Ricky Demer 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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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