Preuve à divulgation nulle de connaissance

Une preuve à divulgation nulle de connaissance est une brique de base utilisée en cryptologie dans le cadre de l'authentification et de l'identification. Cette expression désigne un protocole sécurisé dans lequel une entité, nommée « fournisseur de preuve », prouve mathématiquement à une autre entité, le « vérificateur », qu'une proposition est vraie sans toutefois révéler d'autres informations que la véracité de la proposition. En pratique, ces schémas se présentent souvent sous la forme de protocoles de type « défi/réponse » (challenge-response). Le vérificateur et le fournisseur de preuve s'échangent des informations et le vérificateur contrôle si la réponse finale est positive ou négative. Les anglophones utilisent l'abréviation ZKIP pour Zero Knowledge Interactive proof. Il existe également des variantes sans interaction (non-interactive zero-knowledge proof). Celles-ci peuvent-être construites dans le modèle de l'oracle aléatoire par l'heuristique de Fiat-Shamir. Jean-Jacques Quisquater et Louis Guillou publient en 1989 un article intitulé « How to explain zero-knowledge protocols to your children » (ou « Comment expliquer à vos enfants les protocoles sans apport de connaissance » ). On y trouve une introduction pédagogique à la notion de preuve à divulgation nulle de connaissance, basée sur le conte « Ali Baba et les quarante voleurs ». On considère deux personnes : Peggy (prouveur) et Victor (vérificateur). On considère aussi une grotte avec une bifurcation : A et B. On peut passer de A à B ou de B à A en ouvrant une porte à l'aide d'un mot magique. Peggy veut prouver à Victor qu'elle connaît le mot magique pour ouvrir la porte mais ne veut pas que Victor l'apprenne. Il s'agit d'une « preuve de connaissance » (Peggy prouve à Victor qu'elle connaît la clé) mais sans « apport d'information » (Peggy conserve son secret). Pour ce faire, Peggy et Victor vont répéter plusieurs fois le scénario suivant. Engagement. Victor (en vert) attend à l'entrée de la caverne et ne voit pas l'intérieur du tunnel.