Title: Vérification simultanée de preuves avec des codes de Reed-Solomon entrelacés
Resume: Les protocoles interactifs STARKs permettent à un vérifieur faible de vérifier qu’un prouveur infiniment puissant a effectué honnêtement un calcul. Cette vérification d’exécution honnête est ramenée à une vérification d’appartenance d’un certain mot à un code de Reed-Solomon. Le protocole interactif FRI permet ensuite de tester cette appartenance en temps logarithmique en la dimension du code pour le prouveur.
Les codes de Reed-Solomon entrelacés possèdent certaines propriétés semblant indiquer qu’ils pourraient donner une meilleure soundness que les codes de Reed-Solomon classiques, c’est-à-dire qu’un prouveur malhonnête aurait une plus petite probabilité de pouvoir tricher sans être detecté. Une autre motivation pour l’utilisation de ces codes est qu’en pratique de nombreux mots doivent être testés successivement, et que l’entrelacement est une technique classique dans ces cas.
Durant mon stage sous la direction de Daniel Augot j’ai tenté d’adapter les preuves existantes de soundness avec les codes de Reed-Solomon pour les utiliser avec des codes entrelacés et améliorer la soundness du protocole. J’ai pu adapter les preuves pour utiliser des codes entrelacés mais les propriétés nécessaires pour améliorer la soundness ne s’avèrent pas être exactement celles des codes de Reed-Solomon entrelacés.