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

English

Séminaire AMAC: CASC

7/01/2021 - 13:30 Jade Nardi (Inria)

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.

(Travaux communs avec Sarah Bordage)