The Niederreiter cryptosystem is a public key cryptosystem using Goppa code. Unfortunately it it is insecure unless it is a binary code. So I thought I could insert random linear codes into randomly selected columns of the public key in the parity check matrix $H'=SHP$ and $H'\,^t$ to make it random. Here $H'$ is byte error correcting code.

This proposal based on q-array syndrome decoding problem. It is another approach to randomization for a Niederreiter public key.

Unless an attacker knows in which column the Goppa code is located, the attacker will (need to) decode by information set decoding.

Is this scheme insecure?

There is no firm belief, but it is based on the assumption that it is difficult to distinguish between a column of randomized Goppa codes and a column of random linear codes. I can not yet think of a way to prove that.

  • $\begingroup$ Why do you say it is "meaningless"? $\endgroup$
    – kodlu
    Jul 30, 2019 at 23:34
  • $\begingroup$ I correct it.I wrote mistakes. $\endgroup$ Jul 30, 2019 at 23:49
  • $\begingroup$ I've tried rewording & formatting your question, please check if it is still correct. The description of your system is rather sparse, and asking for analysis of a scheme is off topic here anyway. Please make your question as specific as possible and show what you've tried yourself to proof / disprove security. $\endgroup$
    – Maarten Bodewes
    Jul 31, 2019 at 8:57


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.