Preuves interactives de proximité d’un mot à un code géométrique

Jade Nardi
INRIA Saclay, GRACE team, Palaiseau
http://www.lix.polytechnique.fr/Labo/Jade.NARDI/

Date(s) : 11/03/2021 iCal
11 h 00 min - 12 h 00 min

Ces dernières années, d’énormes progrès ont été accomplis dans le domaine du calcul vérifiable. Celui-ci permet de fournir, en plus d’un résultat, une preuve courte et rapidement vérifiable que le calcul a été correctement effectué. Certaines de ces preuves peuvent également avoir une propriété « zero-knowledge« , et sont aujourd’hui largement déployées dans des applications liées aux blockchains.

Parmi les différentes familles de schémas de calcul vérifiable, une famille de constructions reposent fondamentalement sur des tests de proximité à des codes algébriques, héritant de techniques étudiées dans les constructions de preuves vérifiables de façon probabilistes (PCP, probabilistically checkable proof) et de systèmes de preuves interactives (IPs, interactive proofs). Dans cette famille, les constructions implémentées dans l’industrie (Stark) utilisent un protocole interactif, appelé FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity), permettant de vérifier la proximité à des codes de Reed-Solomon en temps logarithmique (en la longueur du code).

Naturellement, on se demande si les codes algébriques, généralisation des codes de Reed-Solomon, admettent des tests de proximité avec des paramètres similaires. Dans cet exposé, on présentera le protocole FRI en détails, en prenant du recul sur les outils mathématiques qui font son efficacité. On décrira comment généraliser ces outils aux codes géométriques (qu’on prendra le temps d’introduire rapidement), quels obstacles apparaissent naturellement à cause de la géométrie des courbes non rationnelles et comment les surmonter en adaptant le protocole. On détaillera le cas de codes sur des extensions de Kummer.

(Collaboration avec Sarah Bordage)

Lien Zoom :
https://univ-amu-fr.zoom.us/j/92195848065?pwd=dEVoUmx1b1JUYTdERVZ1c1NPazN0QT09

Meeting ID : 921 9584 8065

Passcode : please contact the organizers / veuillez envoyer un e-mail aux organisateurs

Interactive proofs of proximity of a word to a geometric code

In recent years, enormous progress has been made in the field of verifiable computation. This makes it possible to provide, in addition to a result, a short and quickly verifiable proof that the calculation was correctly carried out. Some of this evidence may also have a « zero-knowledge » property, and is now widely deployed in blockchain-related applications.

Among the different families of verifiable calculation schemes, a family of constructions are fundamentally based on tests of proximity to algebraic codes, inheriting techniques studied in the constructions of probabilistically checkable proofs (PCP) and systems of interactive proofs (IPs, interactive proofs). In this family, the constructions implemented in industry (Stark) use an interactive protocol, called FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity), making it possible to verify the proximity to Reed-Solomon codes in logarithmic time (in the length of the code).

Naturally, one wonders if algebraic codes, generalization of Reed-Solomon codes, admit proximity tests with similar parameters. In this talk, we will present the FRI protocol in detail, taking a step back from the mathematical tools that make it effective. We will describe how to generalize these tools to geometric codes (which we will take the time to introduce quickly), what obstacles naturally appear because of the geometry of non-rational curves and how to overcome them by adapting the protocol. We will detail the case of codes on Kummer extensions.

(Collaboration with Sarah Bordage)

https://arxiv.org/abs/2011.04295

Catégories