Julien Lavauzelle, de l’équipe Grace, soutiendra sa thèse intitulée «Codes à propriétés locales : constructions et applications à des protocoles cryptographiques», le vendredi 30 novembre 2018 à 15h00 en salle Sophie Germain.

La soutenance aura lieu en anglais, devant le jury composé de :

• Maura Paterson, Université Birbeck de Londres (rapporteure)
• Christophe Ritzenthaler, Institut de recherche mathématique de Rennes (rapporteur)
• Alain Couvreur, Inria Saclay (examinateur)
• Camilla Hollanti, Université d’Aalto (examinatrice)
• Gilles Zémor, Université de Bordeaux (examinateur)
• Françoise Levy-dit-Vehel, ENSTA ParisTech (directrice de thèse)
• Daniel Augot, Inria Saclay (co-encadrant)

Résumé: Les codes localement corrigibles ont été introduits dans le but d’extraire une partie de l’information contenue dans un mot de code bruité, en effectuant un nombre limité de requêtes à ses symboles, ce nombre étant appelé la localité du code. Ces dernières années ont vu la construction de trois familles de tels codes, dont la localité est sous-linéaire en la taille du message, et le rendement est arbitrairement grand. Ce régime de paramètres est particulièrement intéressant pour des considérations pratiques.

Dans cette thèse, nous donnons une rapide revue de littérature des codes localement corrigibles, avant d’en proposer un modèle combinatoire générique, à base de block designs. Nous définissons et étudions ensuite un analogue, dans le cas projectif, des relèvements affines de codes introduits par Guo, Kopparty et Sudan. Nous établissons par ailleurs plusieurs liens entre ces deux familles, pour finir par une analyse précise de la structure monomiale de ces codes dans le cas du relèvement plan.

Une deuxième partie de la thèse se focalise sur l’application de ces codes à deux protocoles cryptographiques. D’abord, nous proposons un protocole de récupération confidentielle d’information (private information retrieval, PIR) à partir de codes basés sur des designs transversaux, dont la taille des blocs s’apparente à la localité d’un code localement corrigible. Les protocoles ainsi construits ont l’avantage de n’exiger aucun calcul pour les serveurs, et de présenter une faible redondance de stockage ainsi qu’une complexité de communication modérée. Ensuite, nous donnons une construction générique de preuve de récupérabilité (proof of retrievability, PoR) à base de codes admettant une riche structure d’équations de parité à petit poids. Nous en donnons finalement une analyse de sécurité fine ainsi que plusieurs instanciations fondées sur des codes à propriétés locales.