Jiatu Li | How to build cryptography from proof complexity

Valeur des informations & solidité de l’argumentation

La valeur de cette présentation réside dans sa capacité à établir une connexion inattendue entre deux domaines distincts de l’informatique théorique : la complexité des preuves et la cryptographie. L’argumentation suit une logique rigoureuse : après avoir défini les deux problèmes clés (bornes inférieures pour EF et SNARKs dans le modèle standard), Li montre comment une hypothèse naturelle sur l’inprouvabilité de ces bornes peut être exploitée pour obtenir des SNARKs. La démonstration repose sur l’observation que la sécurité d’un schéma SNARK peut être formalisée dans une théorie faible, ce qui permet d’utiliser une preuve de contradiction. L’orateur insiste sur la simplicité conceptuelle de l’observation centrale, tout en reconnaissant la complexité technique des travaux sous-jacents. La solidité de l’argumentation est renforcée par les références à des résultats récents et par les échanges approfondis avec l’auditoire, qui permettent de clarifier les subtilités de la preuve.

Rigueur scientifique, qualité des sources, adéquation du titre

La rigueur scientifique est exemplaire : l’exposé est fondé sur des travaux de recherche publiés et cite explicitement les auteurs et années. Les sources mentionnées incluent les travaux de Krajíček et Pudlák, Razborov, Ilango, Jain et Jain, et Jain–Kalai–Lombardi–Venkatakrishnan. Les liens fournis dans la description (newton.ac.uk et la page du séminaire) renvoient à des ressources institutionnelles fiables. L’adéquation entre le titre et le contenu est parfaite : le titre annonce la construction de cryptographie à partir de la complexité des preuves, et l’exposé développe exactement cette idée. Aucun écart n’est constaté. La présentation est précise, avec des définitions formelles et des preuves ébauchées, ce qui en fait une source crédible pour un public de spécialistes.

Le titre décrit exactement le sujet : la construction de primitives cryptographiques (SNARKs) à partir d'hypothèses de complexité des preuves.

9/10

Exposé de recherche par un spécialiste reconnu, présenté à l'Institut Isaac Newton, avec des références précises à des travaux récents et une argumentation formelle rigoureuse.

Repères établis par PSI à partir de la transcription : le créateur n'a pas défini de chapitres.

• 02:00Introduction : motivation et contexte, lien entre preuves et cryptographie.
• 05:00Problème ouvert 1 : borne inférieure pour le système de Frege étendu (EF).
• 10:00Problème ouvert 2 : construction de SNARKs dans le modèle standard (sans obfuscation).
• 15:00Établissement du lien entre les deux problèmes et formulation de l'hypothèse d'inprouvabilité.
• 20:00Esquisse de la preuve : formalisation de la sécurité du schéma dans une théorie faible et utilisation de la contradiction.
• 30:00Travail complémentaire : générateurs de complexité de preuves et perspectives.

• Site officiel de l'Institut Isaac Newton — Page principale de l'institut, mentionnée dans la description de la vidéo.
• Page du séminaire (LFCW02) — Page dédiée au séminaire où cet exposé a été donné, fournissant le programme et les détails.

• Page du séminaire INI — Confirme l'existence de l'exposé et son cadre institutionnel.