Résumé
Une preuve sans divulgation de connaissance, également appelée preuve « zero-knowledge », est un protocole entre un prouveur, qui détient un secret satisfaisant une certaine propriété, et une vérificatrice. À l'issue de l'échange, la vérificatrice est quasi certaine que le prouveur connaît le secret en question, mais n'a rien appris d'autre sur sa valeur. Les preuves zero-knowledge ont de nombreuses applications, notamment dans le cadre des blockchains, pour par exemple affirmer des faits sur des données privées (par exemple, garantir qu'un vote électronique est bien formé, sans révéler le vote) ; autoriser des actions tout en préservant l'anonymat de l'acteur ; et déléguer des calculs tout en garantissant que le résultat est correct.
Nous avons commencé ce cours par l'étude des protocoles Sigma, un patron de conception de protocoles zero-knowledge en trois interactions: mise en gage, défi et réponse. Nous avons ensuite énoncé les propriétés de sécurité de ces protocoles (complétude, correction spéciale et non-divulgation) et les avons illustrées à l'aide du protocole de Schnorr (connaissance d'un logarithme discret) et de sa généralisation, le protocole de Maurer (connaissance d'un antécédent par un morphisme). Enfin, nous avons vu comment transformer un protocole Sigma interactif en protocole non interactif à l'aide de l'heuristique de Fiat-Shamir.
La suite du cours a présenté une construction générique de « zk-SNARKs » : des preuves zero-knowledge, succintes (de petite taille) et non interactives de la connaissance d'une valeur satisfaisant une propriété. L'utilisation de circuits arithmétiques contraints permet d'exprimer de manière concise un grand nombre de propriétés. Nous avons vu comment représenter ces circuits contraints sous forme d'équations polynomiales appelées QAP (Quadratic Arithmetic Programs). Après un long détour par la preuve de propriétés de divisibilité de polynômes et l'évaluation homomorphe, chiffrée et authentifiée de polynômes, nous avons décrit le protocole Pinocchio (Parno et al., 2016), qui construit des preuves zk-SNARK pour des propriétés QAP arbitraires.
