. Lm and . Yi, eH pk où e est uniformément distribué dans Sw tandis que si r R Lm, Yi est uniformément distribuée, Nous avons

, Nous donnons dans la table 9.2 nos résultats numériques pour retrouver des mots de poids w dec dans les instances du problème RSL avec les paramètres considérés dans

, Ces résultats ont été obtenus avec Magma et l'utilisation d'un processeur Intel Core i5, cadencé à 1.6 GHz à un seul coeur et avec 8 Go de RAM. Dans notre implémentation nous vérifions que les mots de poids w dec révèlent bien l'espace F généré comme étant le secret

, Éviter l'attaque

, Bien que notre attaque casse les paramètres proposés dans [Gab+17b] nous allons ici montrer qu'il existe en principe un ensemble de paramètres l'évitant. Commençons tout d'abord par rappeler qu'il existe

, Nombre attendu de solutions au problème du décodage générique en métrique rang pour m

]. .. Ibe-de-gpv-[gpv08a,

, Exposant asymptotique ? P range de la complexité de l'algorithme de Prange en base 2 pour q " 2 et R " 1{2 en fonction de ? " w{n, p.79

. .. , Exposant asymptotique ? P range de la complexité de l'algorithme de Prange en base 2 pour q " 2 et w{n " ?´en fonction de R, p.80

, Algorithme de Wagner de profondeur a " 2 appliqué au décodage, p.84

, Exposant asymptotique ? W agner en base 2 de la complexité de l'algorithme de Wagner pour trouver une solution du problème de décodage avec q " 2 et R " 0.7 en fonction de ? " w{n fixé

, Exposants asymptotiques ? W agner et ? W agnerLisse de la complexité de l'algorithme en base 2 des algorithmes de Wagner non lissé et lissé pour trouver une solution du problème de décodage avec q " 2 et R " 0.7 en fonction de ? " w{n fixé

, Exposants asymptotiques ? P range et ? Dumer de la complexité de l'algorithme de Prange et Dumer pour R " 1{2 en fonction de ? " w{n fixé

. .. , Exposants asymptotiques ? P range et ? Dumer de la complexité de l'algorithme de Prange et Dumer pour w{n " ?´en fonction de R, p.91

V. Le-même, ) écrit par découpage en deux et (2) utilisant les représentations

, Dumer et BJMM pour R " 1{2 en fonction de ? " w{n fixé, Exposants asymptotiques ? P range , ? Dumer et ? BJM M de la complexité des algorithmes de Prange

, Exposants asymptotiques ? P range , ? Dumer et ? BJM M de la complexité des algorithmes de Prange, Dumer et BJMM pour w{n " ?´en fonction de R. 96

, Exposants asymptotiques de la complexité de l'algorithme de Prange pour R " 1{2 en fonction de ? pour q " 2 et q " 3

, Exposant asymptotique de la complexité de l'algorithme de Prange pour R " 1{5 en fonction de ? " w{n et avec q " 3

, Exposant asymptotique l'algorithme de Prange pour q " 3 et w{n " ?`en fonction de R

, Distributions pq 2 ps, tqq s et pq unif 2 ps, tqq s avec les distributions internes D t U choisies comme Lappt´3 2 m max cible ptq, 6, maxp0, k U`t´n {2q, tq pour les paramètres n, p.206, 2000.

, Une figure représentant J , I et I 1 en fonction de la forme d'un mot de code dans V 1

. Bibliographie,

A. Carlos, G. Philippe, and S. Julien, A new zero-knowledge code based identification scheme with reduced communication, Proc. IEEE Inf. Theory Workshop-ITW, pp.648-652, 2011.

A. Michael, More on Average Case vs Approximation Complexity, Computational Complexity, vol.20, pp.755-786, 2011.

A. Carlos, . Melchor, B. Olivier, D. Jean-christophe, P. G. Gilles et al., Efficient Encryption From Random Quasi-Cyclic Codes, IEEE Trans. Inform. Theory, vol.64, pp.3927-3943, 2018.

N. Aragon, P. Barreto, S. Bettaieb, B. Loic, O. Blazy et al., BIKE. NIST Round 1 submission for Post-Quantum Cryptography, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01671903

A. Nicolas, G. Philippe, A. Hauteville, and T. Jean-pierre, Improvement of Generic Attacks on the Rank Syndrome Decoding Problem, 2017.

A. Nicolas, G. Philippe, H. Adrien, R. Oliver, and Z. Gilles, RankSign -a signature proposal for the NIST's call-. first round submission to the NIST post-quantum cryptography call. NIST Round 1 submission for Post-Quantum Cryptography, 2017.

A. Nicolas, B. Olivier, G. Philippe, A. Hauteville, and Z. Gilles, Durandal : a rank metric based signature scheme, IACR Cryptology ePrint Archive, 2018.

A. Nicolas, B. Olivier, G. Philippe, A. Hauteville, and Z. Gilles, Durandal : a rank metric based signature scheme, Advances in Cryptology -EUROCRYPT 2019 -38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp.728-758, 2019.

A. Nicolas, B. Olivier, D. Jean-christophe, P. Ga-borit, A. H. Olivier et al.,

, Second round submission to the NIST post-quantum cryptography call. NIST Round 2 submission for Post-Quantum Cryptography, 2019.

A. Frank, A. Kunal, B. Ryan, D. Bacon, C. Joseph et al., Quantum supremacy using a programmable superconducting processor, Nature, vol.574, pp.505-510, 2019.

A. Erdal, Channel polarization : a method for constructing capacityachieving codes for symmetric binary-input memoryless channels, IEEE Trans. Inform. Theory, vol.55, pp.3051-3073, 2009.

A. Daniel, F. Matthieu, G. Philippe, M. Stéphane, and S. Nicolas, SHA-3 proposal : FSB, 2008.

B. László, On Lovász' lattice reduction and the nearest lattice point problem, In : Combinatorica 6, vol.1, pp.1-13, 1986.

B. Marco, B. Marco, C. Franco, J. R. Davide, and S. , Using LDGM Codes and Sparse Syndromes to Achieve Digital Signatures, Post-Quantum Cryptography 2013. T. 7932, pp.1-15, 2013.

B. Boaz, D. Yevgeniy, K. Hugo, P. Olivier, P. Krzysztof et al., Leftover Hash Lemma, Revisited, Advances in Cryptology -CRYPTO 2011 -31st Annual Cryptology Conference, pp.1-20, 2011.

B. Magali, C. Julia, D. Vlad, O. Ayoub, and T. Jean-pierre, Cryptanalysis of the McEliece Public Key Cryptosystem Based on Polar Codes, Post-Quantum Cryptography 2016, pp.118-143, 2016.

B. Marco and C. Franco, Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC Codes, Proc. IEEE Int. Symposium Inf. Theory -ISIT, pp.2591-2595, 2007.

A. Becker, C. Jean-sébastien, and J. Antoine, Improved Generic Algorithms for Hard Knapsacks, Advances in Cryptology -EUROCRYPT 2011 -30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp.364-385, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00664332

A. Becker, J. Antoine, M. Alexander, and M. Alexander, Decoding Random Binary Linear Codes in 2 n{20 : How 1`1 " 0 Improves Information Set Decoding, Advances in Cryptology -EUROCRYPT 2012, 2012.

B. Emanuele, C. Florian, G. Philippe, M. Marc, and M. Víctor, Improved Veron Identification and Signature Schemes in the Rank Metric, Proc. IEEE Int. Symposium Inf. Theory -ISIT 2019. T. abs/1903.10212, pp.1872-1876, 2019.

P. Thierry, . Berger, C. Pierre-louis, P. Gaborit, and O. Ayoub, Reducing Key Length of the McEliece Cryptosystem, Progress in Cryptology -AFRICACRYPT 2009. Sous la dir. de Bart PRENEEL. T. 5580, pp.77-97, 2009.

B. Slim, B. Loïc, G. Philippe, and M. Etienne, Preventing Timing Attacks Against RQC Using Constant Time Decoding of Gabidulin Codes, Post-Quantum Cryptography 2019. Sous la dir. de Jintai DING et Rainer STEINWANDT. T. 11505, pp.371-386, 2019.

D. Boneh, K. Matthew, and . Franklin, Identity-based encryption from the Weil pairing, Advances in Cryptology -CRYPTO 2001. T. 2139, pp.213-229, 2001.

J. F. Buss, G. S. Frandsen, and J. O. Shallit, The Computational Complexity of Some Problems of Linear Algebra, J. Comput. System Sci, vol.58, issue.3, pp.572-596, 1999.

P. Thierry, C. Berger, G. Thiécoumba, J. Belo, and K. , A NP-Complete Problem in Coding Theory with Application to Code Based Cryptography, Codes, Cryptology and Information Security -Second International Conference, C2SI 2017, pp.230-237, 2017.

B. Leif and M. Alexander, Optimizing BJMM with Nearest Neighbors : Full Decoding in 2 2{21n and McEliece Security, WCC Workshop on Coding and Cryptography, 2017.

B. Leif and M. Alexander, Decoding Linear Codes with High Error Rate and Its Impact for LPN Security, Post-Quantum Cryptography 2018. Sous la dir. de Tanja LANGE et Rainer STEINWANDT. T. 10786. LNCS. Fort, pp.25-46, 2018.

S. L. Paulo, R. Barreto, . Misoczki, A. Marcos, and . Simplicio, Onetime signature scheme from syndrome decoding over generic error-correcting codes, Journal of Systems and Software, vol.84, pp.198-204, 2011.

B. Elwyn, M. Robert, and . Henk-van-tilborg, On the inherent intractability of certain coding problems, IEEE Trans. Inform. Theory, vol.24, issue.3, pp.384-386, 1978.

B. Mihir and R. Phillip, Random Oracles are Practical : A Paradigm for Designing Efficient Protocols, CCS '93, Proceedings of the 1st ACM Conference on Computer and Communications Security, pp.62-73, 1993.

B. Mihir and R. Phillip, The Exact Security of Digital Signatures-How to Sign with RSA and Rabin, Advances in Cryptology -EUROCRYPT '96. T. 1070, pp.399-416, 1996.

B. Rémi, C. André, D. Thomas, and L. Et-matthieu, , 2019.

C. Mark, F. Gregory, and G. Zvi, Solving dense subsetsum problems by using analytical number theory, In : J. Complexity, vol.5, pp.271-282, 1989.

C. Nicolas, F. Matthieu, and S. Nicolas, How to Achieve a McEliece-based Digital Signature Scheme, Advances in Cryptology -ASIACRYPT 2001. T. 2248, pp.157-174, 2001.

T. John, . Coffey, M. Rodney, and . Goodman, The complexity of information set decoding, IEEE Transactions on Information Theory, vol.36, pp.1031-1037, 1990.

C. Julia, Étude de cryptosystèmes à clé publique basés sur les codes MDPC quasi-cycliques, 2017.

C. Jean-sebastien and J. Antoine, Cryptanalysis of a provably secure cryptographic hash function. IACR Cryptology ePrint Archive, 2004.

C. Clifford, An identity based encryption scheme based on quadratic residues, 8th IMA International Conference on Cryptography and Coding, pp.360-363, 2001.

C. Jean-sébastien, Optimal Security Proofs for PSS and Other Signature Schemes, Advances in Cryptology -EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, pp.272-287, 2002.

C. Alain, G. Philippe, G. Valérie, O. Ayoub, and T. Jean-pierre, Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes, Des. Codes Cryptogr, vol.73, pp.641-666, 2014.

C. Nicolas, Efficient zero-knowledge authentication based on a linear algebra problem MinRank, Advances in Cryptology -ASIACRYPT 2001. T. 2248, pp.402-421, 2001.

C. Alain, Introduction to Coding Theory, 2019.

C. Pierre-louis, O. Ayoub, and V. Damien, On Kabatianskii-Krouk-Smeets Signatures, Arithmetic of Finite Fields -WAIFI 2007. T. 4547, pp.237-251, 2007.

C. Rodolfo and S. Nicolas, Analysis of Information Set Decoding for a Sub-linear Error Weight, Post-Quantum Cryptography 2016, pp.144-161, 2016.

C. Julia and S. Nicolas, Worst case QC-MDPC decoder for McEliece cryptosystem, IEEE Conference, pp.1366-1370, 2016.

C. Rodolfo and T. Jean-pierre, Speeding up decoding a code with a non-trivial automorphism group up to an exponential factor, Proc. IEEE Int. Symposium Inf. Theory -ISIT, pp.1927-1931, 2019.

M. Thomas, J. A. Cover, and . Thomas, Information Theory, 1991.
URL : https://hal.archives-ouvertes.fr/hal-00756546

D. Léonard, Sécurité de protocoles cryptographiques fondés sur les codes correcteurs d'erreurs, 2010.

D. Nico and G. Sanjam, From Selective IBE to Full IBE and Selective HIBE, Theory of Cryptography -15th International Conference, pp.372-408, 2017.

D. Nico and G. Sanjam, Identity-Based Encryption from the Diffie-Hellman Assumption, Advances in Cryptology -CRYPTO 2017. Sous la dir. de Jonathan KATZ et Hovav SHACHAM. T. 10401. LNCS. Santa, pp.537-569, 2017.

D. Whitfield and H. Martin, New directions in cryptography, IEEE transactions on Information Theory, vol.22, pp.644-654, 1976.

T. Debris-alazard, N. Sendrier, and J. Tillich, The problem with the SURF scheme, 2017.

D. Thomas, N. Sendrier, and T. Jean-pierre, SURF : a new code-based signature scheme, 2017.

D. Thomas, N. Sendrier, and T. Jean-pierre, The problem with the SURF scheme, 2017.

D. Thomas, N. Sendrier, and T. Jean-pierre, Wave : A New Family of Trapdoor One-Way Preimage Sampleable Functions Based on Codes, Advances in Cryptology -ASIACRYPT 2019, 2019.

D. Thomas, N. Sendrier, and T. Jean-pierre, Wave : A New Family of Trapdoor One-Way Preimage Sampleable Functions Based on Codes, Cryptology ePrint Archive, 2018.

D. Thomas and T. Jean-pierre, Statistical decoding, Proc. IEEE Int. Symposium Inf. Theory -ISIT 2017, pp.1798-1802, 2017.

T. Debris-alazard and J. Tillich, Two attacks on rank metric codebased schemes : RankSign and an Identity-Based-Encryption scheme, 2018.

D. Thomas and T. Jean-pierre, Two attacks on rank metric code-based schemes : RankSign and an Identity-Based-Encryption scheme. preprint. IACR Cryptology ePrint Archive, 2018.

D. Thomas and T. Jean-pierre, Two attacks on rank metric code-based schemes : RankSign and an Identity-Based-Encryption scheme, Advances in Cryptology -ASIACRYPT 2018. T. 11272, pp.62-92, 2018.

. Il'ya-dumer, Two decoding algorithms for linear codes, Probl. Inf. Transm, vol.25, pp.17-23, 1989.

D. Ilya, On minimum distance decoding of linear codes, Proc. 5th Joint Soviet-Swedish Int. Workshop Inform. Theory. Moscow, pp.50-52, 1991.

D. Nico, G. Sanjam, H. Mohammad, and M. Daniel, New Constructions of Identity-Based and Key-Dependent Message Secure Encryption Schemes, Public-Key Cryptography -PKC 2018. Sous la dir. de Michel ABDALLA et Ricardo DAHAB. T. 10769, pp.3-31, 2018.

N. M. Döttling, Cryptography based on the Hardness of Decoding, 2014.

E. Peter, oding for Noisy Channels, IRE conv. Rec, vol.3, p.37, 1955.

F. Tomás, H. Viliam, S. Paul, Z. Pavol, G. Qian et al., A Reaction Attack on the QC-LDPC McEliece Cryptosystem, Post-Quantum Cryptography -8th International Workshop, pp.51-68, 2017.

J. Valérie, G. Ayoub, O. Ludovic, P. Jean-pierre, and T. , A Distinguisher for High Rate McEliece Cryptosystems. IACR Cryptology ePrint Archive

J. Ayoub, O. Ludovic, P. Jean-pierre, and T. , Algebraic Cryptanalysis of McEliece Variants with Compact Keys, Advances in Cryptology -EUROCRYPT 2010. T. 6110, pp.279-298, 2010.

.. Je, V. Faugère, A. Gauthier, L. Otmani, J. Perret et al., A Distinguisher for High Rate McEliece Cryptosystems, 2013.

J. Faugère, Résolution des systèmes polynômiaux en utilisant les bases de Grobner, 2015.

F. Matthieu, Parallel-CFS -Strengthening the CFS McEliece-Based Signature Scheme, Selected Areas in Cryptography 17th International Workshop, pp.159-170, 2010.

P. C. Marc, . Fossorier, K. Kazukuni, and I. Hideki, Modeling bit flipping decoding based on nonorthogonal check sums with application to iterative decoding attack of McEliece cryptosystem, IEEE Trans. Inform. Theory, vol.53, pp.402-411, 2007.

J. Françoise, L. Ludovic, and P. , Cryptanalysis of Minrank, Advances in Cryptology -CRYPTO 2008. Sous la dir. de David WAGNER. T. 5157, pp.280-296, 2008.

F. Pierre-alain, H. Jeffrey, K. Paul, L. Vadim, P. Thomas et al., Falcon : Fast-Fourier Lattice-based Compact Signatures over NTRU. First round submission to the NIST post-quantum cryptography call. NIST Round 1 submission for Post-Quantum Cryptography, 2017.

F. Abraham and P. Bartosz, Solving Medium-Density Subset Sum Problems in Expected Polynomial Time, STACS 2005, 22nd Annual Symposium on Theoretical Aspects of Computer Science, pp.305-314, 2005.

F. Matthieu and S. Nicolas, Security Bounds for the Design of Code-based Cryptosystems, Advances in Cryptology -ASIACRYPT 2009. Sous la dir. de M. MATSUI. T. 5912, pp.88-105, 2009.

F. Amos and S. Adi, How to Prove Yourself : Practical Solutions to Identification and Signature Problems, Advances in Cryptology -CRYPTO '86. Sous la dir. d'A.M. ODLYZKO. T. 263, pp.186-194, 1987.

J. Fischer and J. Stern, An efficient pseudo-random generator provably as secure as syndrome decoding, Advances in Cryptology -EUROCRYPT'96. Sous la dir. d'Ueli MAURER. T. 1070, pp.245-255, 1996.

J. Mohab, S. El-din, and S. Pierre-jean, Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology, International Symposium on Symbolic and Algebraic Computation, pp.257-264, 2010.

F. Kazuhide, P. Sarathi, R. Rui, X. U. Shinsaku, K. Tsuyoshi et al., Random Code-based Signature Scheme). first round submission to the NIST post-quantum cryptography call. NIST Round 1 submission for Post-Quantum Cryptography, 2017.

G. Philippe, M. Gaétan, R. Olivier, and Z. Gilles, Low Rank Parity Check codes and their application to cryptography, Proceedings of the Workshop on Coding and Cryptography WCC'2013, 2013.

P. Gaborit, O. Ruatta, J. Schrek, and G. Zémor, RankSign : An Efficient Signature Algorithm Based on the Rank Metric, Post-Quantum Cryptography, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01261425

G. Philippe, R. Olivier, S. Julien, and Z. Gilles, Rank-Sign : An Efficient Signature Algorithm Based on the Rank Metric, Post-Quantum Cryptography 2014. T. 8772, pp.88-107, 2014.

G. Philippe, H. Adrien, D. Hieu, P. Jean-pierre, and T. , Identity-based Encryption from Rank Metric. IACR Cryptology ePrint Archive

P. Gaborit, A. Hauteville, D. H. Phan, and J. Tillich, Identity-based Encryption from Rank Metric, Advances in Cryptology -CRYPTO, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01589463

G. Philippe, H. Adrien, D. Hieu, P. Jean-pierre, and T. , Identity-based Encryption from Rank Metric, Advances in Cryptology -CRYPTO2017. T. 10403. LNCS, pp.194-226, 2017.

G. Philippe, Shorter keys for code based cryptography, Proceedings of the 2005 International Workshop on Coding and Cryptography (WCC 2005), pp.81-91, 2005.

E. Mukhamedovich and G. , Theory of codes with maximum rank distance, Problemy Peredachi Informatsii, vol.21, pp.3-16, 1985.

R. G. Gallager, Low Density Parity Check Codes. Cambridge, Massachusetts, 1963.

G. Philippe, A. Hauteville, and T. Jean-pierre, RankSynd a PRNG Based on Rank Metric, Post-Quantum Cryptography, pp.18-28, 2016.

C. Thiécoumba, G. , J. Belo, K. Et-shoichi, and H. , Generalization of BJMM-ISD Using May-Ozerov Nearest Neighbor Algorithm over an Arbitrary Finite Field \mathbb F_q, Codes, Cryptology and Information Security -Second International Conference, C2SI 2017, pp.96-109, 2017.

G. Danilo, S. Simona, J. Håkon, and B. Sergey, McEliece in the world of Escher. IACR Cryptology ePrint Archive, 2014.

G. Shafi and M. Daniele, Complexity of Lattice Problems : A Cryptographic Perspective. T. 671. Kluwer International Series in Engineering and Computer Science, 2002.

G. Zvi and M. Oded, An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem, In : SIAM J. Comput, vol.20, pp.1157-1189, 1991.

G. Oded, Basic Techniques, vol.1, pp.0-521, 2001.

E. M. Gabidulin, A. V. Paramonov, and O. V. Tretjakov, Ideals over a non-commutative ring and their applications to cryptography, Advances in Cryptology -EUROCRYPT'91, vol.547, pp.482-489, 1991.

C. Gentry, C. Peikert, and V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, 2008.

G. Craig, P. Chris, and V. Vinod, Trapdoors for hard lattices and new cryptographic constructions, Proceedings of the fortieth annual ACM symposium on Theory of computing, pp.197-206, 2008.

G. Oded, R. Ronitt, and S. Madhu, Learning Polynomials with Queries : The Highly Noisy Case, In : SIAM J. Discrete Math, vol.13, pp.535-570, 2000.

G. Philippe, R. Olivier, and S. Julien, On the complexity of the Rank Syndrome Decoding problem, 2013.

G. Philippe, R. Olivier, and S. Julien, On the Complexity of the Rank Syndrome Decoding Problem, IEEE Trans. Information Theory, vol.62, pp.1006-1019, 2016.

G. Philippe and S. Julien, Efficient code-based one-time signature from automorphism groups with syndrome compatibility, Proc. IEEE Int. Symposium Inf. Theory -ISIT 2012, pp.1982-1986, 2012.

G. Philippe and Z. Gilles, On the hardness of the decoding and the minimum distance problems for rank codes, IEEE Trans. Information Theory, vol.62, issue.12, pp.7245-7252, 2016.

H. Shoichi, May-Ozerov Algorithm for Nearest-Neighbor Problem over F q and Its Application to Information Set Decoding, Innovative Security Solutions for Information Technology and Communications -9th International Conference, SECITC 2016, pp.115-126, 2016.

H. Nicholas and J. Antoine, New generic algorithms for hard knapsacks, Advances in Cryptology -EUROCRYPT 2010. Sous la dir. d'Henri GILBERT. T. 6110. LNCS. Sringer, 2010.

H. Jeffrey, H. Joseph, and . Silverman, NTRU : A Ring-Based Public Key Cryptosystem, Algorithmic Number Theory, Third International Symposium, pp.267-288, 1998.

A. Huelsing, D. J. Bernstein, P. Lorenz, and L. Tanja, Official NIST comments made for RaCoSS. Official NIST comments made for RaCoSS, 2018.

I. Carmelo, K. Karan, R. Nicole, J. Rosen-thal, and W. Violetta, Generalization of the Ball-Collision Algorithm, 2018.

E. H. Mourad, . Ismail, and S. Plamen, Strong asymptotics for Krawtchouk polynomials, Journal of Computational and Applied Mathematics, pp.121-144, 1998.

A. Al and J. , A statistical decoding algorithm for general linear block codes, Cryptography and coding. Proceedings of the 8 th IMA International Conference. Sous la dir. de Bahram HONARY. T. 2260, pp.1-8, 2001.

J. Antoine, A One Round Protocol for Tripartite Diffie-Hellman, Algorithmic Number Theory, 4th International Symposium, pp.385-394, 2000.

J. Richard, Quantum factoring, discrete logarithms, and the hidden subgroup problem, Computing in Science and Engineering, vol.3, pp.34-43, 2001.

K. Gregory, K. Evgenii, and S. Sergei, Error Correcting Coding and Security for Data Networks : Analysis of the Superchannel Concept, 2005.

K. Gregory, K. Evgenii, . J. Ben, and . Smeets, A Digital Signature Scheme Based on Random Error-Correcting Codes, IMA Int. Conf. T. 1355, pp.161-167, 1997.

P. N. Klein, Finding the closest lattice vector when it's unusually close, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp.937-941, 2000.

K. Aviad and S. Adi, Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization, Advances in Cryptology -CRYPTO'99. T. 1666. LNCS, pp.19-30, 1999.

J. Pil, E. F. Lee, and . Brickell, An Observation on the Security of McEliece's Public-Key Cryptosystem, Advances in Cryptology -EUROCRYPT'88. T. 330, pp.275-280, 1988.

L. Wijik, K. Young-sik, Y. Lee, and N. O. Jong-seon, Post quantum signature scheme based on modified Reed-Muller code pqsigRM. first round submission to the NIST post-quantum cryptography call. NIST Round 1 submission for Post-Quantum Cryptography, 2017.

L. Matthieu, Permutation decoding : Towards an approach using algebraic properties of the ?-subcode, WCC 2011. Sous la dir. de Daniel AUGOT et Anne CANTEAUT, pp.193-202, 2011.

L. Jeffrey, A probabilistic algorithm for computing minimum weights of large error-correcting codes, IEEE Trans. Inform. Theory, vol.34, pp.1354-1359, 1988.

L. Pierre, Properties of codes in rank metric, 2006.

L. Vadim, On Random High Density Subset Sums, Electronic Colloquium on Computational Complexity (ECCC), vol.1, p.7, 2005.

V. Lyubashevsky, Fiat-Shamir with aborts : Applications to lattice and factoring-based signatures, 2009.

L. Vadim, Fiat-Shamir with aborts : Applications to lattice and factoring-based signatures, International Conference on the Theory and Application of Cryptology and Information Security, pp.598-616, 2009.

L. Vadim, Lattice signatures without trapdoors, Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp.738-755, 2012.

M. Rafael and P. Barreto, Compact McEliece Keys from Goppa Codes, Selected Areas in Cryptography, 2009.

R. J. Mceliece, A Public-Key System Based on Algebraic Coding Theory, Jet Propulsion Lab, pp.114-116, 1978.

M. Alexander, A Coding-Theoretic Approach to Cryptanalysis, 2017.

M. Rafael, T. Jean-pierre, N. Sendrier, S. L. Paulo, . Barreto et al., New McEliece Variants from Moderate Density Parity-Check Codes, 2012.

M. Rafael, T. Jean-pierre, N. Sendrier, S. L. Paulo, and . Barreto, MDPC-McEliece : New McEliece variants from Moderate Density Parity-Check codes, Proc. IEEE Int. Symposium Inf. Theory -ISIT, pp.2069-2073, 2013.

M. Alexander, M. Alexander, and T. Enrico, Decoding random linear codes in Op2 0.054n q, Advances in Cryptology -ASIACRYPT 2011. Sous la dir. de Dong Hoon LEE et Xiaoyun WANG. T. 7073, pp.107-124, 2011.

M. Alexander and O. Ilya, On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes, Advances in Cryptology -EUROCRYPT 2015. Sous la dir. d'E. OSWALD et M. FISCHLIN. T. 9056, pp.203-228, 2015.

D. Moody, A. Ray, and . Perlner, Vulnerabilities of "McEliece in the World of Escher, Post-Quantum Cryptography 2016, 2016.

M. Daniele and R. Oded, Lattice-based cryptography, Postquantum cryptography, pp.147-191, 2009.

L. Minder and A. Sinclair, The extended k-tree algorithm, Proceedings of SODA 2009. Sous la dir, pp.586-595, 2009.

J. Florence, . Macwilliams, J. A. Neil, and . Sloane, The Theory of Error-Correcting Codes. Fifth, 1986.

N. Harald, A Public-Key Cryptosystem based on Shift Register Sequences, Advances in Cryptology -EUROCRYPT 1985. T. 219, pp.35-39, 1985.

N. Harald, Knapsack-type cryptosystems and algebraic coding theory, Problems of Control and Information Theory, vol.15, pp.159-166, 1986.

A. V. Ourivski and J. Thomas, New Technique for Decoding Codes in the Rank Metric and Its Cryptography Applications, Problems of Information Transmission, vol.38, pp.32-9460, 2002.

O. Raphael, S. Nicolas, J. Daniel, J. Bernstein, . Buchmann et al., Code-based cryptography". In : Post-quantum cryptography. Sous la dir, pp.95-145, 2009.

O. Ayoub and T. Jean-pierre, An Efficient Attack on All Concrete KKS Proposals, Post-Quantum Cryptography 2011. T. 7071, pp.98-116, 2011.

O. Ayoub and T. Jean-pierre, On the Design of Code-Based Signatures, Code-based Cryptography Workshop (CBC 2012, 2012.

O. Ayoub, T. Jean-pierre, and D. Léonard, Cryptanalysis of Two McEliece Cryptosystems Based on Quasi-Cyclic Codes, In : Special Issues of Mathematics in Computer Science, vol.3, issue.2, pp.129-140, 2010.

O. Raphael, A New Structural Attack for GPT and Variants, Mycrypt. T. 3715, pp.50-63, 2005.

O. Raphael, Information security and privacy : 11 th Australasian conference, LNCS, pp.283-294, 2006.

C. Peters, Information-Set Decoding for Linear Codes over F q, Post-Quantum Cryptography 2010. T. 6061, pp.81-94, 2010.

P. David, Provable Security in the Computational Model, 2019.

P. Eugene, The use of information sets in decoding cyclic codes, IRE Transactions on Information Theory, vol.8, pp.5-9, 1962.

P. Chris, R. Oded, and S. Noah, Pseudorandomness of ring-LWE for any ring and modulus, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp.461-473, 2017.

P. Aurélie and T. Jean-pierre, An Efficient Attack on a Code-Based Signature Scheme, Post-Quantum Cryptography 2016. T. 9606, pp.86-103, 2016.

R. Oded, On lattices, learning with errors, random linear codes, and cryptography, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp.84-93, 2005.

R. L. Rivest, A. Shamir, M. Leonard, and . Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Commun. ACM, vol.21, pp.120-126, 1978.

, Communication personnelle avec Damien Stehlé

C. Schnorr, Efficient signature generation by smart cards, Journal of cryptology, vol.4, pp.161-174, 1991.

S. Nicolas, Cryptosystèmes à clé publique basés sur les codes correcteurs d'erreurs, Mémoire d'habilitation à diriger des recherches, 2002.

S. Nicolas, Decoding One Out of Many, Post-Quantum Cryptography 2011. T. 7071. LNCS, pp.51-67, 2011.

S. Nicolas, The tightness of security reductions in code-based cryptography, Proc. IEEE Inf. Theory Workshop-ITW 2011, pp.415-419, 2011.

S. Nicolas, On the dimension of the hull, SIAM J. Discrete Math. T. 10. 2, pp.282-293, 1997.

S. Adi, Identity-based cryptosystems and signature schemes, Advances in Cryptology -CRYPTO 84. Sous la dir. de G. R. BLAKLEY et David CHAUM. T. 196, pp.47-53, 1984.

S. Victor, Sequences of games : a tool for taming complexity in security proofs, IACR Cryptology ePrint Archive, p.332, 2004.

W. Peter and . Shor, Algorithms for quantum computation : Discrete logarithms and factoring, pp.124-134, 1994.

S. Raj, S. Young-sik, and K. , New McEliece cryptosystem based on polar codes as a candidate for post-quantum cryptography, 14th International Symposium on Communications and Information Technologies (ISCIT), pp.368-372, 2014.

D. Silva, R. Frank, . Kschischang, and K. Ralf, Communication over finite-field matrix channels, IEEE Trans. Information Theory, vol.56, pp.1296-1305, 2010.

S. Ryuichi, O. Kiyoshi, and K. Masao, Cryptosystems based on pairing, SCIS 2000, 2000.

P. Spaenlenhauer, Résolution de systèmes multi-homogènes et determinantiels, Univ. Pierre et Marie Curie-Paris, vol.6, 2012.

V. Michilovich, S. , and S. O. Shestakov, On the insecurity of cryptosystems based on generalized Reed-Solomon codes, Discrete Math. Appl, vol.1, issue.4, pp.439-444, 1992.

S. Jacques, A method for finding codewords of small weight, Coding Theory and Applications. Sous la dir. de G. D. COHEN et J. WOLFMANN. T. 388, pp.106-113, 1988.

J. Stern, A New Identification Scheme Based on Syndrome Decoding, 1993.

S. Jacques, A New Identification Scheme Based on Syndrome Decoding, Advances in Cryptology -CRYPTO'93. Sous la dir. de D.R. STINSON. T. 773, pp.13-21, 1993.

S. Nicolas and V. Valentin, On the Decoding Failure Rate of QC-MDPC Bit-Flipping Decoders, IACR Cryptology ePrint Archive, p.1207, 2018.

S. Nicolas and V. Valentin, On the Decoding Failure Rate of QC-MDPC Bit-Flipping Decoders, Post-Quantum Cryptography 2019. Sous la dir. de Jintai DING et Rainer STEINWANDT. T. 11505, pp.404-416, 2019.

J. Tillich, The Decoding Failure Probability of MDPC Codes, 2018 IEEE International Symposium on Information Theory, pp.941-945, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01957037

J. Tillich, The decoding failure probability of MDPC codes, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01957037

V. Pascal, Improved identification schemes based on error-correcting codes, In : Appl. Algebra Eng. Commun. Comput, vol.8, issue.1, pp.57-69, 1996.

W. David, A generalized birthday problem, Advances in Cryptology -CRYPTO 2002. Sous la dir. de Moti YUNG. T. 2442, pp.288-303, 2002.

W. Christian, Two NP-complete Problems in Coding Theory with an Application in Code Based Cryptography, Proc. IEEE Int. Symposium Inf. Theory -ISIT, pp.1733-1737, 2006.

M. J. Wainwright, N. Elitza, . Maneva, and M. Emin, Lossy source compression using low-density generator matrix codes : analysis and algorithms, IEEE Trans. Information Theory, vol.56, pp.1351-1368, 2010.

A. Carlos, . Melchor, A. Nicolas, B. Slim, B. Loïc et al., Second round submission to the NIST post-quantum cryptography call, 2019.

C. Rodolfo and . Torres, Asymptotic Analysis of ISD algorithms for the q´ary case, Proceedings of the Tenth International Workshop on Coding and Cryptography WCC 2017, 2017.

E. Taher, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, 1984.