In this chapter, we consider the theory and the practice of code-based cryptographic systems. By this term, we mean the cryptosystems in which the algorithmic primitive (the underlying one-way function) uses an error correcting code C. This primitive may consist in adding an error to a word of C or in computing a syndrome relatively to a parity check matrix of C.
The first of those systems is a public key encryption scheme and it was proposed by Robert J. McEliece in 1978 [48]. The private key is a random bi¬nary irreducible Goppa code and the public key is a random generator matrix of a randomly permuted version of that code. The ciphertext is a codeword to which some errors have been added, and only the owner of the private key (the Goppa code) can remove those errors. Three decades later, some parameter adjustment have been required, but no attack is known to represent a serious threat on the system, even on a quantum computer.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
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
Alabbadi, M. and Wicker, S.: A digital signature scheme based on linear error-correcting block codes. In ASIACRYPT ’94, volume LNCS 917, pages 238–248 (Springer 1995).
Assmus, Jr, E.F. and Key, J.D.: Affine and projective planes. Discrete Mathematics, 83:161–187 (1990).
Augot, D., Finiasz, M., and N.Sendrier: A family of fast syndrome based cryptographic hash functions. In Proc. of Mycrypt 2005, volume 3715 of LNCS, pages 64–83 (2005).
Barg, A.: Complexity issues in coding theory. In V.S. Pless and W.C. Huffman, editors, Handbook of Coding theory, volume I, chapter 7, pages 649–754. North-Holland (1998).
Berger, T. and Loidreau, P.: Security of the Niederreiter form of the GPT public-key cryptosystem. In IEEE International Symposium on Information Theory, Lausanne, Suisse. IEEE (July 2002).
Berlekamp, E., McEliece, R., and van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory, 24(3):384–386 (1978).
Berlekamp, E.: Algebraic coding theory. McGraw-Hill, New York (1968).
Berson, T.: Failure of the McEliece public-key cryptosystem under message-resend and related-message attack. In Proceedings of CRYPTO, volume 1294 of Lecture Notes in Computer Science, pages 213–220. Springer Verlag (1997).
Blaum, M. and McEliece, R.J.: Coding protection for magnetic tapes: A generalization of the Patel - Hong code. IEEE Transactions on Information Theory, 31(5):690– (1985).
Camion, P. and Patarin, J.: The knapsack hash function proposed at Crypto'89 can be broken. In D.W. Davies, editor, Advances in Cryptology - EURO-CRYPT'91, number 547 in LNCS, pages 39–53. Springer-Verlag (1991).
Canteaut, A. and Chabaud, F.: Improvements of the attacks on cryptosystems based on error-correcting codes. Rapport interne du Departement Mathema-tiques et Informatique, LIENS-95-21 (1995).
Canteaut, A. and Chabaud, F.: A new algorithm for finding minimum-weight words in a linear code: Application to McEliece's cryptosystem and to narrow-sense BCH codes of length 511. IEEETIT: IEEE Transactions on Information Theory, 44 (1998).
Canteaut, A. and Sendrier, N.: Cryptanalysis of the original McEliece cryptosys-tem. In Advances in Cryptology — ASIACRYPT '98 Proceedings, pages 187–199. Springer-Verlag (1998).
Courtois, N., Finiasz, M., and N.Sendrier: How to achieve a McEliece-based digital signature scheme. In Advances in Cryptology — ASIACRYPT 2001, volume 2248, pages 157–174. Springer-Verlag (2001).
Cover, T.: Enumerative source encoding. IEEE Transactions on Information Theory, 19(1):73–77 (1973).
Dallot, L., Tillich, J., Otmani, A.: Cryptanalysis of two McEliece cryptosys-tems based on quasi-cyclic codes (2008). CoRR, abs/0804.0409, available at http://arxiv.org/abs/0804.0409 (2008).
Engelbert, D., Overbeck, R., and Schmidt, A.: A summary of McEliece-type cryptosystems and their security. Journal of Mathematical Cryptology, 1(2):151– 199 (2007).
Finiasz, M.: Nouvelles constructions utilisant des codes correcteurs d'erreurs en cryptographie à clef publique. Thèse de doctorat, École Polytechnique (2004).
Fischer, J.B. and Stern, J.: An eficient pseudo-random generator provably as secure as syndrome decoding. In U.M. Maurer, editor, Advances in Cryptology — EUROCRYPT '96, volume 1070 of LNCS, pages 245–255. Springer-Verlag (1996).
Fossorier, M., Imai, H., and Kobara, K.: Modeling bit flipping decoding based on non orthogonal check sums and application to iterative decoding attack of McEliece cryptosystem. In Proc. of 2004 International Symposium on Information Theory and its Applications, Parma, Italy (ISITA'04)(October 2004).
Fujisaki, E. and Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. In Proc. of CRYPTO, volume 547 of LNCS, pages 535–554. Springer Verlag (1999).
Gabidulin, E.M. and Ourivski, A.V.: Column scrambler for the GPT cryptosys-tem. Discrete Applied Mathematics, 128(1):207–221 (2003).
Gabidulin, E.: Theory of codes with maximum rank distance. Problems of Information Transmission, 21, No. 1 (1985).
Gabidulin, E.: On public-key cryptosystems based on linear codes. In Proc. of 4th IMA Conference on Cryptography and Coding 1993, Codes and Ciphers. IMA Press (1995).
Gabidulin, E. and Loidreau, P.: Subfield subcodes of maximum-rank distance codes. In Seventh International Workshop on Algebraic and Combinatorial Coding Theory, volume 7 of ACCT, pages 151–156 (2000).
Gabidulin, E., Ourivski, A., Honary, B., and Ammar, B.: Reducible rank codes and their applications to cryptography. IEEE Transactions on Information Theory, 49(12):3289–3293 (2003).
Gabidulin, E., Paramonov, A., and Tretjakov, O.: Ideals over a non-commutative ring and their applications to cryptography. In Proc. Eurocrypt '91, volume 547 of LNCS. Springer Verlag (1991).
Gaborit, P.: Shorter keys for code based cryptography. In Proc. of WCC 2005, pages 81–90 (2005).
Gaborit, P. and Girault, M.: Lightweight code-based authentication and signature. In Proc. of ISIT 2007(2007).
Gaborit, P., Laudaroux, C., and Sendrier, N.: Synd: a very fast code-based cipher stream with a security reduction. In IEEE Conference, ISIT'07, pages 186–190. Nice, France (2007).
Gibson, K.: Equivalent Goppa codes and trapdoors to McEliece's public key cryptosystem. In D.W. Davies, editor, Advances in Cryptology — Eurocrypt'91, volume 547 of LNCS, pages 517–521. Springer Verlag (1991).
Harn, L. and Wang, D.C.: Cryptanalysis and modification of digital signature scheme based on error-correcting codes. Electronics Letters, 28(2):157–159 (1992).
Heise and Quattrocchi: Informations- und Codierungstheorie. Springer Berlin Heidelberg, 3 edition (1995).
Jabri, A.K.A.: A statistical decoding algorithm for general linear block codes. In Cryptography and Coding 2001, volume 2260 of LNCS, pages 1–8. Springer Verlag (2001).
Janwa, H. and Moreno, O.: McEliece public key cryptosystems using algebraic-geometric codes. Designes, Codes and Cryptography, 8:293–307 (1996).
Johansson, T. and Ourivski, A.: New technique for decoding codes in the rank metric and its cryptography applications. Problems of Information Transmission, 38, No. 3:237–246 (2002).
Kobara, K. and Imai, H.: Semantically secure McEliece public-key cryptosys-tems — conversions for McEliece PKC. In Practice and Theory in Public Key Cryptography — PKC '01 Proceedings. Springer Verlag (2001).
Kobara, K. and Imai, H.: On the one-wayness against chosen-plaintext attacks of the Loidreau's modified McEliece PKC. IEEE Transactions on Information Theory, 49, No. 12:3160–3168 (2003).
Lee, P. and Brickell, E.: An observation on the security of McEliece's public key cryptosystem. In Advances in Cryptology-EUROCRYPT'88, volume 330 of LNCS, pages 275–280. Springer Verlag (1989).
Leon, J.: A probabilistic algorithm for computing minimum weights of large error-correcting codes. IEEE Transactions on Information Theory, 34(5):1354– 1359 (1988).
Levine, L. and Myers, W.: Semiconductor memory reliability with error detecting and correcting codes.COMPUTER, 9(10):43–50 (1976). ISSN 0018-9162.
Li, Y., Deng, R., and Wang, X.: the equivalence of McEliece's and Niederreiter's public-key cryptosystems.IEEE Transactions on Information Theory, Vol. 40, pp. 271–273 (1994).
Lidl, R. and Niederreiter, H.: Introduction to finite fields and their applications. Cambridge University Press, 2 edition (1986).
Loidreau, P.: Strengthening McEliece cryptosystem. In Advances in Cryptology - ASIACRYPT '00 Proceedings, pages 585–598. Springer Verlag (2000).
Loidreau, P. and Overbeck, R.: Decoding rank errors beyond the error-correction capability. In Proc. of ACCT-10, Zvenigorod, pages 168–190 (2006).
Loidreau, P. and Sendrier, N.: Weak keys in the McEliece public-key cryptosystem.IEEE Transactions on Information Theory, 47, No. 3:1207 –1211 (March 2001).
MacWilliams, F. and Sloane, N.: The Theory of Error-Correctiong Codes. North-Holland Amsterdam, 7 edition (1992).
McEliece, R.: A public key cryptosystem based on algebraic coding theory.DSN progress report, 42–44:114–116 (1978).
Minder, L.: Cryptography based on error correcting codes. Phd thesis, EPFL (2007).
Minder, L. and Shokrollahi, A.: Cryptanalysis of the Sidelnikov cryptosystem. In M. Naor, editorAdvances in Cryptology — EUROCRYPT 2007, number 4515 in LNCS, pages 347–360. Springer (2007).
Montpetit, A.: Note sur la notion d'équivalence entre deux codes linéaires.Discrete Mathematics, 65:177–185 (1987).
Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory.Probl. Control and Inform. Theory, 15:19–34 (1986).
Overbeck, R.: Public key cryptography based on coding theory. Ph.D. Thesis, Available at http://elib.tu-darmstadt.de/diss/000823/.
Overbeck, R.: A new structural attack for GPT and variants. In Proc. of Mycrypt 2005, volume 3715 of LNCS, pages 50–63. Springer Verlag (2005).
Overbeck, R.: Statistical decoding revisited. In Proc. of ACISP 2006, volume 4058 of LNCS, pages 283–294. Springer Verlag (2006).
Overbeck, R.: Recognizing the structure of permuted reducible codes. In Proc. of WCC 2007, pages 269–276 (2007).
Overbeck, R.: Structural attacks for public key cryptosystems based on Gabidulin codes.Journal of Cryptology, 21(2):280–301 (2008).
Patterson, N.: Algebraic decoding of Goppa codes.IEEE Trans. Info.Theory, 21:203–207 (1975).
Petrank, E. and Roth, R.M.: Is code equivalence easy to decide? IEEE Trans. on IT, 43(5):1602–1604 (1997).
Pointcheval, D.: Chosen-ciphertext security for any one-way cryptosystem. In Proc. of PKC, volume 1751 of LNCS, pages 129–146. Springer Verlag (2000).
Ramabadran, T.V.: A coding scheme for m-out-of-ncodes.IEEE Transactions on Communications, 38(8):1156–1163 (1990).
Schalkwijk, J.P.M.: An algorithm for source coding.IEEE Transactions on Information Theory, 18(3):395–399 (1972).
Sendrier, N.: Efficient generation of binary words of given weight. In C. Boyd, editorCryptography and Coding ; proceedings of the 5th IMA conference, number 1025 in LNCS, pages 184–187. Springer-Verlag (1995).
Sendrier, N.: On the concatenated structure of a linear code.AAECC, 9(3):221–242 (1998).
Sendrier, N.: Cryptosystèmes à clé publique basés sur les codes correcteurs d'erreurs. Mémoire d'habilitation à diriger des recherches, Université Paris 6 (2002).
Sendrier, N.: On the security of the McEliece public-key cryptosystem. In M. Blaum, P. Farrell, and H. van Tilborg, editorsProceedings of Workshop honoring Prof. Bob McEliece on his 60th birthday, pages 141–163. Kluwer (2002).
Sendrier, N.: Encoding information into constant weight words. In IEEE Conference, ISIT'2005, pages 435–438. Adelaide, Australia (2005).
Sendrier, N.: Finding the permutation between equivalent linear codes: the support splitting algorithm.IEEE Transactions on Information Theory, 46:1193–1203 (Jul 2000).
Sendrier, N.: On the dimension of the hull.SIAM Journal on Discrete Mathematics, 10(2):282–293 (May 1997).
Sidelnikov, V.: A public-key cryptosystem based on binary Reed-Muller codes.Discrete Mathematics and Applications, 4 No. 3 (1994).
Sidelnikov, V. and Shestakov, S.: On insecurity of cryptosystems based on generalized Reed-Solomon codes.Discrete Mathematics and Applications, 2, No. 4:439–444 (1992).
Stern, J.: A method for finding codewords of small weight.Coding Theory and Applications, 388:106–133 (1989).
Stern, J.: A new identification scheme based on syndrome decoding. In Advances in Cryptology — CRYPTO'93, volume 773 of LNCS. Springer Verlag (1994).
Stern, J.: Can one design a signature scheme based on error-correcting codes. In ASIACRYPT '94, volume 917 of LNCS, pages 424–426 (1995).
van Tilburg, J.: On the McEliece cryptosystem. In S. Goldwasser, editorAdvances in Cryptology — CRYPTO'88, number 403 in LNCS, pages 119–131. Springer-Verlag (1990).
Véron, P.: Improved identification schemes based on error-correcting codes.Appl. Algebra Eng. Commun. Comput., 8(1):57–69 (1996).
Wagner, D.: A generalized birthday problem. In M. Yung, editorCRYPTO, volume 2442 of Lecture Notes in Computer Science, pages 288–303. Springer (2002). ISBN 3-540-44050-X.
Wieschebrink, C.: An attack on a modified Niederreiter encryption scheme. In Public Key Cryptography, volume 3958 of LNCS, pages 14–26 (2006).
Xinmei, W.: Digital signature scheme based on error-correcting codes.Electronics Letters, 26(13):898–899 (1990).
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Overbeck, R., Sendrier, N. (2009). Code-based cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds) Post-Quantum Cryptography. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-88702-7_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-88702-7_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-88701-0
Online ISBN: 978-3-540-88702-7
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)