A Distinguisher for High Rate McEliece Cryptosystems

Article English OPEN
Faugère, Jean-Charles; Gauthier-Umana, Valérie; Otmani, Ayoub; Perret, Ludovic; Tillich, Jean-Pierre;
  • Publisher: Institute of Electrical and Electronics Engineers
  • Related identifiers: doi: 10.1109/TIT.2013.2272036
  • Subject: [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] | [ INFO.INFO-CR ] Computer Science [cs]/Cryptography and Security [cs.CR]
    arxiv: Computer Science::Cryptography and Security

International audience; The Goppa Code Distinguishing (GD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. The hardness of this problem is an assumption to prove the security of code-based cryptographic primitives such as McEliece's c... View more
  • References (43)
    43 references, page 1 of 5

    [1] N. T. Courtois, M. Finiasz, and N. Sendrier, “How to achieve a McEliece-based digital signature scheme,” in ASIACRYPT, vol. 2248, 2001, pp. 157-174.

    [2] R. J. McEliece, A Public-Key System Based on Algebraic Coding Theory. Jet Propulsion Lab, 1978, pp. 114-116, dSN Progress Report 44.

    [3] P. J. Lee and E. F. Brickell, “An observation on the security of McEliece's public-key cryptosystem,” in Advances in Cryptology - EUROCRYPT'88, ser. Lecture Notes in Computer Science, vol. 330/1988. Springer, 1988, pp. 275-280.

    [4] J. S. Leon, “A probabilistic algorithm for computing minimum weights of large error-correcting codes,” IEEE Transactions on Information Theory, vol. 34, no. 5, pp. 1354-1359, 1988.

    [5] J. Stern, “A method for finding codewords of small weight,” in Coding Theory and Applications, ser. Lecture Notes in Computer Science, G. D. Cohen and J. Wolfmann, Eds., vol. 388. Springer, 1988, pp. 106-113.

    [6] A. Canteaut and F. Chabaud, “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, vol. 44, no. 1, pp. 367-378, 1998.

    [7] D. J. Bernstein, T. Lange, and C. Peters, “Attacking and defending the McEliece cryptosystem,” in PQCrypto, ser. LNCS, vol. 5299, 2008, pp. 31-46.

    [8] --, “Smaller decoding exponents: Ball-collision decoding,” in CRYPTO, ser. Lecture Notes in Computer Science, P. Rogaway, Ed., vol. 6841. Springer, 2011, pp. 743-760.

    [9] A. May, A. Meurer, and E. Thomae, “Decoding random linear codes in O˜(20.054n),” in ASIACRYPT, ser. Lecture Notes in Computer Science, D. H. Lee and X. Wang, Eds., vol. 7073. Springer, 2011, pp. 107-124.

    [10] A. Becker, A. Joux, A. May, and A. Meurer, “Decoding random binary linear codes in 2n/20: How 1 + 1 = 0 improves information set decoding,” in EUROCRYPT, ser. Lecture Notes in Computer Science, D. Pointcheval and T. Johansson, Eds., vol. 7237. Springer, 2012, pp. 520-536.

  • Metrics