Sarah Bordage, member of the Grace team, will defend her PhD thesis entitled “Efficient protocols for testing proximity to algebraic codes”.

The defense will take place on the 16th of June at 10:00 am at Inria Saclay, Amphithéâtre Sophie Germain (1 rue Honoré d’Estiennes d’Orves, 91120 Palaiseau).

The presentation will be given in English. It will also be possible to follow the defense remotely, please find more details below.

Keywords: interactive proof systems, probabilistic proof systems, low degree tests, proximity testing, error- correcting codes, algebraic geometry

Abstract: Probabilistic proof systems, such as probabilistically checkable proofs, interactive proofs, and zero-knowledge proofs, feature the common characteristic of having a probabilistic verification procedure. Notably, such proof systems are at the heart of cryptographic protocols that enable polylogarithmic-time verification of very long computations.

Generalizing both PCPs and IPs, the Interactive Oracle Proof (IOP) model has been introduced in 2016 by Ben-Sasson, Chiesa and Spooner. The IOP model has attracted a lot of interest since its introduction, leading to both interesting theoretical results related to efficient transparent succinct non-interactive arguments and industrial deployments.

A recurrent problem in constructions of probabilistic proof systems is that of testing proximity to an error-correcting code. The goal is to determine whether a certain word belongs to a given linear code, or if it is far from any codeword of that code. Proximity tests for polynomial codes are often called low degree tests. A notable building-block of several IOP-based constructions is a concretely efficient IOP of Proximity for testing proximity to Reed-Solomon codes (Ben-Sasson et al., ICALP 2018).

In this thesis, we propose protocols in the IOP model for verifying proximity to error-correcting codes. Based on the proximity test for Reed-Solomon codes designed by Ben-Sasson et al., we formulate and analyze an abstract and generic framework to construct IOPs of Proximity for linear codes. We then apply this methodology to different families of codes that generalize Reed-Solomon codes. These are, on the one hand, codes defined from evaluations of multivariate polynomials and, on the other hand, algebraic geometry codes defined on curves. Our protocols have similar efficiency parameters compared to the construction of Ben-Sasson et al., and allow efficient proximity testing for families of codes with attractive properties compared to Reed-Solomon codes (such as small alphabet sizes).

WebEx meeting

• Invite link : https://inria.webex.com/inria/j.php?MTID=m8fe32d0e8800c9bf1c2191d82e9ac6bc
• Meeting ID : 2742 984 3956
• Password : JAmc3yRM3J7