nach oben

Mathematics in Computer Science

Erschienen in:

17.12.2019

Computer Algebra Tales on Goppa Codes and McEliece Cryptography

verfasst von: Narcís Sayols, Sebastià Xambó-Descamps

Erschienen in: Mathematics in Computer Science | Ausgabe 2/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The 40-year old McEliece public-key crypto-system is revisited with the help of recently developed resources: an improved Peterson–Gorenstein–Zierler decoder for alternant error-correcting codes; PyECC, a purely Python CAS; a package of PyECC functional utilities for the computations involved in defining, coding and decoding error-correcting codes; and a Web page with free-access to companion materials. The last two tales trace the evolution of the McEliece systems and provide an account about their current security levels.

Vorheriger Artikel Self-Dual Codes Over Chain Rings

Nächster Artikel Presentation of the Book The Gröbner Cover

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

http://jupyter.org/.

All random choices that appear in this paper are drawn according to the uniform distribution.

These kind of entities provide links that work with the pdf version. To find their destinations when reading the paper version, go directly to the page https://mat-web.upc.edu/people/sebastia.xambo/Papers/PyACA.html.

Note that this system was broken in 1982 by A. Shamir, see [53].

McEliece does not quote Goppa’s article and instead refers to pages 179–180 and 193–194 of [29].

Aragon, N., Gaborit, P., Hauteville, A., Tillich, J.-P.: Improvement of generic attacks on the rank syndrome decoding problem. https://hal.archives-ouvertes.fr/hal-01618464 (2017)

Augot, D., Batina, L., Bernstein, D.J., Bos, J., Buchmann, J., Castryck, W., Dunkelman, O., Güneysu, T., Gueron, S., Hülsing, A., Lange, T., Mohamed, M.S.E., Rechberger, C., Schwabe, P., Sendrier, N., Vercauteren, F., Yang, B.Y.: Initial recommendations of long-term secure post-quantum systems. PQCRYPTO / ICT-645622 / Horizon 2020 (2015). https://pqcrypto.eu.org/docs/initial-recommendations.pdf

Barbier, M., Barreto, P.S.L.M.: Key Reduction of McEliece’s cryptosystem using list decoding. In: Kuleshov, A., Blinovsky, V.M., Ephremides, A., (eds), International Symposium of Information Theory (ISIT), Saint-Peterburg, Russia. IEEE, pp 2657–2661 (2011). https://hal.inria.fr/inria-00565343/file/preprint.pdf

Berlekamp, E.: Algebraic Coding Theory. McGraw-Hill, 1968. Revised edition by Aegean Park Press in 1984, revised edition by World Scientific Publishing Co. in 2015, with a new Preface

Berlekamp, E.R., McEliece, R.J., van Tilborg, H.C.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24(3), 384–386 (1978)MathSciNetCrossRef

Bernstein, D.J.: Index of formal scientific papers (2018). https://cr.yp.to/papers.html. Consulted on 1st February

Bernstein, D.J.: Introduction to post-quantum cryptography. In: Post-Quantum Cryptography. Springer, pp. 1–14. Introductory chapter of [10] (2009). http://www.pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf

Bernstein, D. J.: Is the security of quantum cryptography guaranteed by the laws of physics? (2017). https://sidechannels.cr.yp.to/qkd/holographic-20160326.pdf

Bernstein, D.J., Biasse, J.F., Mosca, M.: A low-resource quantum factoring algorithm. In: Lange, T., Takagi, T., (eds.) Post-Quantum Cryptography-8th International Workshop, PQCrypto 2017, Lecture Notes in Computer Science 10346. Springer, pp. 330–346 (2017). Proceedings of the PQCrypto 2017 workshop held at Utrecht, the Netherlands, June 26-28. https://cr.yp.to/papers/grovernfs-20170419.pdf

10.

Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.): Post-Quantum Cryptography. Springer, Berlin (2009)MATH

11.

Bernstein, D.J., Lange, T.: Post-quantum cryptography -dealing with the fallout of physics success. Nature 549, 188–194 (2017)CrossRef

12.

Bernstein, D.J., Lange, T., Peters, C.: Attacking and defending the McEliece cryptosystem. In: Buchmann, J., Ding, J., (eds) Post-Quantum Cryptography, Number 5299 in Lecture Notes in Computer Science, Proceedings of the Second international Workshop PQCrypto 2008, October 17–19, Cincinnati, OH, USA. Springer pp. 31–45 (2008)

13.

Bernstein, D.J., Lange, T., Peters, C.: Wild McEliece incognito. In: Yang, B.Y., (eds) Post-quantum Cryptography–4th International Workshop, PQCrypto 2011, Lecture Notes in Computer Science 7071, Proceedings of the PQCrypto 2011 Workshop Held at Taipei, Taiwan, November 29–December 2, 2011. Springer, pp 244–254 (2011) . https://cr.yp.to/codes/wild2-20110915.pdf

14.

Bernstein, D.J., Yang, B.Y.: Asymptotically faster quantum algorithms to solve multivariate quadratic equations (2017). https://cr.yp.to/papers/groverxl-20171215.pdf

15.

Biswas, B.: Implementational aspects of code-based cryptography. PhD thesis, L’École Polytechnique / INRIA (2010). https://hal.archives-ouvertes.fr/pastel-00523007/

16.

Cameron, P.J.: Notes on Cryptography (2013). http://www.maths.qmul.ac.uk/~pjc/notes/crypt.pdf

17.

Campbell, E.T., Terhal, B.M., Vuillot, C.: The steep road towards robust and universal quantum computation (2016). https://arxiv.org/pdf/1612.07330.pdf

18.

Courtois, N.T., Finiasz, M., Sendrier, N.: How to achieve a McEliece-based digital signature scheme. In: International Conference on the Theory and Application of Cryptology and Information Security. Springer, pp. 157–174 (2001)

19.

Deneuville, J.-C., Gaborit, P., Zémor, G.: Ouroboros: A simple, secure and efficient key exchange protocol based on coding theory. In: Lange, T., Takagi, T., (eds), Post-Quantum Cryptography, Number 10346 in Lecture Notes in Computer Science. Proceedings of the International Workshop PQCrypto 2017, pp 18–34 (2017). https://rd.springer.com/chapter/10.1007%2F978-3-319-59879-6_2

20.

Diffie, W., Hellmann, M.: New directions in cryptography. IEEE Trans. Inf. Theory 22, 644–654 (1976)MathSciNetCrossRef

21.

Dinh, H., Moore, C., Russell, A.: McEliece and Niederreiter cryptosystems that resist quantum Fourier sampling attacks. In: Rogaway, P. (ed) CRYPTO 2011. Springer, pp. 761–779 (2011). https://www.iacr.org/archive/crypto2011/68410758/68410758.pdf

22.

Engelbert, D., Overbeck, R., Schmidt, A.: A summary of McEliece-type cryptosystems and their security. J. Math. Cryptol. 1(2), 151–199 (2007)MathSciNetCrossRef

23.

Farré, R., Sayols, N., Xambó-Descamps, S.: On the PGZ decoding algorithm for alternant codes. Comput. Appl. Math. (in press) (2018). arXiv:1704.05259

24.

Gaborit, P.: Shorter keys for code based cryptography. In: Proceedings of Workshop on Codes and Cryptography, pp. 81–90 (2005)

25.

Gaborit, P., Ruatta, O., Schrek, J.: On the complexity of the rank syndrome decoding problem. IEEE Trans. Inf. Theory 62(2), 1006–1019 (2016). https://arxiv.org/pdf/1301.1026.pdf

26.

Goppa, V.D.: A new class of linear correcting codes. Probl. Pederachi Inf. 6(3), 24–34 (1970). (in Russian)MathSciNetMATH

27.

Gorenstein, D., Zierler, N.: A class of error-correcting codes in \(p^m\) symbols. J. Soc. Ind. Appl. Math. 9(2), 2007–214 (1961)CrossRef

28.

Katz, J., Lindell, Y.: Modern Cryptography. Cryptography and Network Security. Chapmann & Hall/CRC, London (2008)MATH

29.

McEliece, R.J.: The Theory of Information and Coding Volume 3 of The Encyclopedia of Mathematics and its Applications. Addison-Wesley, Boston (1977)

30.

McEliece, R. J.: A public-key cryptosystem based on algebraic coding theory. Jet Propulsion Laboratory, DSN Progress Report 42-44 (1978). http://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.pdf

31.

Merkle, R.C., Hellman, M.E.: Hiding information and signatures in trapdoor knapsacks. IEEE Int. Symp. Inf. Theory 24(5), 525–530 (1978)CrossRef

32.

Misoczki, R., Tillich, J.-P., Sendrier, N., Barreto, P.S.L.M.: MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes (2012). https://eprint.iacr.org/2012/409.pdf

33.

Molina, S., Sayols, N., Xambó-Descamps, S.: A bootstrap for the number of \({\mathbb{F}}_{q^m}\)-rational points on a curve over \({\mathbb{F}}_q\) (2017)

34.

Niebuhr, R.: Attacking and Defending Code-based Cryptosystems. Ph.D. thesis (2012)

35.

Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Probl. Control Inf. Theory 15, 159–166 (1986)MathSciNetMATH

36.

NISTIR-2018. Report on post-quantum cryptography (2018). https://nvlpubs.nist.gov/nistpubs/ir/2016/NIST.IR.8105.pdf

37.

Overbeck, R., Sendrier, N.: Code-based cryptography. In: Post-Quantum Cryptography. Springer. See [10], pp. 95–146 (2009)

38.

Patterson, N.J.: The algebraic decoding of Goppa codes. IEEE Trans. Inf. Theory 21(2), 203–207 (1975)MathSciNetCrossRef

39.

Persichetti, E.: Improving the Efficiency of Code-Based Cryptography. Ph.D. thesis, Department of Mathematics, University of Auckland, New Zeeland (2012). https://www.math.auckland.ac.nz/~sgal018/EdoardoPhD.pdf

40.

Peterson, W.W.: Encoding and error-correction procedures for the Bose–Chaudhuri codes. IRE Trans. Inf. Theory 6, 459–470 (1960)MathSciNetCrossRef

41.

Peterson, W.W., Weldon, E.J.: Error-Correcting Codes (2nd edition). MIT Press, Boston (1972)MATH

42.

Post-Quantum Cryptography 2018. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography. First PQC Standardization Conference organized by the NIST Computer Security Resource Center

43.

Post-quantum cryptography (2018). https://pqcrypto.org/

44.

Randall, D.: Efficient generation of random nonsingular matrices, 1991. Report No. UCB/CSD-91-658 (November 1991). https://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/CSD-91-658.pdf

45.

Repka, M., Zadaj, P.: Overview of the McEliece cryptosystem and its security. Tatra Mt. Math. Publ. 60, 57–83 (2014)MathSciNetMATH

46.

Rivest, R., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosistems. Commun. ACM 21, 120–126 (1978)CrossRef

47.

Rué, J., Xambó-Descamps, S.: Introducció matemàtica a la computació quàntica. Butlletí de la Societat Catalana de Matemàtiques, 28(2), 183–231 (2013). English version available at https://mat-web.upc.edu/people/sebastia.xambo/QC/qc.pdf

48.

Sayols, N., Xambó-Descamps, S.: A Python package for the construction, coding and decoding of error-correcting codes (2017). https://mat-web.upc.edu/people/sebastia.xambo/PyECC.html

49.

Sayols, N., Xambó-Descamps, S.: Computer algebra tales on Goppa codes and McEliece cryptography: Python sources and companion materials (2018). https://mat-web.upc.edu/people/sebastia.xambo/Papers/PyACA.html

50.

Sendrier, N.: Efficient generation of binary words of given weight. In: Proceedings of the 5th IMA Conference on Cryptography and Coding. Springer, pp. 184–187 (1995). https://link.springer.com/chapter/10.1007/3-540-60693-9_20

51.

Sendrier, N.: Cryptosystm̀es à clé publique basés sur les codes correcteurs d’erreurs. Université Pierre et Marie Curie, Institut National de Recherche en Informatique et Automatique, INRIA Rocquencourt. Mémoire d’habilitation à diriger des recherches (2002)

52.

Sendrier, N.: On the use of structured codes in code based cryptography. In: Nikova, S., Prenell, B., Storme, L., (eds), Coding Theory and Cryptography III. Contactforum. Koninklijke Vlaamse Academie van België voor Wetenschaeppen en Kunsten. pp. 59–68 (2009). https://www.rocq.inria.fr/secret/Nicolas.Sendrier/PDFs/Sen10c.pdf

53.

Shamir, A.: A polynomial-time algorithm for breaking the basic Merkle–Hellman cryptosystem. IEEE Trans. Inf. Theory 30(5), 699–704 (1984)MathSciNetCrossRef

54.

Shor, P.: Algorithms for quantum computation: Discrete logarithms and factorization. In: Symposium of Foundations on Computer Science (Santa Fe, New Mexico, 1994). For a revised and expanded version of this paper, see [53] (1994)

55.

Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484–1509 (1997)MathSciNetCrossRef

56.

Tillich, J.-P.: The decoding failure probability of MDPC codes (2018). https://arxiv.org/pdf/1801.04668.pdf

57.

Wang, J.: Quantum resistant random linear code based public key encryption scheme RLCE. In: Proceedings IEEE ISIT 2016, pp. 2519–2523 (2016). https://eprint.iacr.org/2015/298.pdf

58.

Wang, J.: Decoding generalized Reed-Solomon codes and its application to RLCE encryption schemes (2017). https://arxiv.org/pdf/1702.07737.pdf

59.

Wikipedia. Quantum cryptography (2018). https://en.wikipedia.org/wiki/Quantum_cryptography

60.

Xambó-Descamps, S., Miret, J.M., Sayols, N.: Intersection Theory and Enumerative Geometry–A Computational Primer. Springer, Berlin (2019)

61.

Xambó-Descamps, S., Sayols, N.: Error-Correcting Codes. A Computational Primer. Universitext. Springer, 2019. 2nd edition of [60], with Three New Chapters, Corrections, and an Extended Introductory Chapter. Companion materials, including source code, available at https://mat-web.upc.edu/people/sebastia.xambo/PyECC.html

62.

Xambó-Descamps, S.: Block Error-correcting Codes: A Computational Primer. Universitext, Springer (2003)CrossRef

Titel: Computer Algebra Tales on Goppa Codes and McEliece Cryptography
verfasst von: Narcís Sayols
Sebastià Xambó-Descamps
Publikationsdatum: 17.12.2019
Verlag: Springer International Publishing
Erschienen in: Mathematics in Computer Science / Ausgabe 2/2020
Print ISSN: 1661-8270
Elektronische ISSN: 1661-8289
DOI: https://doi.org/10.1007/s11786-019-00444-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2020

Analysing the “Calculator Effect” of Different Kinds of Software for School Arithmetic and Algebra

Nonlinear Oscillations of a Spring Pendulum at the 1:1:2 Resonance by Normal Form Methods

Quantum Codes Obtained from Some Constacyclic Codes Over a Family of Finite Rings

Binary Isodual Codes Having an Automorphism of Odd Prime Order

Using Oshima Splines to Produce Accurate Numerical Results and High Quality Graphical Output

Computing Perturbations in the Two-Planetary Three-Body Problem with Masses Varying Non-isotropically at Different Rates

Premium Partner