Abstract
The classical McEliece cryptosystem is built upon the class of Goppa codes, which remains secure to this date in contrast to many other families of codes but leads to very large public keys. Previous proposals to obtain short McEliece keys have primarily centered around replacing that class by other families of codes, most of which were shown to contain weaknesses, and at the cost of reducing in half the capability of error correction. In this paper we describe a simple way to reduce significantly the key size in McEliece and related cryptosystems using a subclass of Goppa codes, while also improving the efficiency of cryptographic operations to \(\tilde{O}(n)\) time, and keeping the capability of correcting the full designed number of errors in the binary case.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Baldi, M., Chiaraluce, F.: Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC code. In: IEEE International Symposium on Information Theory – ISIT 2007, Nice, France, pp. 2591–2595. IEEE, Los Alamitos (2007)
Baldi, M., Chiaraluce, F., Bodrato, M.: A new analysis of the mcEliece cryptosystem based on QC-LDPC codes. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds.) SCN 2008. LNCS, vol. 5229, pp. 246–262. Springer, Heidelberg (2008)
Berger, T.P., Cayrel, P.-L., Gaborit, P., Otmani, A.: Reducing key length of the McEliece cryptosystem. In: Preneel, B. (ed.) AFRICACRYPT 2009. LNCS, vol. 5580, pp. 77–97. Springer, Heidelberg (2009), http://www.unilim.fr/pages_perso/philippe.gaborit/reducing.pdf
Berlekamp, E., McEliece, R., van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory 24(3), 384–386 (1978)
Bernstein, D.J.: List decoding for binary Goppa codes (2008) (preprint), http://cr.yp.to/papers.html#goppalist
Bernstein, D.J., Buchmann, J., Dahmen, E.: Post-Quantum Cryptography. Springer, Heidelberg (2008)
Bernstein, D.J., Lange, T., Peters, C.: Attacking and defending the mcEliece cryptosystem. In: Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol. 5299, pp. 31–46. Springer, Heidelberg (2008), http://www.springerlink.com/content/68v69185x478p53g
Gaborit, P.: Shorter keys for code based cryptography. In: International Workshop on Coding and Cryptography – WCC 2005, Bergen, Norway, pp. 81–91. ACM Press, New York (2005)
Gaborit, P., Girault, M.: Lightweight code-based authentication and signature. In: IEEE International Symposium on Information Theory – ISIT 2007, Nice, France, pp. 191–195. IEEE, Los Alamitos (2007)
Gibson, J.K.: Severely denting the Gabidulin version of the McEliece public key cryptosystem. Designs, Codes and Cryptography 6(1), 37–45 (1995)
Gibson, J.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)
Gulamhusein, M.N.: Simple matrix-theory proof of the discrete dyadic convolution theorem. Electronics Letters 9(10), 238–239 (1973)
IEEE P1363 Working Group. IEEE 1363-1: Standard Specifications for Public-Key Cryptographic Techniques Based on Hard Problems over Lattices, Draft (2009), http://grouper.ieee.org/groups/1363/lattPK/index.html
Loidreau, P., Sendrier, N.: Some weak keys in McEliece public-key cryptosystem. In: IEEE International Symposium on Information Theory – ISIT 1998, Boston, USA, p. 382. IEEE, Los Alamitos (1998)
MacWilliams, F.J., Sloane, N.J.A.: The theory of error-correcting codes. North-Holland Mathematical Library, vol. 16 (1977)
McEliece, R.: A public-key cryptosystem based on algebraic coding theory. The Deep Space Network Progress Report, DSN PR 42–44 (1978), http://ipnpr.jpl.nasa.gov/progressreport2/42-44/44N.PDF
Micciancio, D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Computational Complexity 16(4), 365–411 (2007)
Monico, C., Rosenthal, J., Shokrollahi, A.: Using low density parity check codes in the McEliece cryptosystem. In: IEEE International Symposium on Information Theory – ISIT 2000, Sorrento, Italy, p. 215. IEEE, Los Alamitos (2000)
Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory 15(2), 159–166 (1986)
European Network of Excellence in Cryptology (ECRYPT). ECRYPT yearly report on algorithms and keysizes (2007-2008). D.SPA.28 Rev. 1.1, IST-2002-507932 ECRYPT, 07/2008 (2008), http://www.ecrypt.eu.org/ecrypt1/documents/D.SPA.28-1.1.pdf
National Institute of Standards and Technology (NIST). Recommendation for key management – part 1: General (2007), http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf
Otmani, A., Tillich, J.-P., Dallot, L.: Cryptanalysis of two McEliece cryptosystems based on quasi-cyclic codes (2008) (preprint), http://arxiv.org/abs/0804.0409v2
Patterson, N.J.: The algebraic decoding of Goppa codes. IEEE Transactions on Information Theory 21(2), 203–207 (1975)
Sarwate, D.V.: On the complexity of decoding Goppa codes. IEEE Transactions on Information Theory 23(4), 515–516 (1977)
Schechter, S.: On the inversion of certain matrices. Mathematical Tables and Other Aids to Computation 13(66), 73–77 (1959), http://www.jstor.org/stable/2001955
Sendrier, N.: Finding the permutation between equivalent linear codes: the support splitting algorithm. IEEE Transactions on Information Theory 46(4), 1193–1203 (2000)
Sidelnikov, V., Shestakov, S.: On cryptosystems based on generalized Reed-Solomon codes. Discrete Mathematics 4(3), 57–63 (1992)
Tzeng, K.K., Zimmermann, K.: On extending Goppa codes to cyclic codes. IEEE Transactions on Information Theory 21, 721–726 (1975)
Wieschebrink, C.: Two NP-complete problems in coding theory with an application in code based cryptography. In: IEEE International Symposium on Information Theory – ISIT 2006, Seattle, USA, pp. 1733–1737. IEEE, Los Alamitos (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Misoczki, R., Barreto, P.S.L.M. (2009). Compact McEliece Keys from Goppa Codes. In: Jacobson, M.J., Rijmen, V., Safavi-Naini, R. (eds) Selected Areas in Cryptography. SAC 2009. Lecture Notes in Computer Science, vol 5867. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-05445-7_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-05445-7_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-05443-3
Online ISBN: 978-3-642-05445-7
eBook Packages: Computer ScienceComputer Science (R0)