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
| Mot | Ce que ça veut dire |
|---|---|
| Interactive | qui demande des messages dans les deux sens |
| Non interactive | un seul message que tout le monde peut vérifier |
| Fiat-Shamir | remplacer le défi par un hachage |
| Transcription | tout ce qui est envoyé pendant une preuve |
| Falsification | une 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
docker exec jupyter python3 steps/fiatshamir.pyAffiché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 interactif | Schnorr avec Fiat-Shamir | |
|---|---|---|
| Qui choisit c | Le vérificateur, au hasard | Un hachage de y, de t et du message |
| Messages | Trois, aller et retour | Un seul, t et s ensemble |
| Qui peut vérifier | Seulement le vérificateur qui a choisi c | Tout le monde, à tout moment |
| Qui est convaincu | Un seul vérificateur | Tous ceux qui vérifient |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À vous : falsifier face à un hachage faible
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
docker exec jupyter grep -n def zk.pyAffichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.