Note publique d'information : En 1978, McEliece introduit un nouveau schéma de chiffrement à clé publique basé sur
les codes correcteurs d'erreurs. Depuis, il s'est avéré avoir de nombreux avantages,
comme un chiffrement et déchiffrement rapide, couplé au fait qu'il soit un bon candidat
en cryptographie post-quantique. La principale contrainte est qu'il impose des tailles
de clé trop grosses comparées aux autres systèmes de chiffrement à clé publique actuels.
Dans ce contexte, nous étudions la sécurité de certaines variantes du schéma de McEliece,
basées sur des sous-codes de codes de géométrie algébrique (SSAG). Plus précisément,
nous montrons que la structure secrète du code SSAG public peut être récupérée à partir
du celle de son sous-code invariant, qui a de plus petits paramètres.Initialement
fondée sur les codes de Goppa classique, la proposition initiale de McEliece est encore
considérée comme sécurisé aujourd'hui. Tenant compte de ce fait, nous définissons
une nouvelle famille de codes : les codes AG Goppa-like. L'idée est de copier la structure
algébrique des codes de Goppa hérité du choix du multiplicateur, tout en considérant
des courbes de genre supérieur, permettant de construire de plus longs codes. Se concentrant
sur les codes à un point sur des courbes C_{a,b}, nous étudions le comportement de
la dimension du carré de leur dual pour évaluer leur résistance aux attaques par distingueur.
Comme cette famille peut être encodée rapidement, il s'agit d'un bon candidat pour
remplacer les codes de Goppa classiques.Dans le contexte des preuves par oracle interactif
(IOPs), nous engageons l'étude de tests de proximité à des codes AG. Le problème de
tester la proximité à un code C consiste à distinguer le cas ou un mot donné en entrée
appartient à C du cas où il en est très éloigné. Dans le but de généraliser le protocole
FRI s'appuyant sur les codes de Reed-Solomon, nous proposons un cadre valide pour
définir un IOP de Proximité aux codes AG (AG-IOPP). Comme exemple concret, nous nous
concentrons sur les codes construits à partir d'une tour de courbes Hermitiennes,
qui peuvent être définis sur un alphabet de taille polylogarithmique. Nous donnons
également une famille de codes repliables dont l'AG-IOPP correspondant atteint une
complexité quasilinéaire pour le prouveur et polylogarithmique pour le vérifieur.
Note publique d'information : In 1978, McEliece introduced a new public-key cryptosystem, based on error-correcting
codes. Since then, it has demonstrated to have a lot of advantages, such as a fast
encryption and decryption, in addition to the fact that it is a good candidate for
post-quantum cryptography. The main constraint is that it imposes large keys sizes
compared with other actual public-key cryptosystems. In this context, we study the
security of variants of McEliece's encryption schemes based on structured subfield
subcode of algebraic geometry codes (SSAG). More precisely, we show that the underlying
secret structure of the public SSAG can be recovered from that of its invariant code,
which has smaller parameters.Initially based on the family of classical Goppa codes,
the first proposal of McEliece is still considered secure today. Taking this into
account, we define a new family of codes: Goppa-like AG codes. The idea is to mimic
the algebraic structure of Goppa codes inherited from the choice of the multiplier
while considering higher genus curves, which allows to construct longer codes. Focusing
one one-point codes from C_{a,b} curves, we study the behavior of the square of their
dual to determine their resistance to distinguisher attacks. As this family can be
efficiently encoded, it is a good candidate to replace classical Goppa codes.In the
context of Interactive Oracle Proofs (IOPs), we initiate the study of proximity tests
to AG codes. The problem of testing proximity to a code C consists in distinguishing
between the case where an input word belong to C and the case where it is far from
it. Aiming to generalize the FRI protocol based on Reed-Solomon codes, we give valid
setting to design an efficient IOP of Proximity to AG codes (AG-IOPP). As concrete
instantiation, we focus on AG codes arising from a tower of Hermitian curves, which
can be defined over polylogarithmic-size alphabet. We also give a family of foldable
AG codes on this tower whose corresponding AG-IOPP achieves quasilinear prover time
and polylogarithmic verification.
paprika.idref.fr
data.idref.fr
Documentation
