, Further examples of maximal curves, Journal of Pure and Applied Algebra, vol.213, issue.6, pp.1192-1196, 2009.
, Étude des systèmes algébriques surdéterminés. applications aux codes correcteurs et à la cryptographie, 2004.
, On the security of some compact keys for McEliece scheme, WCC Workshop on Coding and Cryptography, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01674546
, DAGS : Key encapsulation for dyadic GS codes, 2017.
, , 2017.
, Two-point codes for the generalised GK curve, IEEE Trans. Inform. Theory, 2017.
, An efficient structural attack on nist submission DAGS, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01796338
, Reducing key length of the McEliece cryptosystem, Progress in CryptologyAFRICACRYPT, vol.5580, pp.77-97, 2009.
, The Magma algebra system I: The user language, J. Symbolic Comput, vol.24, issue.3/4, pp.235-265, 1997.
, The order bound for general algebraic geometric codes, Finite Fields and Their Applications, vol.13, pp.665-680, 2007.
, Goppa and related codes invariant under a prescribed permutation, IEEE Trans. Inform. Theory, vol.46, issue.7, pp.2628-2633, 2000.
, On the cyclicity of Goppa codes, parity-check subcodes of Goppa codes and extended Goppa codes, Finite Fields Appl, vol.6, issue.3, pp.255-281, 2000.
, On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations, Proceedings of the International Conference on Polynomial System Solving, pp.71-74, 2004.
, Decoding random binary linear codes in 2 n/20 : How 1 + 1 = 0 improves information set decoding, Advances in Cryptology-EUROCRYPT 2012, 2012.
, Algebraic codes on lines, planes, and curves: an engineering approach, 2008.
, Monoidic codes in cryptography, Post-Quantum Cryptography, LNCS, vol.7071, pp.179-199, 2011.
, On the inherent intractability of certain coding problems, IEEE Trans. Inform. Theory, vol.24, issue.3, pp.384-386, 1978.
, Ag codes and ag quantum codes from the ggs curve, Designs, Codes and Cryptography, vol.86, issue.10, pp.2315-2344, 2018.
, McEliece cryptosystem implementation: theory and practice, Post-Quantum Cryptography, Second International Workshop, vol.5299, pp.47-62, 2008.
, A generalization of the weierstrass semigroup, Journal of Pure and Applied Algebra, vol.207, issue.2, pp.243-260, 2006.
, Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes, Des. Codes Cryptogr, vol.73, issue.2, pp.641-666, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00830594
, A polynomial time attack against algebraic geometry code based public key cryptosystems, Proc. IEEE Int. Symposium Inf. Theory-ISIT, pp.1446-1450, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00937476
, Cryptanalysis of McEliece cryptosystem based on algebraic geometry codes and their subcodes, IEEE Trans. Inform. Theory, vol.63, issue.8, pp.5404-5418, 2017.
, Polynomial time attack on wild McEliece over quadratic extensions, IEEE Trans. Inform. Theory, vol.63, issue.1, pp.404-427, 2017.
URL : https://hal.archives-ouvertes.fr/hal-00931774
, C library for computing asymptotic exponents of generic decoding work factors, 2016.
, Two-point ag codes on the gk maximal curves, IEEE Trans. Information Theory, vol.62, issue.2, pp.681-686, 2016.
, On subfield subcodes of modified Reed-Solomon codes, IEEE Trans. Inform. Theory, vol.21, issue.5, pp.575-576, 1975.
, New directions in cryptography, IEEE transactions on Information Theory, vol.22, issue.6, pp.644-654, 1976.
, Distance bounds for algebraic geometric codes, Journal of Pure and Applied Algebra, vol.215, issue.8, pp.1863-1878, 2011.
, Algebraic and physical security in code-based cryptography. (sécurités algébrique et physique en cryptographie fondée sur les codes correcteurs d'erreurs), 2015.
URL : https://hal.archives-ouvertes.fr/tel-01187916
, On minimum distance decoding of linear codes, Proc. 5th Joint SovietSwedish Int. Workshop Inform. Theory (Moscow), pp.50-52, 1991.
, The automorphism groups of Reed-Solomon codes, Journal of Combinatorial Theory, Series A, vol.44, pp.69-82, 1987.
, Two-point coordinate rings for gk-curves, IEEE Transactions on Information Theory, vol.57, issue.2, pp.593-600, 2011.
, Etudes de systèmes cryptographiques construits à l'aide de codes correcteurs, en métrique de hamming et en métrique rang, 2009.
, One-point ag codes on the gk maximal curves, IEEE Transactions on Information Theory, vol.56, issue.1, pp.202-210, 2010.
, A distinguisher for high rate McEliece cryptosystems, IACR Cryptology ePrint Archive, 2010.
, NP-completeness of certain sub-classes of the syndrome decoding problem, 2009.
, Cryptanalysis of the McEliece cryptosystem over hyperelliptic curves, Proceedings of the eleventh International Workshop on Algebraic and Combinatorial Coding Theory, pp.99-107, 2008.
, Folding alternant and Goppa Codes with non-trivial automorphism groups, IEEE Trans. Inform. Theory, vol.62, issue.1, pp.184-198, 2016.
, Structural cryptanalysis of McEliece schemes with compact keys, Des. Codes Cryptogr, vol.79, issue.1, pp.87-112, 2016.
, Algebraic cryptanalysis of McEliece variants with compact keys, Advances in Cryptology-EUROCRYPT 2010, vol.6110, pp.279-298, 2010.
, Algebraic attack against variants of McEliece with Goppa polynomial of a special form, Advances in Cryptology-ASIACRYPT 2014, vol.8873, pp.21-41, 2014.
, Decoding algebraic-geometric codes up to the designed minimum distance, IEEE Transactions on Information Theory, vol.39, issue.1, pp.37-45, 1993.
, Algebraic curves, An Introduction to Algebraic Geometry, p.54, 2008.
, Shorter keys for code based cryptography, Proceedings of the 2005 International Workshop on Coding and Cryptography (WCC 2005) (Bergen, Norway), pp.81-91, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00078726
, A generalization of the giulietti-korchmáros maximal curve, Advances in Geometry, vol.10, issue.3, pp.427-434, 2010.
, A new family of maximal curves over a finite field, Mathematische Annalen, vol.343, issue.1, p.229, 2009.
, Consecutive weierstrass gaps and minimum distance of goppa codes, vol.84, pp.199-207, 1993.
, Basic structures of function field arithmetic, Ergebnisse der Mathematik und ihrer Grenzgebiete, vol.35, issue.3, 1996.
, The automorphism group of the generalized giulietti-korchmáros function field, Advances in Geometry, vol.13, issue.2, pp.369-380, 2013.
, On subfields of the hermitian function field, Compositio Mathematica, vol.120, issue.2, pp.137-170, 2000.
, A modular analysis of the Fujisaki-Okamoto transformation, Theory of Cryptography Conference, pp.341-371, 2017.
, On the decoding of algebraic-geometric codes, IEEE Transactions on Information Theory, vol.41, issue.6, pp.1589-1614, 1995.
, Fundamentals of error-correcting codes, 2003.
, Algebraic geometry codes, Handbook of coding theory, vol.1, pp.871-961, 1998.
, Multi-point codes from the ggs curves, 2017.
, Construction and decoding of a class of algebraic geometry codes, IEEE Transactions on Information Theory, vol.35, issue.4, pp.811-821, 1989.
, McEliece public key cryptosystems using algebraic-geometric codes, Des. Codes Cryptogr, vol.8, issue.3, pp.293-307, 1996.
, Semantically secure mceliece public-key cryptosystem, IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, vol.85, issue.1, pp.74-83, 2002.
, The art of computer programming: sorting and searching, vol.3, 1997.
, Codes derived from binary Goppa codes, Probl. Inf. Transm, vol.37, issue.2, pp.91-99, 2001.
URL : https://hal.archives-ouvertes.fr/hal-00967387
, Weierstrass pairs and minimum distance of goppa codes, Designs, Codes and Cryptography, vol.22, issue.2, pp.107-121, 2001.
, Compact McEliece keys from Goppa codes, Selected Areas in Cryptography, 2009.
DOI : 10.1007/978-3-642-05445-7_24
URL : https://link.springer.com/content/pdf/10.1007%2F978-3-642-05445-7_24.pdf
, A public-key system based on algebraic coding theory, pp.114-116, 1978.
, The online database for optimal parameters of (t, m, s)-nets, (t, s)-sequences
, Cryptography based on error correcting codes, 2007.
, Decoding random linear codes in O(2 0.054n ), Advances in Cryptology-ASIACRYPT 2011, vol.7073, pp.107-124, 2011.
DOI : 10.1007/978-3-642-25385-0_6
URL : https://link.springer.com/content/pdf/10.1007%2F978-3-642-25385-0_6.pdf
, Algebraic curves over finite fields, 1993.
DOI : 10.1017/cbo9780511608766
, Equality of geometric goppa codes and equivalence of divisors, Journal of Pure and Applied Algebra, vol.90, issue.3, pp.229-252, 1993.
DOI : 10.1016/0022-4049(93)90043-s
URL : https://doi.org/10.1016/0022-4049(93)90043-s
, The theory of error-correcting codes, 1986.
, Cryptanalysis of the Sidelnikov cryptosystem, Advances in Cryptology-EUROCRYPT 2007, vol.4515, pp.347-360, 2007.
, Knapsack-type cryptosystems and algebraic coding theory, Problems of Control and Information Theory, vol.15, pp.159-166, 1986.
, On a decoding algorithm for codes on maximal curves, IEEE transactions on information theory, vol.35, issue.6, pp.1228-1232, 1989.
DOI : 10.1109/18.45279
, Information-set decoding for linear codes over F q , Post-Quantum Cryptography, LNCS, vol.6061, pp.81-94, 2010.
DOI : 10.1007/978-3-642-12929-2_7
URL : http://www.win.tue.nl/%7Ecpeters/publications/2010.isdfq.pdf
, The use of information sets in decoding cyclic codes, IRE Transactions on Information Theory, vol.8, issue.5, pp.5-9, 1962.
DOI : 10.1109/tit.1962.1057777
, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, vol.21, issue.2, pp.120-126, 1978.
DOI : 10.1145/357980.358017
URL : http://people.csail.mit.edu/rivest/pubs/RSA78.pdf
, On the structure of a randomly permuted concatenated code, pp.169-173, 1994.
, Finding the permutation between equivalent linear codes: The support splitting algorithm, IEEE Trans. Inform. Theory, vol.46, issue.4, pp.1193-1203, 2000.
, Algorithms for quantum computation: Discrete logarithms and factoring, FOCS, pp.124-134, 1994.
, A public-key cryptosytem based on Reed-Muller codes, Discrete Math. Appl, vol.4, issue.3, pp.191-207, 1994.
, Fast decoding of algebraic-geometric codes up to the designed minimum distance, IEEE Transactions on Information Theory, vol.41, issue.6, pp.1672-1677, 1995.
, On the insecurity of cryptosystems based on generalized Reed-Solomon codes, Discrete Math. Appl, vol.1, issue.4, pp.439-444, 1992.
, A method for finding codewords of small weight, Coding Theory and Applications, LNCS, vol.388, pp.106-113, 1988.
, On automorphisms of geometric Goppa codes, Journal of Algebra, vol.130, issue.1, pp.113-121, 1990.
, Algebraic function fields and codes, Graduate Texts in Mathematics, vol.254, 2009.
, On the decoding of algebraic-geometric codes, IEEE Transactions on Information Theory, vol.36, issue.5, pp.1051-1060, 1990.
, List of Algorithms 1 Recover the divisor in the case ? diagonalizable in F q m, p.61, 2007.
,
, 85 7 Recover the code C pub from the invariant code
,
, 71 4.2 Number of variables of the polynomial system after reduction, List of Tables 3.1 Average time for Algorithm 3 with ? diagonalizable in F q
, Estimation of the minimum distance
, We define L(G + ?Q, Definition A.1. Let Q be a rational place and G be a rational divisor of F q (?)
, We call H(Q
, G) the set of G-non-gaps at Q. The set ?(Q; G) := Z ?v Q (G)?deg(G) \ H(Q; G) is called the set of G-gaps at Q
, the set of gaps at Q. Further, note that if i ? H(Q; F 1 ) and j ? H(Q; F 2 ), then i + j ? H(Q; F 1 + F 2 ). Finally, observe that the theorem of Riemann-Roch implies that the number of G-gaps at Q coincides with the genus of ?
,
, If i < ? deg(G) then deg(G + iQ) < 0 and L(G + iQ) = {0}. So in the previous definition we can write L(G + ?Q) = i?? deg(G) L(G + iQ). Further, note that for any a ? Z we have
, G + aQ) = H(Q; G) as well as ?(Q
,
, Let Q be a rational place and let F 1 , F 2 be two divisors of ?
, Q be a rational place not occurring in D, and F 1 , F 2 be two divisors disjoint from D. Suppose that C L, Let D = P 1 + · · · + P n be a divisor that is a sum of n distinct rational places of F q (?)
, + F 2 ) of C L (D, F 1 + F 2 ) ? satisfies d(F 1 + F 2 ) ? min{?(Q; F 1
, Q (N ) of not necessarily distinct rational places, none occurring in D, such that
, 0), where the minimum is taken over all i satisfying 1 ?
, ) + · · · + Q (i) ). The well known Goppa bound is a direct consequence of Proposition A.1 as shown in
, If the support of a divisor G consists of one rational point not in supp(D), the code C L (D, G) is called a one-point AG code. Similarly, if G = a 1 Q 0 + a 2 Q ? , the code C L (D, G) is called a two-point code. By slight abuse of notation, the dual of a one-point code (resp. two-point code) are sometimes also called one-point (resp. two-point) codes, but we will only use the terminology for the codes C L (D, G), n be a sum of distinct rational places, let Q be a rational place not occurring in D, and let F 1 , F 2 be two divisors disjoint from D. Then ?(Q; F 1
, ) for all t satisfying 0 ? t ? min{b 2 ? 1, 2g ? 1 ? a 1 ? a 2 }. In the next theorem we show that the order bound in the same situation improves upon the Goppa bound by at least one as well. Therefore, our results will automatically include all results in [CT16b] as a special case
, Q 2 ) for all t satisfying 0 ? t ? min{b 2 ? 1, 2g ? 1 ? a 1 ? a 2 } is equivalent to the statement that ? Q 1 ,Q 2 (b 1 ) ? b 2 or ? Q 1 ,Q 2 (b 1 ) < b 2 ?1?min{b 2 ?1, 2g?1?a 1 ?a 2 }. With these reformulations in mind
,
, ) < b 2 ? 1 ? min{b 2 ? 1, 2g ? a 1 ? a 2 }, then ?(Q 2
, Combining Remark 23 with (the proof of) Lemma A.2 we see that ?(Q 1 G) ? 2g(?) + 2. Indeed, the term q Q 1, vol.223, p.220
, ) for which dimension of the form C L (D, a 1 Q 0 ) ? or C L (D, a 2 Q ? ) ?. The four entries in boldface indicate new improvements on the MinT tables, Table A.1 gives for q = 2