# zbMATH — the first resource for mathematics

Wild McEliece. (English) Zbl 1290.94041
Biryukov, Alex (ed.) et al., Selected areas in cryptography. 17th international workshop, SAC 2010, Waterloo, Ontario, Canada, August 12–13, 2010. Revised selected papers. Berlin: Springer (ISBN 978-3-642-19573-0/pbk). Lecture Notes in Computer Science 6544, 143-158 (2011).
Summary: The original McEliece cryptosystem uses length-$$n$$ codes over $$\mathbb F_2$$ with dimension $$\geq n-mt$$ efficiently correcting $$t$$ errors where $$2^m \geq n$$. This paper presents a generalized cryptosystem that uses length-$$n$$ codes over small finite fields $$\mathbb F_q$$ with dimension $$\geq n-m(q-1)t$$ efficiently correcting $$\lfloor{qt/2}\rfloor$$ errors where $$q^m \geq n$$. Previously proposed cryptosystems with the same length and dimension corrected only $$\lfloor{(q-1)t/2}\rfloor$$ errors for $$q\geq 3$$. This paper also presents list-decoding algorithms that efficiently correct even more errors for the same codes over $$\mathbb F_q$$. Finally, this paper shows that the increase from $$\lfloor{(q-1)t/2}\rfloor$$ errors to more than $$\lfloor{qt/2}\rfloor$$ errors allows considerably smaller keys to achieve the same security level against all known attacks.
For the entire collection see [Zbl 1208.94008].

##### MSC:
 94A60 Cryptography 11T71 Algebraic coding theory; cryptography (number-theoretic aspects) 94B35 Decoding
##### Software:
McEliece; SageMath
Full Text:
##### References:
 [1] — (No Editor), Eleventh International Workshop on Algebraic and Combinatorial Coding Theory, Pamporovo, Bulgaria, June 16–22 (2008), http://www.moi.math.bas.bg/acct2008/acct2008.html , See [15] [2] Berger, T.P., Cayrel, P.-L., Gaborit, P., Otmani, A.: Reducing Key Length of the McEliece Cryptosystem. In: AFRICACRYPT 2009 [35], pp. 77–97 (2009), Citations in This Document: §6 · Zbl 1246.94022 · doi:10.1007/978-3-642-02384-2_6 [3] Bernstein, D.J.: Grover vs. McEliece. In: PQCrypto 2010 [36], pp. 73–80 (2010), http://cr.yp.to/papers.html#grovercode , Citations in This Document: §1 · Zbl 1284.94053 [4] Bernstein, D.J.: List Decoding for Binary Goppa Codes (2008), http://cr.yp.to/papers.html#goppalist , Citations in This Document: §5 · Zbl 1272.94095 [5] Bernstein, D.J.: Fast Multiplication and Its Applications. In: Algorithmic Number Theory [10], pp. 325–384 (2008), http://cr.yp.to/papers.html#multapps , Citations in This Document: §5 · Zbl 1208.68239 [6] Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.): Post-Quantum Cryptography. Springer, Heidelberg (2009) ISBN 978-3-540-88701-0, See [32] [7] Bernstein, D.J., Lange, T., Peters, C.: Attacking and Defending the McEliece Cryptosystem. In: PQCrypto 2008 [9], pp. 31–46 (2008), http://eprint.iacr.org/2008/318 , Citations in This Document: §1, §6, §7 · Zbl 1177.94128 [8] Boyd, C. (ed.): Advances in Cryptology – ASIACRYPT 2001, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security Held on the Gold Coast, December 9-13, 2001. LNCS, vol. 2248. Springer, Heidelberg (2001) ISBN 3-540-42987-5, See [13] · Zbl 0977.00048 [9] Buchmann, J., Ding, J. (eds.): Proceedings of Post-Quantum Cryptography, Second International Workshop, PQCrypto 2008, Cincinnati, OH, USA, October 17-19, 2008. LNCS, vol. 5299. Springer, Heidelberg (2008), See [7] · Zbl 1147.94002 [10] Buhler, J., Stevenhagen, P. (eds.): Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography. Cambridge University Press, Cambridge (2008) ISBN 978-0521808545, See [5] · Zbl 1154.11002 [11] Canteaut, A., 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. IEEE Transactions on Information Theory 44, 367–378 (1998), http://hal.inria.fr/inria-00074006/en/ , MR 98m:94043, Citations in This Document: §6 · Zbl 1053.94558 · doi:10.1109/18.651067 [12] Cohen, G.D., Wolfmann, J. (eds.): Coding Theory and Applications. LNCS, vol. 388. Springer, Heidelberg (1989), See [40] · Zbl 0676.00026 [13] Courtois, N., Finiasz, M., Sendrier, N.: How to Achieve a McEliece-Based Digital Signature Scheme. In: ASIACRYPT 2001 [8], pp. 157–174 (2001), http://hal.inria.fr/docs/00/07/25/11/PDF/RR-4118.pdf , MR 2003h:94028, Citations in This Document: §6 · Zbl 1062.94556 [14] Faugère, J.-C., Otmani, A., Perret, L., Tillich, J.-P.: Algebraic Cryptanalysis of McEliece Variants with Compact Keys. In: EUROCRYPT 2010 [18], pp. 279–298 (2010), Citations in This Document: §6, §6 · Zbl 1280.94051 · doi:10.1007/978-3-642-13190-5_14 [15] Faure, C., Minder, L.: Cryptanalysis of the McEliece Cryptosystem over Hyperelliptic Codes. In: ACCT 2008 [1], pp. 99–107 (2008), http://www.moi.math.bas.bg/acct2008/b17.pdf , Citations in This Document: §4 [16] Finiasz, M., Sendrier, N.: Security Bounds for the Design of Code-Based Cryptosystems. In: ASIACRYPT 2009 [27], pp. 88–105 (2009), http://eprint.iacr.org/2009/414 , Citations in This Document: §6, §6 · Zbl 1267.94058 [17] Gauthier Umana, V., Leander, G.: Practical Key Recovery Attacks on Two McEliece Variants (2009), http://eprint.iacr.org/2009/509 , Citations in This Document: §6 [18] Gilbert, H. (ed.): Proceedings of Advances in Cryptology – EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30-June 3, 2010. LNCS, vol. 6110. Springer, Heidelberg (2010), See [14] · Zbl 1188.94008 [19] Guruswami, V., Sudan, M.: Improved Decoding of Reed-Solomon and Algebraic-Geometry Codes. IEEE Transactions on Information Theory 45, 1757–1767 (1999), http://theory.lcs.mit.edu/ madhu/bib.html , ISSN 0018–9448, MR 2000j:94033, Citations in This Document: §5 · Zbl 0958.94036 · doi:10.1109/18.782097 [20] Isaacs, I.M., Lichtman, A.I., Passman, D.S., Sehgal, S.K., Sloane, N.J.A., Zassenhaus, H.J. (eds.): Representation Theory, Group Rings, and Coding Theory: Papers in Honor of S. D. Berman. Contemporary Mathematics, vol. 93. American Mathematical Society, Providence (1989), See [23] · Zbl 0666.00005 [21] Jacobson Jr., M.J., Rijmen, V., Safavi-Naini, R. (eds.): Selected Areas in Cryptography, 16th Annual International Workshop, SAC 2009, Calgary, Alberta, Canada, August 13-14, 2009. LNCS, vol. 5867. Springer, Heidelberg (2009), See [30] · Zbl 1177.94012 [22] Janwa, H., Moreno, O.: McEliece Public Key Cryptosystems Using Algebraic-Geometric Codes. Designs, Codes and Cryptography 3, 293–307 (1996), Citations in This Document: §1, §4 · Zbl 0859.94008 · doi:10.1023/A:1027351723034 [23] Katsman, G.L., Tsfasman, M.A.: A Remark on Algebraic Geometric Codes. In: Representation Theory, Group Rings, and Coding Theory [20], pp. 197–199, Citations in This Document: §4 · doi:10.1090/conm/093/1003354 [24] Kim, K. (ed.): Public Key Cryptography: Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptosystems (PKC 2001) Held on Cheju Island, February 13-15, 2001. LNCS, vol. 1992. Springer, Heidelberg (2001), See [25] · Zbl 0960.00080 [25] Kobara, K., Imai, H.: Semantically Secure McEliece Public-Key Cryptosystems – Conversions for McEliece PKC. In: PKC 2001 [24], pp. 19–35 (2001), MR 2003c:94027, Citations in This Document: §5, §6, §7 · Zbl 0988.94021 [26] Li, Y.X., Deng, R.H., Wang, X.M.: On the Equivalence of McEliece’s and Niederreiter’s Public-Key Cryptosystems. IEEE Transactions on Information Theory 40, 271–273 (1994), Citations in This Document: §2 · Zbl 0803.94016 · doi:10.1109/18.272496 [27] Matsui, M. (ed.): Proceedings of Advances in Cryptology – ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6-10, 2009. LNCS, vol. 5912. Springer, Heidelberg (2009), See [16] · Zbl 1177.94014 [28] McEliece, R.J.: A Public-Key Cryptosystem Based on Algebraic Coding Theory, JPL DSN Progress Report, pp. 114–116 (1978), http://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF , Citations in This Document: §1, §2 [29] Minder, L.: Cryptography Based on Error-Correcting Codes, Ph.D. Thesis, EPFL, PhD thesis 3846 (2007), Citations in This Document: §4 [30] Misoczki, R., Barreto, P.S.L.M.: Compact McEliece Keys from Goppa Codes. In: SAC 2009 [21], pp. 376–392 (2009), Citations in This Document: §1, §6 · Zbl 1267.94086 · doi:10.1007/978-3-642-05445-7_24 [31] Niederreiter, H.: Knapsack-Type Cryptosystems and Algebraic Coding Theory. Problems of Control and Information Theory 15, 159–166 (1986), Citations in This Document: §1, §2 · Zbl 0611.94007 [32] Overbeck, R., Sendrier, N.: Code-Based Cryptography. In: Post-Quantum Cryptography [6], pp. 95–145 (2009), Citations in This Document: §1, §7 · Zbl 1161.81329 · doi:10.1007/978-3-540-88702-7_4 [33] Patterson, N.J.: The Algebraic Decoding of Goppa Codes. IEEE Transactions on Information Theory 21, 203–207 (1975), Citations in This Document: §1, §5 · Zbl 0301.94016 · doi:10.1109/TIT.1975.1055350 [34] Peters, C.: Information-Set Decoding for Linear Codes over F q . In: PQCrypto 2010 [36], pp. 81–94 (2010), http://eprint.iacr.org/2009/589 , Citations in This Document: §1, §4, §6, §6, §7 · Zbl 1284.94101 [35] Preneel, B. (ed.): Progress in Cryptology — AFRICACRYPT 2009, Second International Conference on Cryptology in Africa, Gammarth, Tunisia, June 21-25, 2009. LNCS, vol. 5580. Springer, Heidelberg (2009), See [2] · Zbl 1165.94004 [36] Sendrier, N. (ed.): Post-Quantum Cryptography, Third International Workshop, PQCrypto, Darmstadt, Germany, May 25-28, 2010. LNCS, vol. 6061. Springer, Heidelberg (2010), See [3], [34] · Zbl 1189.94010 [37] Sendrier, N.: Finding the Permutation between Equivalent Linear Codes: The Support Splitting Algorithm. IEEE Transactions on Information Theory 46, 1193–1203 (2000), http://hal.inria.fr/docs/00/07/30/37/PDF/RR-3637.pdf , MR 2001e:94017, Citations in This Document: §6 · Zbl 1002.94037 · doi:10.1109/18.850662 [38] Sidelnikov, V.M., Shestakov, S.O.: On an Encoding System Constructed on the Basis of Generalized Reed-Solomon Codes. Discrete Mathematics and Applications 2, 439–444 (1992), MR 94f:94009, Citations in This Document: §1, §2 [39] Stein, W. (ed.): Sage Mathematics Software (Version 4.4.3). The Sage Group (2010), http://www.sagemath.org , Citations in This Document: §5 [40] Stern, J.: A Method for Finding Codewords of Small Weight. In: [12], pp. 106–113 (1989), Citations in This Document: §6 · Zbl 0678.94006 · doi:10.1007/BFb0019850 [41] Sugiyama, Y., Kasahara, M., Hirasawa, S., Namekawa, T.: Further Results on Goppa Codes and Their Applications to Constructing Effcient Binary Codes. IEEE Transactions on Information Theory 22, 518–526 (1976), Citations in This Document: §1, §4, §4, §4 · Zbl 0356.94056 · doi:10.1109/TIT.1976.1055610 [42] Wagner, D.: A Generalized Birthday Problem (Extended Abstract). In: [45], pp. 288–303 (2002); See Also Newer Version [43], http://www.cs.berkeley.edu/ daw/papers/genbday.html [43] Wagner, D.: A Generalized Birthday Problem (Extended Abstract) (Long Version) (2002); See Also Older Version [42], http://www.cs.berkeley.edu/ daw/papers/genbday.html , Citations in This Document: §6 [44] Wirtz, M.: On the Parameters of Goppa Codes. IEEE Transactions on Information Theory 34, 1341–1343 (1988), Citations in This Document: §4 · Zbl 0665.94013 · doi:10.1109/18.21264 [45] Yung, M. (ed.): Proceedings of Advances in Cryptology – CRYPTO 2002: 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 2002. LNCS, vol. 2442. Springer, Heidelberg (2002) ISBN 3-540-44050-X, See [42] · Zbl 0997.00039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.