Plus facile à lire avec un fond crème, une teinte, plus de contraste ou un texte plus grand ? Choisissez vos couleurs et votre texte, une fois pour toutes les pages.

Leçon gratuite

Fiat-Shamir : une preuve que tous peuvent vérifier

Après cette leçon: Je peux calculer un défi de Fiat-Shamir et vérifier une preuve non interactive.

Leçon de 60 min2 commandesLab de preuves à divulgation nulle : engagements, Schnorr, Fiat-Shamir et Merkle en Python

Une preuve qui se passe de conversation

La transformation de Fiat-Shamir change une preuve interactive en preuve non interactive. Le prouveur fabrique toute la preuve seul, et n’importe qui peut la vérifier plus tard. Un hachage joue le rôle du vérificateur.

C’est ainsi que Schnorr devient une signature, et ainsi que la plupart des preuves à divulgation nulle sont publiées et vérifiées aujourd’hui.

À la fin de cette leçon

Remarque

Je peux calculer un défi de Fiat-Shamir et vérifier une preuve non interactive.

Mots-clés

MotCe que ça veut dire
Interactivequi demande des messages dans les deux sens
Non interactiveun seul message que tout le monde peut vérifier
Fiat-Shamirremplacer le défi par un hachage
Transcriptiontout ce qui est envoyé pendant une preuve
Falsificationune preuve qui passe sans le secret

Les cellules que les étudiants remplissent restent vides dans cet aperçu.

Un hachage peut choisir le défi

Schnorr interactif demande un vérificateur présent, ce qui gêne pour une preuve que beaucoup de gens vérifient plus tard.

Fiat-Shamir pose c égal au hachage de la clé publique, de t et d’un message, réduit modulo Q. Le prouveur ne peut pas choisir c, car c dépend de t et un hachage ne se dirige pas. Il doit donc toujours s’engager sur t d’abord. Tout le monde peut recalculer le même c.

Fabriquer et vérifier une preuve non interactive

Commande
docker exec jupyter python3 steps/fiatshamir.py

Affichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.

Lire ce que le labo a affiché

Le labo écrit en anglais. La preuve tient en deux nombres, t = 718 et s = 501. Le défi, calculé à partir du hachage, vaut 14. La preuve passe : True.

Les deux mêmes nombres avec un autre message donnent False, car le message est dans le hachage et donne un autre défi. Une preuve de Schnorr liée à un message est une signature de ce message.

Exemple travaillé : interactif et non interactif

Schnorr interactifSchnorr avec Fiat-Shamir
Qui choisit cLe vérificateur, au hasardUn hachage de y, de t et du message
MessagesTrois, aller et retourUn seul, t et s ensemble
Qui peut vérifierSeulement le vérificateur qui a choisi cTout le monde, à tout moment
Qui est convaincuUn seul vérificateurTous ceux qui vérifient

Les cellules que les étudiants remplissent restent vides dans cet aperçu.

À vous : falsifier face à un hachage faible

Code: python
import hashlib

P = 1019
Q = 509
G = 4
y = 227  # la clé publique de quelqu’un : nous ne connaissons pas son secret

def defi_faible(message):
    # Faux exprès : t est oublié dans le hachage.
    return int(hashlib.sha256(message.encode()).hexdigest(), 16) % Q

message = "Léa doit 5 à Tom"
c = defi_faible(message)
s = 123
t = pow(G, s, P) * pow(pow(y, c, P), -1, P) % P
print("c =", c, "t falsifié =", t, "s =", s)
print("le contrôle passe :", pow(G, s, P) == t * pow(y, c, P) % P)
# Corrigez : hachez str(t) + message, pour que t soit choisi avant de connaître c.

Hacher tout ce que verrait le vérificateur

Le code ci-dessus a oublié t dans le hachage. Le falsificateur a donc calculé c d’abord, choisi n’importe quel s, puis fabriqué un t qui va avec, comme le simulateur. Le contrôle a passé sans aucun secret.

La règle : hacher chaque valeur que le vérificateur aurait vue avant de choisir, soit le groupe, la clé publique, t et le message. De vrais systèmes ont été livrés avec cette erreur, alors vérifiez-la à l’œil.

Erreur fréquente

Attention

On croit souvent que n’importe quel hachage rend Fiat-Shamir sûr. Il n’est sûr que si le hachage couvre t et l’énoncé. Si t manque, un falsificateur choisit le défi d’abord et truque la preuve, comme le fait le simulateur.

Lister les fonctions de zk.py

Commande
docker exec jupyter grep -n def zk.py

Affichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.

À propos de ce labo et de sa source: Lab de preuves à divulgation nulle : engagements, Schnorr, Fiat-Shamir et Merkle en Python

Vous enseignez à une classe ? Proposez ce module à vos étudiants avec un guide de l'enseignant, des devoirs corrigés et un laboratoire pour chaque étudiant.