Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes

Free registration required

Executive Summary

In this paper a new structural attack on the McEliece/Niederreiter public key cryptosystem based on subcodes of generalized Reed-Solomon codes proposed by Berger and Loidreau is described. It allows the reconstruction of the private key for almost all practical parameter choices in polynomial time with high probability. Public key cryptosystems based on the difficulty of the (syndrome) decoding problem for linear codes have been discussed since the work by McEliece in 1977. Although the McEliece cryptosystem remains unbroken till today (for suitable parameter choices) in practice it could not stand up to encryption schemes such as RSA or schemes based on the discrete logarithm problem. This is partly due to the large (public) key sizes needed in the McEliece scheme.

  • Format: PDF
  • Size: 191.8 KB