Vérification ultra-rapide des preuves mathématiques : ce que signifie ce nouveau résultat pour l'authentification de données massives

Points clés

• Apple ML Research a publié une étude sur une nouvelle classe de systèmes de preuve mathématique appelée preuves interactives doublement sous-linéaires de proximité.
• La méthode permet à un prouveur, la partie qui formule une affirmation, de lire seulement une petite fraction d'un ensemble de données massif pour générer une preuve.
• Un vérificateur, la partie qui contrôle l'affirmation, doit lire une fraction encore plus petite pour confirmer si la preuve est probablement correcte.
• La technique s'applique à la vérification approximative, ce qui signifie qu'elle détecte les entrées clairement incorrectes sans avoir besoin d'inspecter chaque octet.
• Selon la recherche, aucune technique existante ne peut tromper le vérificateur pour qu'il accepte une affirmation fausse.

Imaginez que vous exploitez un entrepôt contenant un million de boîtes et que quelqu'un vous dit qu'environ 95 pour cent d'entre elles sont correctement étiquetées. Vous n'avez pas le temps d'ouvrir chaque boîte. Et si vous pouviez en vérifier au hasard quelques centaines seulement et rester certain que l'affirmation est fondée ? C'est l'intuition qui sous-tend cette recherche.

Des scientifiques d'Apple ML Research ont publié une étude sur ce qu'ils appellent les preuves interactives doublement sous-linéaires de proximité, ou dsIPP. Une preuve interactive de proximité est un protocole, un échange formel entre deux parties, qui permet à l'une de convaincre l'autre qu'un énorme ensemble de données satisfait une certaine propriété, sans que l'une ou l'autre ait besoin de lire la totalité. « Sous-linéaire » signifie simplement que le travail augmente beaucoup plus lentement que la taille des données, de sorte que vérifier un milliard d'enregistrements pourrait nécessiter la lecture de seulement quelques milliers.

La partie « doublement » est la nouvelle subtilité. La partie qui génère la preuve et celle qui la vérifie travaillent toutes deux en temps sous-linéaire. Auparavant, les systèmes de preuve de ce type exigeaient que le prouveur lise l'ensemble des données. Ici, le prouveur lit une petite portion. Le vérificateur lit une portion encore plus petite.

Que signifie « approximatif » ici ? Le système ne garantit pas la perfection. Il garantit que si une entrée appartient véritablement à la propriété testée, un prouveur honnête peut toujours convaincre le vérificateur d'accepter. Et si une entrée est très éloignée de cette propriété, aucun prouveur malhonnête ne peut tromper le vérificateur en le faisant dire oui. Pensez à un détecteur de fumée : il ne manquera pas un vrai feu, et une machine à fumée ne le trompera pas.

Pourquoi les gens ordinaires devraient-ils s'en soucier ?

Vous n'interagirez probablement pas directement avec cette recherche pendant des années, voire jamais. Mais les problèmes qu'elle résout se trouvent sous les technologies que les gens utilisent chaque jour. Les services de diffusion en continu vérifient si d'énormes bibliothèques de fichiers respectent les normes de qualité. Les banques auditent les enregistrements de transactions pour détecter les fraudes. Les systèmes de santé analysent des millions de dossiers pour identifier les erreurs de signalement. Toute situation où vérifier tout est trop lent ou trop coûteux est exactement celle où ce type de système de preuve devient utile.

La recherche est théorique pour l'instant, ce qui signifie qu'elle pose les fondations mathématiques plutôt que de livrer un produit. Les outils pratiques basés sur ces idées pourraient permettre aux systèmes logiciels de vérifier des affirmations à grande échelle bien plus rapidement que les méthodes actuelles ne le permettent, sans compromettre la fiabilité.

L'article complet est disponible pour les chercheurs qui souhaitent approfondir les preuves formelles et les limites de complexité.