Abstract
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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
McEliece, R.: A public-key cryptosystem based on algebraic coding theory. DSN Progress Report, Jet Prop. Lab., California Inst. Tech. 42-44, 114–116 (1978)
van Tilborg, H.: Encyclopedia of Cryptography and Security. Springer, Heidelberg (2005)
Minder, L., Shokrollahi, A.: Cryptanalysis of the Sidelnikov cryptosystem. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 347–360. Springer, Heidelberg (2007)
Gibson, K.: The security of the Gabidulin public-key cryptosystem. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 212–223. Springer, Heidelberg (1996)
Sidelnikov, V., Shestakov, S.: On insecurity of cryptosystems based on generalized Reed-Solomon codes. Discrete Math. Appl. 2, 439–444 (1992)
Berger, T., Loidreau, P.: How to mask the structure of codes for a cryptographic use. Designs, Codes and Cryptography 35, 63–79 (2005)
Wieschebrink, C.: An attack on a modified Niederreiter encryption scheme. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 14–26. Springer, Heidelberg (2006)
Berlekamp, E., Welch, L.: Error correction of algebraic block codes, US Patent No. 4,633,470 (1986)
Guruswami, V., Sudan, M.: Improved decoding of Reed-Solomon and algebraic-geometric codes. In: Proceedings of 39th Annual Symposium on Foundations of Computer Science, pp. 28–37 (1998)
MacWilliams, F., Sloane, N.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam (1997)
Niederreiter, N.: Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory 15, 159–166 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wieschebrink, C. (2010). Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes. In: Sendrier, N. (eds) Post-Quantum Cryptography. PQCrypto 2010. Lecture Notes in Computer Science, vol 6061. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12929-2_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-12929-2_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12928-5
Online ISBN: 978-3-642-12929-2
eBook Packages: Computer ScienceComputer Science (R0)