INRIA Saclay, GRACE team, Palaiseau
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
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)