Inspiré par une question que m'a posée Greg Kuperberg, je me demande s'il existe des articles qui définissent et étudient les classes de complexité des langues admettant divers types de preuves de connaissances . Les classes comme SZK et NISZK sont extrêmement naturelles du point de vue de la...
Dans le chapitre 10 de HAC (10.4.2) , nous voyons le célèbre protocole d'identification Feige-Fiat-Shamir basé sur une preuve de connaissance nulle utilisant la difficulté (présumée) d'extraire des racines carrées modulo un composite difficile à factoriser. Je vais donner le schéma dans mes propres...
La preuve de Goldreich et al. Que la trois colorabilité n'a aucune preuve de connaissance utilise l'engagement de bits pour une coloration entière du graphique à chaque tour [1]. Si un graphe a sommets et e arêtes, un hachage sécurisé a b bits et que nous recherchons la probabilité d'erreur p , le...
Existe-t-il un moyen pour un prouveur de convaincre un vérificateur qu'une expression HORN-SAT est satisfaisable? Bien sûr, cela peut sembler idiot, car il existe des algorithmes de temps linéaires pour HORN-SAT. D'un autre côté, HORN-SAT est P-complet, ce qui signifie qu'il n'a pas d'algorithmes...