Niederreiter cryptosystem is usually described by a parity check matrix $H$ over $\mathbb{F}_{2^n}$.

The minimum distance $d$ is given by

$d := min\lbrace k \text{ such that there are $k$ linearly dependant columns in $H$}\rbrace$

Encryption in this case is done by encoding messages $m$ of weight less than $d/2$.

Now keeping Niederreiter systems in mind, my question is, since $m$ is over $\mathbb{F}_2$, it makes sense to consider linearly dependence over $\mathbb{F}_2$ rather than $\mathbb{F}_{2^n}$. In other words, is it okay to consider code as a code over $F_{2}$ with alphabet extension or do we have to consider it as codes over $\mathbb{F}_{2^n}$.


According to Sendrier, Niederreiter systems are only known to be secure when used with Goppa codes. All other families of codes which have been tried have been broken. You are suggesting a code superficially related to the Goppa code but probably having very different properties. Hence it is likely to be insecure (or perhaps useless for other reasons, such as low rate or low distance).

More generally, cryptosystems are surprisingly brittle. I would leave them to the experts.

| cite | improve this answer | |
  • $\begingroup$ In recent years there have been many attempts with quasi cyclic codes particularly LDPC and MDPC(although as you pointed out most of them turned out to be vulnerable) so there is nothing principally wrong or demotivating for someone to look into them. Anyway, my question is not about security but rather about understanding algebraic structure. Would the decoding algorithm work if I use codes with either of the above structures namely codes over $\mathbb{F}_{2^l}$ or over $\mathbb{F}_2$ extension symbols. $\endgroup$ – Root Jul 20 '19 at 2:46
  • $\begingroup$ Multiplication in the larger field is very different from its counterpart in the base field, so the two codes will be rather different. $\endgroup$ – Yuval Filmus Jul 20 '19 at 4:25
  • $\begingroup$ Yes. Sure. That's why I am asking which one of them is used? And can we use any of them? Clearly linearly independent in higher fields would mean the same in base field. But would decoding work with codes over base field with extension of alphabets (as msgs are still over base field in Niederreiter systems)? $\endgroup$ – Root Jul 20 '19 at 5:02
  • $\begingroup$ Linear independence doesn’t mean the same thing. There’s no reason to assume your new code has any reasonable properties, though your construction is similar to code concatenation. $\endgroup$ – Yuval Filmus Jul 20 '19 at 5:05

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.