P vs NP vs IP vs SNARK

Déterminer si un vérificateur faible peut vérifier des affirmations d'une superintellygence est un problème standard de la cryptographie. Cette vidéo explique ce mécanisme, et les grandes questions scientifiques qui l'entourent.
#LeFabuleuxChantier #Tournesol #Bayes #Science4All

0:00 Introduction
1:25 P versus NP
6:56 Les preuves de connaissance
12:13 La classe IP
17:20 Les SNARK
23:10 Conclusion

Guide de survie au cybercrime en entreprise (mon 6e livre, avec Romain du Maraiis, aka @Pour 1nf0 ) :
La dictature des algorithmes (mon 5e livre, avec Jean-Lou Fourquet, aka @ApresLaBiere ) :
SmartPoop (mon 4e livre, avec Tristan Le Magoarou, aka @RisqueAlpha ) :
Turing à la plage (mon 3e livre, avec Rachid Guerraoui) :
Le fabuleux chantier (mon 2e livre, avec El Mahdi El Mhamdi) :
La formule du savoir (mon 1er livre) :

[bause]

Une des meilleures chaînes de vulgarisation !

[Cuikui]

Un programme intéressant. 1 million pour P vs NP est une somme assez dérisoire par rapport à l'impact que ça aurait.

[LaCaverneDesCodeurs]

Ouille. J'ai eu la mauvaise idée d'écouter la vidéo à une heure où ma tête commençait à se fatiguer 🙂
Suis bon pour réécouter un autre jour...

[tartiflettefontaine]

La métaphore du prouveur faible et de la superyntelligence est extremement claire merci

[tartiflettefontaine]

J'ai cliqué parce que j'arrivais plus a me rappeler de qui etait le barbu sur la miniature et la 4ème fois que j'ai vu j'ai ressenti de la satisfaction, bravo.

[unknowjlm]

J'ai l'impression, surtout après cette vidéo, que résoudre P = NP mérite + qu'un million...

[VaviVove]

Etrange coïncidence je lisais des choses sur les VRF, merci pour le contenu de qualité 👍

[ethernaal]

Ah super, les preuves à divulgation nulles font partis de ce que je recherche en ce moment ! J'ai hâte de voir tes vidéos sur zk-snark et zk-stark. J'ai n'ai pas réussi à les généraliser pour fonctionner avec un algorithme quelconque, à chaque fois il faut construire un circuit (R1CS) spécifique et donc réussir à transformer l'algo dont je souhaite prouver l'exécution en un problème mathématique très précis :\
Tu vas peut-être me faire avancer dans ma quête pour un système de vote à distance, anonyme et sécurisé !

[ThomasKundera]

5:32 : Plutôt que de dire qu'il faut 60s (n=60), disons qu'il faut une minute (n=1).
Dans ce cas, 2¹=2 et donc on va trouver en 2mn, et non des trouzillions de secondes.

(Y'a une astuce quelque part, mais ce point de la vidéo est imprécis:, n est un nombre d'opérations, pas un temps).

[VaviVove]

13:30 il y a une coquille dans la définition de la classe IP, quand la réponse est non, pour tout prouveur Q (malicieux), la probabilité que le verificateur accepte la preuve doit être inférieure à 1/3 ( et non pas supérieur à 2/3) ça serait bizarre sinon non ?

[aragon]

Fantastique !! Je n'ai pas fait de 🐓
à l'université seulement entendu parler il y a un an

[bobbogus]

Je ne pense pas que l'usage de plein d'extraits randoms d'autres chaines apporte quelquechose à la vidéo :/

[marcaurelion]

Tu penses quoi de Zama qui fait de la cryptographie homomorphique ? C'est une solution valide pour la sécurité et la confidentialité des données ?

[patrickguedj]

c (~= 300 000 km/s) établi un lien entre le temps et l'espace, établi aussi un lien entre l'énergie et la masse. Pour des algorithmes, utiliser plus d'espace réduit le temps. Savez vous si l'on retrouve c dans la complexité des algorithmes ?

[Captainumerica]

Plusieurs points par étapes :

- si l'on accepte la validité statistique comme suffisamment satisfaisante, alors ne risque-t'on pas juste de lancer un SNARKrun avec farming comme on l'a vu sur la crypto?
- si l'on admet la possibilité de superintelligence, est-ce qu'on ne va pas pousser cette IA à aller à l'hyperintelligence pour résoudre P =/≠ NP? J'ajoute que si je suis une super, a fortiori hyperintelligence, j'aurais tendance à vouloir conserver cet avantage stratégique par-devers moi.
- au final, ne va-t'on pas se retrouver piégés dans une version globalisée du dilemme du menteur?

D'avance désolé si je suis complètement à coté de la plaque.

[AvatarsBlanc]

Je fais une thèse sur des SNARK à base de codes et je tiens à ajouter que la seule hypothèse cryptographique de ces protocoles (contrairement à ceux à base de courbes elliptiques ou de réseaux euclidiens) est l'existence d'une fonction de hashage cryptographique !
Je pensais avoir vu des papiers sur le fait de vérifier l'entraînement d'un réseau de neurones. Je vérifie ça demain.

[kalgon]

A quand un featuring avec Eli Ben Sasson ? (STARK)
Sinon COQ ça me rappelle mon "enfance", j'en ai fait un peu à la FAC c'était il y a presque 20 ans 😱

[pierrerunavot]

Pas simple tout ça ! Ca me rappelle les problèmes actuels en GenAI et les vérificateurs. On a une grosse machine qui peut être utile mais qui génère souvent n'importe quoi, il faut pouvoir controler la performance, on peut écrire des vérificateurs, mais c'est pas très satisfaisant.

[aymantimjicht]

J'attends encore mon argent de mes recherches. L'histoire du million de dollars pour P vs NP serait-elle une autre arnaque ou Il prend le temps de vérification, mais devrait au moins vérifier l'heure de ma publication avant de me payer?
J'ai fait plus de 100 autres démonstrations en l'attendant.

[Anonyme-car-trop-de-cons]

j'ai le neurone qui fume c'est un travail sur le contrôle de la dérive entre les souhait exprimé a une intelligence et sa réponse ou une recherche sur les limites de l’intelligence?