En 1978, McEliece introduit un schéma de chiffrement à clé publique issu de la théorie des codes correcteurs d’erreurs. L’idée du schéma de McEliece est d’utiliser un code correcteur dont lastructure est masquée, rendant le décodage de ce code difficile pour toute personne ne connaissant pas cette structure. Le principal défaut de ce schéma est la taille de la clé publique. Dans ce contexte, on se propose d'étudier l'utilisation de codes dont on connaît une représentation compacte, en particulier le cas de codes quais-cyclique ou quasi-dyadique. Les deux familles de codes qui nous intéressent dans cette thèse sont: la famille des codes alternants et celle des sous--codes sur un sous--corps de codes géométriques. En faisant agir un automorphisme $sigma$ sur le support et le multiplier des codes alternants, on saitqu'il est possible de construire des codes alternants quasi-cycliques. On se propose alors d'estimer la sécurité de tels codes à l'aide du textit{code invariant}. Ce sous--code du code public est constitué des mots du code strictement invariant par l'automorphisme $sigma$. On montre ici que la sécurité des codes alternants quasi-cyclique se réduit à la sécurité du code invariant. Cela est aussi valable pour les sous—codes sur un sous--corps de codes géométriques quasi-cycliques. Ce résultat nous permet de proposer une analyse de la sécurité de codes quasi-cycliques construit sur la courbe Hermitienne. En utilisant cette analyse nous proposons des clés compactes pour la schéma de McEliece utilisant des sous-codes sur un sous-corps de codes géométriques construits sur la courbe Hermitienne. Le cas des codes alternants quasi-dyadiques est aussi en partie étudié. En utilisant le code invariant, ainsi que le textit{produit de Schur}et le textit{conducteur} de deux codes, nous avons pu mettre en évidence une attaque sur le schéma de McEliece utilisant des codes alternants quasi-dyadique de degré $2$. Cette attaque s'applique notamment au schéma proposé dans la soumission DAGS, proposé dans le contexte de l'appel du NIST pour la cryptographie post-quantique. / In 1978, McEliece introduce a new public key encryption scheme coming from errors correcting codes theory. The idea is to use an error correcting code whose structure would be hidden, making it impossible to decode a message for anyone who do not know a specific decoding algorithm for the chosen code. The McEliece scheme has some advantages, encryption and decryption are very fast and it is a good candidate for public-key cryptography in the context of quantum computer. The main constraint is that the public key is too large compared to other actual public-key cryptosystems. In this context, we propose to study the using of some quasi-cyclic or quasi-dyadic codes. In this thesis, the two families of interest are: the family of alternant codes and the family of subfield subcode of algebraic geometry codes. We can construct quasi-cyclic alternant codes using an automorphism which acts on the support and the multiplier of the code. In order to estimate the securtiy of these QC codes we study the em{invariant code}. This invariant code is a smaller code derived from the public key. Actually the invariant code is exactly the subcode of code words fixed by the automorphism $sigma$. We show that it is possible to reduce the key-recovery problem on the original quasi-cyclic code to the same problem on the invariant code. This is also true in the case of QC algebraic geometry codes. This result permits us to propose a security analysis of QC codes coming from the Hermitian curve. Moreover, we propose compact key for the McEliece scheme using subfield subcode of AG codes on the Hermitian curve. The case of quasi-dyadic alternant code is also studied. Using the invariant code, with the em{Schur product} and the em{conductor} of two codes, we show weaknesses on the scheme using QD alternant codes with extension degree 2. In the case of the submission DAGS, proposed in the context of NIST competition, an attack exploiting these weakness permits to recover the secret key in few minutes for some proposed parameters.
| Identifer | oai:union.ndltd.org:theses.fr/2018SACLX095 |
| Date | 10 December 2018 |
| Creators | Barelli, Elise |
| Contributors | Université Paris-Saclay (ComUE), Augot, Daniel, Couvreur, Alain |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0024 seconds