Communications in Cryptology IACR CiC

Understanding binary-Goppa decoding

Authors

Daniel J. Bernstein
Daniel J. Bernstein
University of Illinois at Chicago, USA
Ruhr University Bochum, Germany
Academia Sinica, Taiwan
djb at cr dot yp dot to

Abstract

This paper reviews, from bottom to top, a polynomial-time algorithm to correct $t$ errors in classical binary Goppa codes defined by squarefree degree-$t$ polynomials. The proof is factored through a proof of a simple Reed–Solomon decoder, and the algorithm is simpler than Patterson's algorithm. All algorithm layers are expressed as Sage scripts backed by test scripts. All theorems are formally verified. The paper also covers the use of decoding inside the Classic McEliece cryptosystem, including reliable recognition of valid inputs.

References

[@1998]
39th annual symposium on foundations of computer science, FOCS '98, November 8–11, 1998, Palo Alto, California, USA, IEEE Computer Society, 1998. https://doi.org/10.1109/SFCS.1998.
Google Scholar ePrint
[@2000]
Proceedings of the 32nd annual ACM symposium on theory of computing, New York, 2000. Association for Computing Machinery.
Google Scholar ePrint
[AbrMKS22]
Oskar Abrahamsson, Magnus O. Myreen, Ramana Kumar, and Thomas Sewell. Candle: A verified implementation of HOL Light. In June Andronick and Leonardo de Moura, editors, 13th international conference on interactive theorem proving, ITP 2022, August 7–10, 2022, Haifa, Israel, volume 237, 3:1–3:17. Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPICS.ITP.2022.3.
Google Scholar ePrint
[AlbCPTT17]
Martin Albrecht, Carlos Cid, Kenneth G. Paterson, CJ Tjhai, and Martin Tomlinson. NTS-KEM. 2017.
Google Scholar ePrint
[AlbCPTT19]
Martin Albrecht, Carlos Cid, Kenneth G. Paterson, CJ Tjhai, and Martin Tomlinson. NTS-KEM: second round submission. 2019.
Google Scholar ePrint
[AndM22]
June Andronick and Leonardo de Moura, editors. 13th international conference on interactive theorem proving, ITP 2022, August 7–10, 2022, Haifa, Israel, volume 237, Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 2022.
Google Scholar ePrint
[Berl68]
Elwyn R. Berlekamp. Algebraic coding theory. McGraw-Hill, 1968.
Google Scholar ePrint
[Bern08a]
Daniel J. Bernstein. Fast multiplication and its applications. In Joe P. Buhler and Peter Stevenhagen, editors, Surveys in algorithmic number theory, volume 44 of Mathematical Sciences Research Institute Publications, 325–384. New York, 2008. Cambridge University Press.
Google Scholar ePrint
[Bern08b]
Daniel J. Bernstein. Reducing lattice bases to find small-height values of univariate polynomials. In Joe P. Buhler and Peter Stevenhagen, editors, Surveys in algorithmic number theory, volume 44 of Mathematical Sciences Research Institute Publications, 421–446. New York, 2008. Cambridge University Press.
Google Scholar ePrint
[Bern11a]
Daniel J. Bernstein. List decoding for binary Goppa codes. In Yeow Meng Chee, Zhenbo Guo, San Ling, Fengjing Shao, Yuansheng Tang, Huaxiong Wang, and Chaoping Xing, editors, Coding and cryptology—third international workshop, IWCC 2011, Qingdao, China, May 30–June 3, 2011, proceedings, volume 6639 of Lecture Notes in Computer Science, 62–80. Springer, 2011. https://doi.org/10.1007/978-3-642-20901-7_4.
Google Scholar ePrint
[Bern11b]
Daniel J. Bernstein. Simplified high-speed high-distance list decoding for alternant codes. In Bo-Yin Yang, editor, Post-quantum cryptography—4th international workshop, PQCrypto 2011, Taipei, Taiwan, November 29–December 2, 2011, proceedings, volume 7071, 200–216. Springer, 2011. https://doi.org/10.1007/978-3-642-25405-5_13.
Google Scholar ePrint
[Bern20]
Daniel J. Bernstein. Verified fast formulas for control bits for permutation networks. 2020.
Google Scholar ePrint
[BernBD09]
Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, editors. Post-quantum cryptography, Springer, 2009. https://doi.org/10.1007/978-3-540-88702-7.
Google Scholar ePrint
[BernCLM+17]
Daniel J. Bernstein, Tung Chou, Tanja Lange, Ingo von Maurich, Rafael Misoczki, Ruben Niederhagen, Edoardo Persichetti, Christiane Peters, Peter Schwabe, Nicolas Sendrier, Jakub Szefer, and Wen Wang. Classic McEliece: conservative code-based cryptography. 2017.
Google Scholar ePrint
[BernCLM+19]
Daniel J. Bernstein, Tung Chou, Tanja Lange, Ingo von Maurich, Rafael Misoczki, Ruben Niederhagen, Edoardo Persichetti, Christiane Peters, Peter Schwabe, Nicolas Sendrier, Jakub Szefer, and Wen Wang. Classic McEliece: conservative code-based cryptography. 2019.
Google Scholar ePrint
[BernCS13]
Daniel J. Bernstein, Tung Chou, and Peter Schwabe. McBits: fast constant-time code-based cryptography. In Guido Bertoni and Jean-Sébastien Coron, editors, Cryptographic hardware and embedded systems—CHES 2013—15th international workshop, Santa Barbara, CA, USA, August 20–23, 2013, proceedings, volume 8086, 250–272. Springer, 2013. https://doi.org/10.1007/978-3-642-40349-1_15.
Google Scholar ePrint
[BernLP11]
Daniel J. Bernstein, Tanja Lange, and Christiane Peters. Wild McEliece. In Alex Biryukov, Guang Gong, and Douglas R. Stinson, editors, Selected areas in cryptography—17th international workshop, SAC 2010, Waterloo, Ontario, Canada, August 12–13, 2010, revised selected papers, volume 6544 of Lecture Notes in Computer Science, 143–158. Springer, 2011. https://doi.org/10.1007/978-3-642-19574-7_10.
Google Scholar ePrint
[BernY19]
Daniel J. Bernstein and Bo-Yin Yang. Fast constant-time gcd computation and modular inversion. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019.3:340–398, 2019. https://doi.org/10.46586/tches.v2019.i3.340-398.
Google Scholar ePrint
[BertC13]
Guido Bertoni and Jean-Sébastien Coron, editors. Cryptographic hardware and embedded systems—CHES 2013—15th international workshop, Santa Barbara, CA, USA, August 20–23, 2013, proceedings, volume 8086, Springer, 2013. https://doi.org/10.1007/978-3-642-40349-1.
Google Scholar ePrint
[BhaPTY03]
Vijay K. Bhargava, H. Vincent Poor, Vahid Tarokh, and Seokho Yoon, editors. Communications, information and network security. With a foreword by Richard E. Blahut, Springer, 2003. https://doi.org/10.1007/978-1-4757-3789-9.
Google Scholar ePrint
[BirGS11]
Alex Biryukov, Guang Gong, and Douglas R. Stinson, editors. Selected areas in cryptography—17th international workshop, SAC 2010, Waterloo, Ontario, Canada, August 12–13, 2010, revised selected papers, volume 6544 of Lecture Notes in Computer Science, Springer, 2011. https://doi.org/10.1007/978-3-642-19574-7.
Google Scholar ePrint
[BlaH20]
Jasmin Blanchette and Catalin Hritcu, editors. Proceedings of the 9th ACM SIGPLAN international conference on certified programs and proofs, CPP 2020, New Orleans, LA, USA, January 20–21, 2020, ACM, 2020. https://doi.org/10.1145/3372885.
Google Scholar ePrint
[Bon00]
Dan Boneh. Finding smooth integers in short intervals using CRT decoding. In Proceedings of the 32nd annual ACM symposium on theory of computing, 265–272. New York, 2000. Association for Computing Machinery. https://doi.org/10.1145/335305.335337.
Google Scholar ePrint
[Bon02]
Dan Boneh. Finding smooth integers in short intervals using CRT decoding. Journal of Computer and System Sciences, 64:768–784, 2002. https://doi.org/10.1006/jcss.2002.1827.
Google Scholar ePrint
[BraCPR22]
Martin Brain, Carlos Cid, Rachel Player, and Wrenna Robson. Verifying Classic McEliece: examining the role of formal methods in post-quantum cryptography standardisation. In Jean-Christophe Deneuville, editor, Code-based cryptography—10th international workshop, CBCrypto 2022, Trondheim, Norway, May 29–30, 2022, revised selected papers, volume 13839, 21–36. Springer, 2022. https://doi.org/10.1007/978-3-031-29689-5_2.
Google Scholar ePrint
[Bre81]
Claude Brezinski. The long history of continued fractions and Padé approximants. In Marcel G. de Bruin and Herman van Rossum, editors, Padé approximation and its applications, Amsterdam 1980, proceedings of a conference held in Amsterdam, the Netherlands, October 29–31, 1980, volume 888 of Lecture Notes in Mathematics, 1–27. Springer, 1981. https://doi.org/10.1007/BFb0095574.
Google Scholar ePrint
[BruR81]
Marcel G. de Bruin and Herman van Rossum, editors. Padé approximation and its applications, Amsterdam 1980, proceedings of a conference held in Amsterdam, the Netherlands, October 29–31, 1980, volume 888 of Lecture Notes in Mathematics, Springer, 1981. https://doi.org/10.1007/BFb0095573.
Google Scholar ePrint
[BuhS08]
Joe P. Buhler and Peter Stevenhagen, editors. Surveys in algorithmic number theory, volume 44 of Mathematical Sciences Research Institute Publications, New York, 2008. Cambridge University Press.
Google Scholar ePrint
[CanC95]
Anne Canteaut and Florent Chabaud. Improvements of the attacks on cryptosystems based on error-correcting codes. 1995.
Google Scholar ePrint
[CanS98]
Anne Canteaut and Nicolas Sendrier. Cryptanalysis of the original McEliece cryptosystem. In Kazuo Ohta and Dingyi Pei, editors, Advances in cryptology—ASIACRYPT'98: proceedings of the international conference on the theory and application of cryptology and information security held in Beijing, volume 1514 of Lecture Notes in Computer Science, 187–199. Springer, 1998. https://doi.org/10.1007/3-540-49649-1_16.
Google Scholar ePrint
[CheeGLS+11]
Yeow Meng Chee, Zhenbo Guo, San Ling, Fengjing Shao, Yuansheng Tang, Huaxiong Wang, and Chaoping Xing, editors. Coding and cryptology—third international workshop, IWCC 2011, Qingdao, China, May 30–June 3, 2011, proceedings, volume 6639 of Lecture Notes in Computer Science, Springer, 2011. https://doi.org/10.1007/978-3-642-20901-7.
Google Scholar ePrint
[ChenC21]
Ming-Shing Chen and Tung Chou. Classic McEliece on the ARM Cortex-M4. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021.3:125–148, 2021. https://doi.org/10.46586/tches.v2021.i3.125-148.
Google Scholar ePrint
[Cho17]
Tung Chou. McBits revisited. In Wieland Fischer and Naofumi Homma, editors, Cryptographic hardware and embedded systems—CHES 2017—19th international conference, Taipei, Taiwan, September 25–28, 2017, proceedings, volume 10529, 213–231. Springer, 2017. https://doi.org/10.1007/978-3-319-66787-4_11.
Google Scholar ePrint
[Cho18]
Tung Chou. McBits revisited: toward a fast constant-time code-based KEM. Journal of Cryptographic Engineering, 8:95–107, 2018. https://doi.org/10.1007/s13389-018-0186-9.
Google Scholar ePrint
[Cho20]
Tung Chou. An IND-CCA2 attack against the 1st- and 2nd-round versions of NTS-KEM. In Diana Maimut, Andrei-George Oprina, and Damien Sauveron, editors, Innovative security solutions for information technology and communications—13th international conference, SecITC 2020, Bucharest, Romania, November 19–20, 2020, revised selected papers, volume 12596, 165–184. Springer, 2020. https://doi.org/10.1007/978-3-030-69255-1_11.
Google Scholar ePrint
[CohH15]
Henry Cohn and Nadia Heninger. Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications, 9:311–339, 2015. https://doi.org/10.3934/amc.2015.9.311.
Google Scholar ePrint
[Com01]
Douglas E. Comer. How to criticize computer scientists: or, avoiding ineffective deprecation and making insults more pointed. 2001.
Google Scholar ePrint
[Den23]
Jean-Christophe Deneuville, editor. Code-based cryptography—10th international workshop, CBCrypto 2022, Trondheim, Norway, May 29–30, 2022, revised selected papers, volume 13839, Springer, 2023. https://doi.org/10.1007/978-3-031-29689-5.
Google Scholar ePrint
[Dor87]
Jean Louis Dornstetter. On the equivalence between Berlekamp's and Euclid's algorithms. IEEE Transactions on Information Theory, 33:428–431, 1987. https://doi.org/10.1109/TIT.1987.1057299.
Google Scholar ePrint
[Emd13]
Peter van Emde Boas. The correspondence between Donald E. Knuth and Peter van Emde Boas on priority deques during the spring of 1977. 2013.
Google Scholar ePrint
[Euc300BC]
Euclid. Elements. No publisher listed, about 300 B.C.
Google Scholar ePrint
[FisH17]
Wieland Fischer and Naofumi Homma, editors. Cryptographic hardware and embedded systems—CHES 2017—19th international conference, Taipei, Taiwan, September 25–28, 2017, proceedings, volume 10529, Springer, 2017. https://doi.org/10.1007/978-3-319-66787-4.
Google Scholar ePrint
[For65a]
G. David Forney, Jr. Concatenated codes. PhD thesis, Massachusetts Institute of Technology, 1965.
Google Scholar ePrint
[For65b]
G. David Forney, Jr. On decoding BCH codes. IEEE Transactions on Information Theory, 11:549–557, 1965. https://doi.org/10.1109/TIT.1965.1053825.
Google Scholar ePrint
[Gao03]
Shuhong Gao. A new algorithm for decoding Reed-Solomon codes. In Vijay K. Bhargava, H. Vincent Poor, Vahid Tarokh, and Seokho Yoon, editors, Communications, information and network security. With a foreword by Richard E. Blahut, 55–68. Springer, 2003. https://doi.org/10.1007/978-1-4757-3789-9_5.
Google Scholar ePrint
[Gau1801]
Carl Friedrich Gauss. Disquisitiones arithmeticae. No publisher listed, 1801.
Google Scholar ePrint
[GhoV14]
Santosh Ghosh and Ingrid Verbauwhede. BLAKE-512-based 128-bit CCA2 secure timing attack resistant McEliece cryptoprocessor. IEEE Transactions on Computers, 63:1124–1133, 2014. https://doi.org/10.1109/TC.2012.271.
Google Scholar ePrint
[Gop70]
Valerii D. Goppa. A new class of linear correcting codes. Problemy Peredachi Informatsii, 6:24–30, 1970.
Google Scholar ePrint
[GorZ61]
Daniel Gorenstein and Neal Zierler. A class of error-correcting codes in $p^m$ symbols. Journal of the Society for Industrial and Applied Mathematics, 9:207–214, 1961. https://doi.org/10.1137/0109020.
Google Scholar ePrint
[GurS98]
Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon and algebraic-geometry codes. In 39th annual symposium on foundations of computer science, FOCS '98, November 8–11, 1998, Palo Alto, California, USA, 28–39. IEEE Computer Society, 1998. https://doi.org/10.1109/SFCS.1998.
Google Scholar ePrint
[GurS99]
Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Transactions on Information Theory, 45:1757–1767, 1999. https://doi.org/10.1109/18.782097.
Google Scholar ePrint
[Har96]
John Harrison. HOL Light: A tutorial introduction. In Mandayam K. Srivas and Albert John Camilleri, editors, Formal methods in computer-aided design, first international conference, FMCAD '96, Palo Alto, California, USA, November 6–8, 1996, proceedings, volume 1166 of Lecture Notes in Computer Science, 265–269. Springer, 1996. https://doi.org/10.1007/BFb0031814.
Google Scholar ePrint
[HeiHT92]
G. H. L. M. Heideman, Fokke W. Hoeksema, and Henk E. P. Tattje, editors. Proceedings of the 13th symposium on information theory in the Benelux, Werkgemeenschap voor Informatie- en Communicatietheorie, 1992.
Google Scholar ePrint
[Jus76]
Jørn Justesen. On the complexity of decoding Reed–Solomon codes. IEEE Transactions on Information Theory, 22:237–238, 1976. https://doi.org/10.1109/TIT.1976.1055516.
Google Scholar ePrint
[Knu74]
Donald E. Knuth. Structured programming with go to statements. Computing Surveys, 6:261–301, 1974. https://doi.org/10.1145/356635.356640.
Google Scholar ePrint
[Knu97]
Donald E. Knuth. The art of computer programming, volume 2: seminumerical algorithms. Addison-Wesley, 3rd edition, 1997. ISBN 0-201-89684-2.
Google Scholar ePrint
[Kro1881]
Leopold Kronecker. Zur Theorie der Elimination einer Variablen aus zwei algebraischen Gleichungen. Monatsberichte der Königlich Preussischen Akademie der Wissenschaften zu Berlin, 1881.
Google Scholar ePrint
[Lag1773]
Joseph-Louis Lagrange. Recherches d’arithmétique. Nouveaux Mémoires de l’Académie royale des Sciences et Belles-Lettres de Berlin, 1773.
Google Scholar ePrint
[Lag1776]
Joseph-Louis Lagrange. Sur l’usage des fractions continues dans le calcul intégral. Nouveaux Mémoires de l’Académie royale des Sciences et Belles-Lettres de Berlin, 1776.
Google Scholar ePrint
[MaiOS21]
Diana Maimut, Andrei-George Oprina, and Damien Sauveron, editors. Innovative security solutions for information technology and communications—13th international conference, SecITC 2020, Bucharest, Romania, November 19–20, 2020, revised selected papers, volume 12596, Springer, 2021. https://doi.org/10.1007/978-3-030-69255-1.
Google Scholar ePrint
[Mas69]
James Massey. Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory, 15:122–127, 1969. https://doi.org/10.1109/TIT.1969.1054260.
Google Scholar ePrint
[Mat20]
The mathlib community. The Lean mathematical library. In Jasmin Blanchette and Catalin Hritcu, editors, Proceedings of the 9th ACM SIGPLAN international conference on certified programs and proofs, CPP 2020, New Orleans, LA, USA, January 20–21, 2020, 367–381. ACM, 2020. https://doi.org/10.1145/3372885.3373824.
Google Scholar ePrint
[Mce78]
Robert J. McEliece. A public-key cryptosystem based on algebraic coding theory. 1978.
Google Scholar ePrint
[Mil75]
William H. Mills. Continued fractions and linear recurrences. Mathematics of Computation, 29:173–180, 1975. https://doi.org/10.1090/S0025-5718-1975-0369276-7.
Google Scholar ePrint
[MouU21]
Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. In André Platzer and Geoff Sutcliffe, editors, Automated deduction—CADE 28—28th international conference on automated deduction, virtual event, July 12–15, 2021, proceedings, volume 12699, 625–635. Springer, 2021. https://doi.org/10.1007/978-3-030-79876-5_37.
Google Scholar ePrint
[Nie86]
Harald Niederreiter. Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory, 15:159–166, 1986. https://doi.org/?
Google Scholar ePrint
[OhtP98]
Kazuo Ohta and Dingyi Pei, editors. Advances in cryptology—ASIACRYPT'98: proceedings of the international conference on the theory and application of cryptology and information security held in Beijing, volume 1514 of Lecture Notes in Computer Science, Springer, 1998. https://doi.org/10.1007/3-540-49649-1.
Google Scholar ePrint
[Orm19]
Tavis Ormandy. Issue 1804: cryptoapi: SymCrypt modular inverse algorithm. 2019.
Google Scholar ePrint
[OveS09]
Raphael Overbeck and Nicolas Sendrier. Code-based cryptography. In Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, editors, Post-quantum cryptography, 95–145. Springer, 2009. https://doi.org/10.1007/978-3-540-88702-7_4.
Google Scholar ePrint
[Pad1892]
Henri Padé. Sur la représentation approchée d'une fonction par des fractions rationnelles. Annales scientifiques de l'École normale supérieure, 9:3–93, 1892. https://doi.org/10.24033/asens.378.
Google Scholar ePrint
[Pate19]
Kenneth G. Paterson. New version of NTS-KEM. 2019.
Google Scholar ePrint
[Patt75]
Nicholas J. Patterson. The algebraic decoding of Goppa codes. IEEE Transactions on Information Theory, 21:203–207, 1975. https://doi.org/10.1109/TIT.1975.1055350.
Google Scholar ePrint
[Pet60]
W. Wesley Peterson. Encoding and error-correction procedures for the Bose-Chaudhuri codes. Transactions of the Institute of Radio Engineers, 6:459–470, 1960. https://doi.org/10.1109/TIT.1960.1057586.
Google Scholar ePrint
[PlaS21]
André Platzer and Geoff Sutcliffe, editors. Automated deduction—CADE 28—28th international conference on automated deduction, virtual event, July 12–15, 2021, proceedings, volume 12699, Springer, 2021. https://doi.org/10.1007/978-3-030-79876-5.
Google Scholar ePrint
[Pra62]
Eugene Prange. The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory, IT-8:S5–S9, 1962. https://doi.org/10.1109/TIT.1962.1057777.
Google Scholar ePrint
[PreBGV92]
Bart Preneel, Antoon Bosselaers, René Govaerts, and Joos Vandewalle. A software implementation of the McEliece public-key cryptosystem. In G. H. L. M. Heideman, Fokke W. Hoeksema, and Henk E. P. Tattje, editors, Proceedings of the 13th symposium on information theory in the Benelux, 119–126. Werkgemeenschap voor Informatie- en Communicatietheorie, 1992.
Google Scholar ePrint
[ReeS60]
Irving S. Reed and Gustave Solomon. Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics, 8:300–304, 1960. https://doi.org/10.1137/0108018.
Google Scholar ePrint
[Sar77]
Dilip V. Sarwate. On the complexity of decoding Goppa codes. IEEE Transactions on Information Theory, 23:515–516, 1977. https://doi.org/10.1109/TIT.1977.1055732.
Google Scholar ePrint
[Shi89]
Akira Shiozaki. Decoding of redundant residue polynomial codes using Euclid's algorithm. IEEE Transactions on Information Theory, 34:1351–1354, 1989. https://doi.org/10.1109/18.21269.
Google Scholar ePrint
[SriC96]
Mandayam K. Srivas and Albert John Camilleri, editors. Formal methods in computer-aided design, first international conference, FMCAD '96, Palo Alto, California, USA, November 6–8, 1996, proceedings, volume 1166 of Lecture Notes in Computer Science, Springer, 1996. https://doi.org/10.1007/BFB0031795.
Google Scholar ePrint
[Ste1585]
Simon Stevin. L'arithmétique. Imprimerie de Christophle Plantin, 1585.
Google Scholar ePrint
[Stra69]
Volker Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13:354–356, 1969. https://doi.org/10.1007/BF02165411.
Google Scholar ePrint
[Stru63]
Dirk J. Struik. The origin of L’Hôpital's rule. The Mathematics Teacher, 56:257–260, 1963. https://doi.org/10.5951/MT.56.4.0257.
Google Scholar ePrint
[Sud97]
Madhu Sudan. Decoding of Reed Solomon codes beyond the error-correction bound. Journal of Complexity, 13:180–193, 1997. https://doi.org/10.1006/jcom.1997.0439.
Google Scholar ePrint
[SugKHN75]
Yasuo Sugiyama, Masao Kasahara, Shigeichi Hirasawa, and Toshihiko Namekawa. A method for solving key equation for decoding Goppa codes. Information and Control, 27:87–99, 1975. https://doi.org/10.1016/S0019-9958(75)90090-X.
Google Scholar ePrint
[The20]
The Sage Developers, editor. SageMath, the Sage Mathematics Software System (Version 9.2), No publisher listed, 2020.
Google Scholar ePrint
[Til93]
Henk C. A. van Tilborg. Coding theory, a first course. No publisher listed, 1993.
Google Scholar ePrint
[War1779]
Edward Waring. Problems concerning interpolations. Philosophical Transactions of the Royal Society, 69:59–67, 1779. https://doi.org/10.1098/rstl.1779.0008.
Google Scholar ePrint
[WelS79]
Lloyd R. Welch and Robert A. Scholtz. Continued fractions and Berlekamp's algorithm. IEEE Transactions on Information Theory, 25:19–27, 1979. https://doi.org/10.1109/TIT.1979.1055987.
Google Scholar ePrint
[Win19]
Davey Winder. Warning: Google researcher drops Windows 10 zero-day security bomb. 2019.
Google Scholar ePrint
[Yan11]
Bo-Yin Yang, editor. Post-quantum cryptography—4th international workshop, PQCrypto 2011, Taipei, Taiwan, November 29–December 2, 2011, proceedings, volume 7071, Springer, 2011. https://doi.org/10.1007/978-3-642-25405-5.
Google Scholar ePrint

PDFPDF Open access

DOI: https://doi.org/10.62056/angy4fe-3
History
Submitted: 2024-01-07
Accepted: 2024-03-05
Published: 2024-04-09
How to cite

Daniel J. Bernstein, Understanding binary-Goppa decoding. IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/angy4fe-3.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.