SC-15-Zero-Knowledge-Proofs-Python - Preuves a Divulgation Nulle

<< Formal Verification | Homomorphic Encryption >>

---

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez : 1. Comprendre les preuves a divulgation nulle (Zero-Knowledge Proofs) 2. Implementer le protocole de Schnorr from scratch 3. Comprendre la transformation de Fiat-Shamir (interactif -> non-interactif) 4. Explorer les Sigma protocols et le protocole de Chaum-Pedersen

Prerequis

• Python 3.10+ avec hashlib (stdlib)
• pycryptodome pour la generation de grands nombres premiers
• Notions de base en arithmetique modulaire

Duree estimee : 60 minutes

---

1. Introduction aux preuves a divulgation nulle

Qu’est-ce qu’une preuve a divulgation nulle ?

Une Zero-Knowledge Proof (ZKP) est un protocole cryptographique qui permet a un prouveur (Prover) de convaincre un verificateur (Verifier) qu’une affirmation est vraie, sans reveler aucune information au-dela de la veracite de l’affirmation elle-même.

L’analogie de la caverne d’Ali Baba

Imaginez une caverne en forme d’anneau avec une porte magique au fond. Peggy (le prouveur) connait le mot de passe de la porte. Victor (le verificateur) veut s’en assurer sans apprendre le mot de passe.

     Entree
       |
      / \
     A   B
      \ /
    [Porte]

1. Peggy entre dans la caverne par A ou B (au hasard, Victor ne voit pas)
2. Victor crie “sors par A” ou “sors par B” (au hasard)
3. Si Peggy connait le mot de passe, elle peut toujours sortir du bon cote
4. Si elle ne le connait pas, elle a 50% de chance d’echouer a chaque tour
5. Après N tours, la probabilite de tricher est de 2^(-N)

Trois proprietes fondamentales

Propriete	Description	Formellement
Completude	Si l’affirmation est vraie, le verificateur sera convaincu	Pr[Accept | vrai] = 1
Solidite	Si l’affirmation est fausse, le prouveur ne peut pas tricher	Pr[Accept | faux] <= 2^(-N)
Zero-knowledge	Le verificateur n’apprend rien de plus que la veracite	Simulation indistinguable

import random

def cave_simulation(knows_password: bool, num_rounds: int = 20) -> bool:
    """Simuler le protocole de la caverne d'Ali Baba.
    Retourne True si le verificateur est convaincu apres tous les rounds.
    """
    for round_num in range(num_rounds):
        # Peggy choisit un cote au hasard
        peggy_side = random.choice(["A", "B"])
        # Victor demande un cote au hasard
        victor_request = random.choice(["A", "B"])

        if peggy_side == victor_request:
            # Pas besoin de la porte, elle est deja du bon cote
            continue
        elif knows_password:
            # Peggy traverse la porte magique
            continue
        else:
            # Peggy ne peut pas traverser -> echec
            return False
    return True

# Simuler un prouveur honnete (connait le mot de passe)
print("ANALOGIE DE LA CAVERNE D'ALI BABA")
print("=" * 60)

honnete_succes = sum(cave_simulation(True, 20) for _ in range(1000))
print(f"Prouveur honnete  (1000 essais, 20 rounds) : {honnete_succes}/1000 reussis")

# Simuler un prouveur malhonnete (ne connait PAS le mot de passe)
malhonnete_succes = sum(cave_simulation(False, 20) for _ in range(1000))
print(f"Prouveur fraudeur (1000 essais, 20 rounds) : {malhonnete_succes}/1000 reussis")
print()
print(f"Probabilite theorique de fraude sur 20 rounds : 2^(-20) = {2**-20:.10f}")
print(f"-> Environ 1 chance sur {2**20:,} de tromper le verificateur")

ANALOGIE DE LA CAVERNE D'ALI BABA
============================================================
Prouveur honnete  (1000 essais, 20 rounds) : 1000/1000 reussis
Prouveur fraudeur (1000 essais, 20 rounds) : 0/1000 reussis

Probabilite theorique de fraude sur 20 rounds : 2^(-20) = 0.0000009537
-> Environ 1 chance sur 1,048,576 de tromper le verificateur

Interpretation

Le prouveur honnete reussit toujours (completude), tandis que le fraudeur echoue presque certainement après 20 rounds (solidite).

La propriete zero-knowledge vient du fait que Victor ne peut pas distinguer “Peggy connait le mot de passe” de “Peggy a eu de la chance sur le cote”. Victor n’apprend que “oui, elle sait” ou “non, elle ne sait pas”.

Ce principe se generalise a des problemes mathematiques utiles en cryptographie, comme le logarithme discret que nous explorons dans la section suivante.

---

2. ZKP du logarithme discret (version simplifiee)

Le problème du logarithme discret est fondamental en cryptographie :

Etant donne un groupe cyclique de générateur g, et une valeur y = g^x mod p, retrouver x est (en pratique) impossible pour de grands nombres premiers.

Un prouveur qui connait x (le “secret”) peut prouver qu’il le connait sans jamais le reveler, grace au protocole suivant :

Protocole interactif

1. Engagement (Commit) : Le prouveur choisit r aleatoire, calcule R = g^r mod p, envoie R
2. Defi (Challenge) : Le verificateur envoie un challenge aleatoire c
3. Reponse (Response) : Le prouveur calcule s = r + c*x mod q, envoie s
4. Verification : Le verificateur verifie que g^s == R * y^c (mod p)

Pourquoi ca marche ?

g^s = g^(r + c*x) = g^r * g^(c*x) = R * (g^x)^c = R * y^c  (mod p)

Le prouveur ne revele jamais x directement. La valeur s = r + c*x est “masquee” par le nonce aleatoire r, rendant impossible de deduire x.

Exécution du protocole interactif

Avec ces paramètres en place, executons le protocole en 4 étapes. A chaque round, le prouveur genere un nonce frais r, ce qui masque completement le secret x dans la reponse s = r + c*x.

# %% Cellule - Parametres Discrete Log avec import guards
# Guard: verification pycryptodome

try:
    from Crypto.Util.number import getPrime, getRandomRange
    from Crypto.Hash import SHA256
    CRYPTO_AVAILABLE = True
    print('pycryptodome disponible.')
except ImportError:
    CRYPTO_AVAILABLE = False
    print('pycryptodome non disponible. Install: pip install pycryptodome')

if CRYPTO_AVAILABLE:
    # Parametres pour le protocole Discrete Logarithm
    # p = nombre premier (ordre du groupe)
    # g = generateur du groupe
    # x = expose secret (discrete log)
    # h = g^x mod p (engagement)
    import random

    def generate_dlog_params(bits=256):
        # Genere les parametres pour un protocole base sur le logarithme discret
        p = getPrime(bits)
        g = getRandomRange(2, p - 1)
        x = getRandomRange(1, p - 1)  # Secret
        h = pow(g, x, p)              # Engagement public
        return p, g, x, h

    # Generation des parametres
    p, g, x, h = generate_dlog_params(bits=256)
    y = h          # cle publique / engagement = g^x mod p (notation des protocoles suivants)
    q = p - 1      # ordre du groupe multiplicatif Z_p* (Fermat: g^(p-1) == 1 mod p)

    print('Parametres Discrete Log generes:')
    print(f'  p (premier) = {hex(p)[:40]}...')
    print(f'  g (generateur) = {hex(g)[:40]}...')
    print('  x (secret) = NON REVELE')
    print(f'  h = g^x mod p = {hex(h)[:40]}...')
    print(f'Verification: g^x mod p == h : {pow(g, x, p) == h}')
else:
    print('Generation des parametres discrete log skippee (pycryptodome requis).')
# Protocole interactif du logarithme discret
from Crypto.Util.number import getRandomRange

def zkp_dlog_interactive(g, y, x, p, q):
    """Executer une ronde du protocole ZKP interactif.
    g, y, p, q : parametres publics
    x : secret du prouveur
    Retourne (succes, details)
    """
    # Etape 1 : Engagement (Prover)
    r = getRandomRange(1, q)  # Nonce aleatoire
    R = pow(g, r, p)          # Commitment

    # Etape 2 : Challenge (Verifier)
    c = getRandomRange(1, q)  # Challenge aleatoire

    # Etape 3 : Response (Prover)
    s = (r + c * x) % q       # Reponse

    # Etape 4 : Verification (Verifier)
    lhs = pow(g, s, p)        # g^s mod p
    rhs = (R * pow(y, c, p)) % p  # R * y^c mod p

    return lhs == rhs, {"R": R, "c": c, "s": s, "lhs": lhs, "rhs": rhs}


# Executer le protocole plusieurs fois
print("PROTOCOLE ZKP DU LOGARITHME DISCRET (INTERACTIF)")
print("=" * 60)

num_rounds = 10
all_valid = True

for i in range(num_rounds):
    valid, details = zkp_dlog_interactive(g, y, x, p, q)
    status = "OK" if valid else "ECHEC"
    print(f"  Round {i+1:2d} : g^s == R*y^c ? {status}")
    if not valid:
        all_valid = False

print()
verdict_final = "CONVAINCU" if all_valid else "ECHEC"
print(f"Resultat apres {num_rounds} rounds : {verdict_final}")
print(f"Probabilite de fraude : 2^(-{num_rounds}) = {2**-num_rounds:.2e}")
print()
print("Points cles :")
print("  - Le secret x n'a JAMAIS ete transmis au verificateur")
print("  - Chaque round utilise un nonce r different (aleatoire)")
print("  - s = r + c*x est masque par r, impossible de deduire x")

pycryptodome disponible.
Parametres Discrete Log generes:
  p (premier) = 0xd53edd08198341a44f3a4daa03e27e889a1427...
  g (generateur) = 0xcff1021ed80fa9d5002560b43bf8571cafe950...
  x (secret) = NON REVELE
  h = g^x mod p = 0x36ebd547446e31bbd7b97b3606d7444cf969b2...
Verification: g^x mod p == h : True
PROTOCOLE ZKP DU LOGARITHME DISCRET (INTERACTIF)
============================================================
  Round  1 : g^s == R*y^c ? OK
  Round  2 : g^s == R*y^c ? OK
  Round  3 : g^s == R*y^c ? OK
  Round  4 : g^s == R*y^c ? OK
  Round  5 : g^s == R*y^c ? OK
  Round  6 : g^s == R*y^c ? OK
  Round  7 : g^s == R*y^c ? OK
  Round  8 : g^s == R*y^c ? OK
  Round  9 : g^s == R*y^c ? OK
  Round 10 : g^s == R*y^c ? OK

Resultat apres 10 rounds : CONVAINCU
Probabilite de fraude : 2^(-10) = 9.77e-04

Points cles :
  - Le secret x n'a JAMAIS ete transmis au verificateur
  - Chaque round utilise un nonce r different (aleatoire)
  - s = r + c*x est masque par r, impossible de deduire x

Interpretation : Paramètres du groupe (version simplifiée)

La démo interactive ci-dessus (cellule 6) utilise un groupe multiplicatif simplifié, à visée pédagogique :

Paramètre	Rôle	Ce que la cellule 6 génère réellement
p (256 bits)	Module du groupe	Nombre premier aléatoire via getPrime(256) — pas un safe prime
q = p − 1 (256 bits)	Ordre du groupe multiplicatif Z_p*	Non premier (p − 1 est pair) ; c’est l’ordre du groupe complet
g (256 bits)	Générateur	Élément aléatoire de Z_p* via getRandomRange(2, p − 1)

Le protocole reste mathématiquement valide dans ce groupe complet : le petit théorème de Fermat garantit g^(p−1) ≡ 1 (mod p), donc la vérification g^s ≡ R · y^c (mod p) tient avec s = r + c·x mod (p−1). L’identification fonctionne, la preuve aussi.

Pourquoi cette version n’est pas suffisante en production ? Travailler dans Z_p* complet (d’ordre p−1 composite) expose aux attaques par sous-groupe petit (Pohlig-Hellman) : un attaquant décompose le logarithme discret modulo chaque facteur premier de p−1. La parade standard est le safe prime p = 2q + 1 (avec q premier), en se restreignant au sous-groupe d’ordre q via un générateur g = h² mod p. C’est précisément ce qu’implémente la section 3 ci-dessous (classe SchnorrZKP, cellule 12) : génération d’un vrai safe prime et d’un générateur d’ordre q premier.

Note : 256 bits est pédagogique ici. En production, on utilise des groupes d’ordre premier ≥ 256 bits (courbes 25519, RFC 7919) pour une sécurité équivalente à AES-128.

Et si le prouveur triche ?

Pour comprendre la solidite du protocole, voyons ce qui se passe quand un prouveur ne connait pas le secret x et tente de generer une reponse valide.

# Demonstration : un prouveur frauduleux echoue
print("TENTATIVE DE FRAUDE (prouveur ne connait PAS x)")
print("=" * 60)

def zkp_dlog_cheat(g, y, p, q):
    """Tentative de fraude : le prouveur ne connait pas x."""
    # Le fraudeur choisit un r au hasard
    r = getRandomRange(1, q)
    R = pow(g, r, p)

    # Challenge du verificateur
    c = getRandomRange(1, q)

    # Le fraudeur ne peut pas calculer s = r + c*x car il ne connait pas x
    # Il essaie un s au hasard
    s_fake = getRandomRange(1, q)

    lhs = pow(g, s_fake, p)
    rhs = (R * pow(y, c, p)) % p

    return lhs == rhs


num_attempts = 1000
frauds_reussies = sum(zkp_dlog_cheat(g, y, p, q) for _ in range(num_attempts))
print(f"Tentatives de fraude : {num_attempts}")
print(f"Fraudes reussies     : {frauds_reussies}")
print(f"-> La probabilite de deviner s correctement est 1/q ~ 2^(-{q.bit_length()})")
print("-> Un seul round suffit pour une securite de 128 bits avec de grands parametres")

TENTATIVE DE FRAUDE (prouveur ne connait PAS x)
============================================================
Tentatives de fraude : 1000
Fraudes reussies     : 0
-> La probabilite de deviner s correctement est 1/q ~ 2^(-256)
-> Un seul round suffit pour une securite de 128 bits avec de grands parametres

Interpretation

Scénario	Résultat	Explication
Prouveur honnete (connait x)	Toujours accepte	s = r + c*x verifie l’equation
Prouveur fraudeur (ne connait pas x)	Toujours rejete	Impossible de calculer s sans x

La securite repose sur le problème du logarithme discret : même en observant y = g^x, R = g^r, et s = r + c*x, il est calculatoirement infaisable de retrouver x.

Limitation de la version interactive : elle necessite un echange en temps reel entre le prouveur et le verificateur. La section suivante resout ce problème.

---

3. Protocole de Schnorr et transformation de Fiat-Shamir

Le protocole de Schnorr (1989) est la version formalisee du protocole de la section 2, avec une amelioration cruciale : la transformation de Fiat-Shamir qui le rend non-interactif.

Idee de Fiat-Shamir (1986)

Au lieu d’attendre un challenge aleatoire du verificateur, le prouveur le genere lui-même a partir du hash de l’engagement :

c = SHA-256(g || y || R)

Cela fonctionne car le hash est imprevisible et lie a l’engagement R. Le prouveur ne peut pas choisir c a l’avance (il faudrait inverser SHA-256).

Consequence fondamentale

La preuve non-interactive (R, s) est en fait une signature numérique ! Les signatures de Schnorr sont exactement des ZKP non-interactives du logarithme discret. C’est la base de nombreux schemas modernes (BIP-340/Taproot dans Bitcoin).

from Crypto.Util.number import getPrime, getRandomRange
from Crypto.Hash import SHA256

class SchnorrZKP:
    """Implementation du protocole de Schnorr (interactif et non-interactif)."""

    def __init__(self, bits=128):
        """Generer les parametres du groupe."""
        while True:
            self.q = getPrime(bits)
            self.p = 2 * self.q + 1
            if pow(2, self.p - 1, self.p) == 1:
                break
        while True:
            h = getRandomRange(2, self.p - 1)
            self.g = pow(h, 2, self.p)
            if self.g > 1:
                break

    def keygen(self):
        """Generer une paire cle privee / cle publique."""
        x = getRandomRange(1, self.q)  # Cle privee
        y = pow(self.g, x, self.p)     # Cle publique
        return x, y

    # --- Version interactive ---

    def prove_interactive_step1(self, x):
        """Prouveur : etape 1 - engagement."""
        r = getRandomRange(1, self.q)
        R = pow(self.g, r, self.p)
        return r, R

    def verify_challenge(self):
        """Verificateur : generer un challenge aleatoire."""
        return getRandomRange(1, self.q)

    def prove_interactive_step3(self, r, c, x):
        """Prouveur : etape 3 - reponse."""
        s = (r + c * x) % self.q
        return s

    def verify_interactive(self, y, R, c, s):
        """Verificateur : verification finale."""
        lhs = pow(self.g, s, self.p)
        rhs = (R * pow(y, c, self.p)) % self.p
        return lhs == rhs

    # --- Version non-interactive (Fiat-Shamir) ---

    def _fiat_shamir_challenge(self, y, R, message=b""):
        """Calculer le challenge via hash (transformation de Fiat-Shamir)."""
        h = SHA256.new()
        h.update(self.g.to_bytes(256, 'big'))
        h.update(y.to_bytes(256, 'big'))
        h.update(R.to_bytes(256, 'big'))
        h.update(message)
        # Convertir le hash en entier modulo q
        return int.from_bytes(h.digest(), 'big') % self.q

    def prove_non_interactive(self, x, y, message=b""):
        """Preuve non-interactive (Fiat-Shamir)."""
        r = getRandomRange(1, self.q)
        R = pow(self.g, r, self.p)
        c = self._fiat_shamir_challenge(y, R, message)
        s = (r + c * x) % self.q
        return R, s  # La preuve = (R, s)

    def verify_non_interactive(self, y, R, s, message=b""):
        """Verification non-interactive."""
        c = self._fiat_shamir_challenge(y, R, message)
        lhs = pow(self.g, s, self.p)
        rhs = (R * pow(y, c, self.p)) % self.p
        return lhs == rhs


# Instancier le protocole
schnorr = SchnorrZKP(bits=128)
x, y = schnorr.keygen()

print("PROTOCOLE DE SCHNORR")
print("=" * 60)
print(f"Parametres : p={str(schnorr.p)[:30]}... ({schnorr.p.bit_length()} bits)")
print(f"Cle publique y = g^x mod p")
print()

PROTOCOLE DE SCHNORR
============================================================
Parametres : p=368594293902468330298745254985... (129 bits)
Cle publique y = g^x mod p

Utilisation : interactif vs non-interactif

La classe SchnorrZKP ci-dessus implemente les deux variantes. Comparons les en exécution pour voir la différence pratique : l’interactif necessite 3 messages, le non-interactif un seul.

# Comparaison interactive vs non-interactive
print("COMPARAISON : INTERACTIF vs NON-INTERACTIF (Fiat-Shamir)")
print("=" * 60)

# 1. Version interactive
print("\n--- Version INTERACTIVE ---")
print("  Etape 1 (Prouveur -> Verificateur) : envoyer R")
r, R = schnorr.prove_interactive_step1(x)
print(f"    R = g^r = {str(R)[:30]}...")

print("  Etape 2 (Verificateur -> Prouveur) : envoyer c")
c = schnorr.verify_challenge()
print(f"    c = {str(c)[:30]}...")

print("  Etape 3 (Prouveur -> Verificateur) : envoyer s")
s = schnorr.prove_interactive_step3(r, c, x)
print(f"    s = r + c*x mod q = {str(s)[:30]}...")

valid_inter = schnorr.verify_interactive(y, R, c, s)
verdict_inter = "OUI" if valid_inter else "NON"
print(f"  Verification : g^s == R*y^c ? {verdict_inter}")
print(f"  -> Necessite 3 messages (2 allers-retours)")

# 2. Version non-interactive (Fiat-Shamir)
print("\n--- Version NON-INTERACTIVE (Fiat-Shamir) ---")
message = b"Je prouve que je connais x"
R_ni, s_ni = schnorr.prove_non_interactive(x, y, message)
print(f"  Preuve (R, s) calculee localement")
print(f"    R = {str(R_ni)[:30]}...")
print(f"    s = {str(s_ni)[:30]}...")
print(f"    c = SHA256(g || y || R || message) (calcule automatiquement)")

valid_ni = schnorr.verify_non_interactive(y, R_ni, s_ni, message)
verdict_ni = "VALIDE" if valid_ni else "INVALIDE"
print(f"  Verification : {verdict_ni}")
print(f"  -> Un seul message, pas besoin d'interaction !")

# 3. Tentative de falsification du message
print("\n--- Falsification du message ---")
fake_message = b"Message modifie"
valid_fake = schnorr.verify_non_interactive(y, R_ni, s_ni, fake_message)
verdict_fake = "VALIDE" if valid_fake else "INVALIDE"
print(f"  Verification avec message modifie : {verdict_fake}")
print(f"  -> La preuve est liee au message (c'est une signature !)")

COMPARAISON : INTERACTIF vs NON-INTERACTIF (Fiat-Shamir)
============================================================

--- Version INTERACTIVE ---
  Etape 1 (Prouveur -> Verificateur) : envoyer R
    R = g^r = 146469142305875860307188168402...
  Etape 2 (Verificateur -> Prouveur) : envoyer c
    c = 125575800894214925790201251586...
  Etape 3 (Prouveur -> Verificateur) : envoyer s
    s = r + c*x mod q = 181138356321469463681048183313...
  Verification : g^s == R*y^c ? OUI
  -> Necessite 3 messages (2 allers-retours)

--- Version NON-INTERACTIVE (Fiat-Shamir) ---
  Preuve (R, s) calculee localement
    R = 153997758336764344879339310484...
    s = 144655119875588345405590637582...
    c = SHA256(g || y || R || message) (calcule automatiquement)
  Verification : VALIDE
  -> Un seul message, pas besoin d'interaction !

--- Falsification du message ---
  Verification avec message modifie : INVALIDE
  -> La preuve est liee au message (c'est une signature !)

Interpretation : Interactif vs Non-interactif

Aspect	Interactif	Non-interactif (Fiat-Shamir)
Messages	3 (R, c, s) sur 2 allers-retours	1 seul message (R, s)
Challenge	Verificateur genere c aleatoirement	Hash SHA-256 de (g, y, R, message)
Temps reel	Requis (interaction synchrone)	Non (asynchrone, stockable)
Falsification message	Possible si verificateur compromis	Impossible (hash lie au message)

Points cles : - La version non-interactive transforme la ZKP en signature numérique : le message est lie a la preuve - Changer un seul octet du message invalide la preuve (le challenge change completement) - Bitcoin Taproot (BIP-340) utilise exactement ce schema pour les transactions

Exercice : Implementer la transformation de Fiat-Shamir

La classe SchnorrZKP ci-dessus implemente la transformation de Fiat-Shamir pour vous. Pour vraiment comprendre pourquoi elle rend la preuve non-interactive, implémentez le coté prouveur vous-meme.

L’idee centrale : dans la version interactive, le vérificateur tire un challenge aleatoire c. Dans la version non-interactive (Fiat-Shamir), le prouveur derive lui-meme c comme un hash de son engagement et du message : c = H(g, y, R, message) mod q. Comme il ne peut pas prédire ce hash avant d’avoir choisi R, la sécurité est préservée sans interaction.

Objectif : completer prove_fiat_shamir(g, p, q, x, message) qui retourne la preuve (R, s). La fonction challenge_fiat_shamir (le hash) est fournie.

Étape 1 : tirer un nonce r aleatoire dans [1, q), calculer l’engagement R = pow(g, r, p). Étape 2 : cle publique y = pow(g, x, p), puis le challenge non-interactif c = challenge_fiat_shamir(g, y, R, message, q). Étape 3 : reponse s = (r + c * x) % q.

# Exercice : Implementer la transformation de Fiat-Shamir (prouveur non-interactif)
# TODO etudiant : implementer prove_fiat_shamir. La cle = challenge = hash, pas aleatoire.

from Crypto.Hash import SHA256
from Crypto.Util.number import getRandomRange

def challenge_fiat_shamir(g, y, R, message, q):
    """Challenge non-interactif = hash SHA-256 de (g, y, R, message). Fonction fournie."""
    h = SHA256.new()
    h.update(str(g).encode())
    h.update(str(y).encode())
    h.update(str(R).encode())
    h.update(message.encode())
    return int(h.hexdigest(), 16) % q

def prove_fiat_shamir(g, p, q, x, message):
    """Prouver la connaissance de x (cle privee) de facon non-interactive.

    Retourner la preuve (R, s) ou c = H(g, y, R, message) mod q remplace le
    challenge aleatoire du verificateur. NE PAS demander de challenge externe.
    """
    # Etape 1 : nonce r aleatoire dans [1, q), engagement R = pow(g, r, p)
    # Etape 2 : cle publique y = pow(g, x, p), challenge c = challenge_fiat_shamir(...)
    # Etape 3 : reponse s = (r + c * x) % q
    return (0, 0)  # TODO etudiant : implementer

print("Exercice a completer")

Exercice a completer

Exercice 2 : Verification multi-rounds du protocole de Schnorr

Implementez une fonction qui execute le protocole de Schnorr interactif sur N rounds et mesure la probabilite de detection de fraude.

Objectif : Completer la fonction schnorr_multiround_test qui teste le protocole de Schnorr sur plusieurs rounds avec un prouveur honnete et un prouveur frauduleux.

Indice : - Reutilisez les méthodes de la classe SchnorrZKP instanciee ci-dessus - Un prouveur honnete suit les 3 étapes normalement - Un prouveur frauduleux genere une reponse aleatoire pour s

Étapes : 1. Boucler sur num_rounds et executer les 4 étapes du protocole 2. Pour le cas frauduleux, remplacer s par getRandomRange(1, q) 3. Retourner le résultat global et les details par round

# Exercice 2 : Verification multi-rounds du protocole de Schnorr
# TODO etudiant : completez la fonction schnorr_multiround_test

def schnorr_multiround_test(schnorr_instance, x, y, num_rounds, honest=True):
    """Execute le protocole de Schnorr interactif sur N rounds.

    Args:
        schnorr_instance: instance de SchnorrZKP
        x: cle privee
        y: cle publique
        num_rounds: nombre de rounds
        honest: True pour prouveur honnete, False pour fraudeur

    Returns:
        tuple: (reussite_globale, liste_de_details_par_round)
    """
    # TODO etudiant : implementez le protocole multi-rounds
    # Indice : pour chaque round, suivez les 4 etapes :
    #   1. r, R = schnorr_instance.prove_interactive_step1(x)  [prouveur]
    #   2. c = schnorr_instance.verify_challenge()              [verificateur]
    #   3. s = schnorr_instance.prove_interactive_step3(r, c, x) [prouveur]
    #   4. valid = schnorr_instance.verify_interactive(y, R, c, s) [verificateur]
    # Etape 1 : boucler sur num_rounds
    # Etape 2 : si honest=True, utiliser x normalement ; si honest=False,
    #           remplacer s par une valeur aleatoire (getRandomRange(1, schnorr_instance.q))
    # Etape 3 : retourner (True, details) si tous les rounds passent, (False, details) sinon
    return None, []  # TODO etudiant


# Validation
result = schnorr_multiround_test(schnorr, x, y, 10, honest=True)
if result[0] is not None:
    success, details = result
    print(f"Prouveur honnete (10 rounds) : {'CONVAINCU' if success else 'ECHEC'}")
    print(f"Details : {len(details)} rounds executes")
else:
    print("Exercice a completer")

Exercice a completer

ZKP = Signature numérique

Un résultat remarquable : la preuve non-interactive (R, s) est exactement une signature de Schnorr sur un message. Signer, c’est prouver la connaissance de la cle privee sans la reveler.

# La preuve non-interactive de Schnorr EST une signature
print("SCHNORR : ZKP = SIGNATURE")
print("=" * 60)
print()
print("Schema de signature de Schnorr :")
print("  Signer(x, message)   -> (R, s) = preuve ZKP non-interactive")
print("  Verifier(y, message, R, s) -> vrai/faux")
print()

# Signer plusieurs messages
messages = [
    b"Transferer 10 ETH a 0xBob",
    b"Approuver le contrat 0xDefi",
    b"Voter OUI pour la proposition 42",
]

print("Signatures de Schnorr sur differents messages :")
for msg in messages:
    R_sig, s_sig = schnorr.prove_non_interactive(x, y, msg)
    valid = schnorr.verify_non_interactive(y, R_sig, s_sig, msg)
    print(f"  Message  : {msg.decode()}")
    print(f"  Sig (R)  : {str(R_sig)[:30]}...")
    print(f"  Valide   : {valid}")
    print()

print("Points cles :")
print("  - Chaque signature a un R different (nonce aleatoire)")
print("  - La verification ne necessite que la cle publique y")
print("  - Bitcoin utilise les signatures Schnorr depuis Taproot (BIP-340)")
print("  - Avantage sur ECDSA : linearite -> aggregation de signatures possible")

SCHNORR : ZKP = SIGNATURE
============================================================

Schema de signature de Schnorr :
  Signer(x, message)   -> (R, s) = preuve ZKP non-interactive
  Verifier(y, message, R, s) -> vrai/faux

Signatures de Schnorr sur differents messages :
  Message  : Transferer 10 ETH a 0xBob
  Sig (R)  : 649330683848833159740118046327...
  Valide   : True

  Message  : Approuver le contrat 0xDefi
  Sig (R)  : 157229905322640983938410499110...
  Valide   : True

  Message  : Voter OUI pour la proposition 42
  Sig (R)  : 244740713708504899984824621709...
  Valide   : True

Points cles :
  - Chaque signature a un R different (nonce aleatoire)
  - La verification ne necessite que la cle publique y
  - Bitcoin utilise les signatures Schnorr depuis Taproot (BIP-340)
  - Avantage sur ECDSA : linearite -> aggregation de signatures possible

Interpretation

La transformation de Fiat-Shamir est un résultat fondamental en cryptographie :

Aspect	Interactif	Non-interactif (Fiat-Shamir)
Messages	3 (aller-retour)	1 (prouveur -> verificateur)
Challenge	Aleatoire (verificateur)	Hash déterministe (SHA-256)
Utilisation	Identification temps reel	Signatures, blockchain
Securite	Random Oracle Model	CRS Model (+ hash)

Consequence pratique : une preuve ZKP non-interactive peut etre verifiee par n’importe qui, a n’importe quel moment, sans interaction avec le prouveur. C’est exactement ce dont on a besoin pour les transactions blockchain.

---

4. Sigma Protocols

Les protocoles de Schnorr et du logarithme discret sont des cas particuliers d’une famille plus large : les Sigma protocols (protocoles en 3 étapes).

Structure générale

Tout Sigma protocol suit le schema :

Prouveur                          Verificateur
  |                                    |
  |--- (1) Engagement (a) ----------->|
  |                                    |
  |<-- (2) Challenge (c) -------------|  (forme Sigma: la lettre grecque)
  |                                    |
  |--- (3) Reponse (z) ------------->|
  |                                    |
  |          Verification : V(a, c, z) = vrai/faux

La forme du diagramme d’echange ressemble a la lettre grecque Sigma, d’ou le nom.

Protocole de Chaum-Pedersen

Le protocole de Chaum-Pedersen (1992) prouve que deux logarithmes discrets sont egaux sans reveler leur valeur :

Prouver que log_g(y1) == log_h(y2) sans reveler l’exposant commun x

Ou : y1 = g^x mod p et y2 = h^x mod p

Ceci est utile pour les votes electroniques, les transferts confidentiels, et les preuves d’egalite de Diffie-Hellman.

from Crypto.Util.number import getRandomRange
from Crypto.Hash import SHA256

class ChaumPedersen:
    """Protocole de Chaum-Pedersen : prouver log_g(y1) == log_h(y2).
    Utilise les memes parametres de groupe que Schnorr.
    """

    def __init__(self, p, q, g):
        self.p = p
        self.q = q
        self.g = g
        # Generer un second generateur h (independant de g)
        while True:
            k = getRandomRange(2, q)
            self.h = pow(g, k, p)
            if self.h > 1 and self.h != g:
                break

    def setup(self, x):
        """Calculer y1 = g^x et y2 = h^x."""
        y1 = pow(self.g, x, self.p)
        y2 = pow(self.h, x, self.p)
        return y1, y2

    def prove(self, x, y1, y2):
        """Generer la preuve (non-interactive via Fiat-Shamir)."""
        # Engagement : r aleatoire, R1 = g^r, R2 = h^r
        r = getRandomRange(1, self.q)
        R1 = pow(self.g, r, self.p)
        R2 = pow(self.h, r, self.p)

        # Challenge (Fiat-Shamir)
        hasher = SHA256.new()
        for val in [self.g, self.h, y1, y2, R1, R2]:
            hasher.update(val.to_bytes(256, 'big'))
        c = int.from_bytes(hasher.digest(), 'big') % self.q

        # Reponse
        s = (r + c * x) % self.q

        return R1, R2, s

    def verify(self, y1, y2, R1, R2, s):
        """Verifier la preuve."""
        # Recalculer le challenge
        hasher = SHA256.new()
        for val in [self.g, self.h, y1, y2, R1, R2]:
            hasher.update(val.to_bytes(256, 'big'))
        c = int.from_bytes(hasher.digest(), 'big') % self.q

        # Verifier les deux equations simultanement
        check1 = pow(self.g, s, self.p) == (R1 * pow(y1, c, self.p)) % self.p
        check2 = pow(self.h, s, self.p) == (R2 * pow(y2, c, self.p)) % self.p

        return check1 and check2


# Utiliser les parametres de Schnorr
cp = ChaumPedersen(schnorr.p, schnorr.q, schnorr.g)

# Le secret x et les deux "cles publiques"
secret_x = getRandomRange(1, schnorr.q)
y1, y2 = cp.setup(secret_x)

print("PROTOCOLE DE CHAUM-PEDERSEN")
print("=" * 60)
print(f"Secret x : {str(secret_x)[:30]}... (cache)")
print(f"y1 = g^x : {str(y1)[:30]}...")
print(f"y2 = h^x : {str(y2)[:30]}...")
print(f"\nObjectif : prouver que log_g(y1) == log_h(y2) sans reveler x")
print()

PROTOCOLE DE CHAUM-PEDERSEN
============================================================
Secret x : 405467132589575281581442046676... (cache)
y1 = g^x : 120877331535270250002695741082...
y2 = h^x : 776145906254379340207988060128...

Objectif : prouver que log_g(y1) == log_h(y2) sans reveler x

Verification et test de solidite

Verifions que la preuve passe pour des logarithmes egaux, et echoue quand les logarithmes sont différents (le prouveur tente de prouver une affirmation fausse).

# Generer et verifier la preuve de Chaum-Pedersen
R1, R2, s = cp.prove(secret_x, y1, y2)
valid = cp.verify(y1, y2, R1, R2, s)

print("VERIFICATION CHAUM-PEDERSEN")
print("=" * 60)
print(f"Preuve (R1, R2, s) :")
print(f"  R1 = {str(R1)[:30]}...")
print(f"  R2 = {str(R2)[:30]}...")
print(f"  s  = {str(s)[:30]}...")
print(f"\nVerification : g^s == R1*y1^c  ET  h^s == R2*y2^c")
verdict_cp = "VALIDE" if valid else "INVALIDE"
print(f"Resultat : {verdict_cp}")
print()

# Test avec des exposants differents (la preuve doit echouer)
print("--- Test avec exposants differents ---")
x_diff = getRandomRange(1, schnorr.q)
y2_fake = pow(cp.h, x_diff, cp.p)  # y2 = h^(x_diff) avec x_diff != x

# Tenter de prouver avec le mauvais secret
R1_f, R2_f, s_f = cp.prove(secret_x, y1, y2_fake)
valid_fake = cp.verify(y1, y2_fake, R1_f, R2_f, s_f)
print(f"y1 = g^x, y2 = h^x_diff (x != x_diff)")
verdict_fake_cp = "VALIDE" if valid_fake else "INVALIDE"
print(f"La preuve avec le secret x pour y2 = h^x_diff : {verdict_fake_cp}")
print()
print("-> La preuve ne fonctionne que si les deux logarithmes sont identiques")
print()
print("Applications :")
print("  - Vote electronique : prouver qu'un bulletin chiffre est bien forme")
print("  - Transferts confidentiels : prouver qu'un montant est conserve")
print("  - Echange de cles : prouver la coherence de Diffie-Hellman")

VERIFICATION CHAUM-PEDERSEN
============================================================
Preuve (R1, R2, s) :
  R1 = 127221726687423160020668329665...
  R2 = 702184564413600230489677654627...
  s  = 248982706694560429464616227450...

Verification : g^s == R1*y1^c  ET  h^s == R2*y2^c
Resultat : VALIDE

--- Test avec exposants differents ---
y1 = g^x, y2 = h^x_diff (x != x_diff)
La preuve avec le secret x pour y2 = h^x_diff : INVALIDE

-> La preuve ne fonctionne que si les deux logarithmes sont identiques

Applications :
  - Vote electronique : prouver qu'un bulletin chiffre est bien forme
  - Transferts confidentiels : prouver qu'un montant est conserve
  - Echange de cles : prouver la coherence de Diffie-Hellman

Interpretation : Verification Chaum-Pedersen

Test	Résultat	Explication
Logarithmes egaux (x identique)	VALIDE	Les deux equations g^s == R1*y1^c et h^s == R2*y2^c sont satisfaites
Logarithmes différents (x != x_diff)	INVALIDE	La seconde equation echoue car y2 = h^x_diff mais la preuve utilise x

Points cles : - Chaum-Pedersen verifie deux equations simultanement avec le même challenge c - Le prouveur demontre que le même exposant x est utilise pour g^x et h^x - Applications directes : vote electronique (preuve de bulletin bien forme), coherence Diffie-Hellman, transferts confidentiels - La solidite repose sur le fait qu’il est impossible de satisfaire les deux equations si les exposants différent

Notion de OR-proofs

Les Sigma protocols se composent naturellement :

• AND-proof : prouver que l’on connait x1 ET x2 (facile : executer deux preuves)
• OR-proof : prouver que l’on connait x1 OU x2 sans reveler lequel

L’OR-proof est plus subtile. L’idee est de simuler la branche que l’on ne connait pas (grace a la propriete zero-knowledge) et de calculer la vraie preuve pour l’autre branche, en liant les deux challenges par c = c1 + c2.

Prouveur connait x1 (mais pas x2) :
  1. Simuler la preuve pour x2 : choisir c2, s2, calculer R2 en arriere
  2. Calculer R1 honnetement avec r1 aleatoire
  3. Recevoir le challenge global c
  4. Calculer c1 = c - c2, puis s1 = r1 + c1*x1
  -> Le verificateur ne peut pas distinguer quelle branche est simulee

Applications : systèmes de vote anonyme (prouver que mon bulletin est 0 ou 1 sans dire lequel), ring signatures (Monero).

Demonstration : construire un OR-proof (Cramer-Damgard-Schoenmakers)

La cellule suivante implemente l’OR-proof enonce ci-dessus – c’est le seul protocole Sigma de cette section qui n’etait jusqu’ici que decrit en prose. On prouve « je connais log_g(y1) OU log_g(y2) » sans reveler lequel des deux secrets est connu, en reutilisant le groupe de Schnorr (p = 2q+1 premier sur, generateur g d’ordre q).

Astuce cles (simulation de la branche inconnue) : le prouveur ne connait le secret que d’une seule branche (mettons x1 tel que y1 = g^x1). Pour l’autre branche (y2), il simule une preuve de Schnorr valide – il choisit c2 et s2 aleatoirement, puis calcule R2 = g^{s2} * y2^{q-c2} qui satisfait l’equation de verification par construction. Pour la branche connue, il engage honnetement R1 = g^{r1}. Le challenge global c = H(g, y1, y2, R1, R2) (Fiat-Shamir) contraint alors c1 = c - c2, d’ou la reponse s1 = r1 + c1*x1.

Pourquoi c’est zero-knowledge : c2 etant uniforme, c1 = c - c2 l’est aussi – le verificateur ne peut pas distinguer la branche honnete de la branche simulee (indistinguabilite). La solidite (soundness) vient de ce qu’un tricheur ne connaissant ni x1 ni x2 devrait produire c1 + c2 = H(...) sans controler les engagements R1, R2, infaisable face a un oracle aleatoire.

Note : les valeurs c1, c2 affichees changent a chaque execution (le groupe et les nonces sont tirees aleatoirement) – c’est inherant a la cryptographie ZKP (la fraicheur aleatoire EST la garantie de zero-knowledge). Ce qui est deterministe, ce sont les verdicts : branche connue -> VALIDE, preuve falsifiee -> INVALIDE.

from Crypto.Util.number import getRandomRange
from Crypto.Hash import SHA256


class ORProofZKP:
    """OR-proof (Cramer-Damgard-Schoenmakers 1994) : prouver qu'on connait
    le log discret de y1 OU celui de y2, SANS reveler lequel des deux.
    Reutilise les parametres du groupe de Schnorr (p=2q+1 premier sur, g d'ordre q)."""

    def __init__(self, p, q, g):
        self.p, self.q, self.g = p, q, g

    def _challenge(self, y1, y2, R1, R2):
        """Challenge global via Fiat-Shamir (hash de tous les engagements)."""
        h = SHA256.new()
        for val in (self.g, y1, y2, R1, R2):
            h.update(val.to_bytes(256, 'big'))
        return int.from_bytes(h.digest(), 'big') % self.q

    def prove(self, known_idx, x_known, y1, y2):
        """known_idx in {1, 2} : le prouveur connait x_known = log_g(y_{known_idx}).
        L'autre branche est SIMULEE (le prouveur ne la connait pas), la branche
        connue est honnete. (R1, R2) sont places en position fixe pour le verificateur."""
        y_other = y2 if known_idx == 1 else y1
        # 1. Simuler la branche 'other' : choisir c_other, s_other, en deduire R_other
        c_other = getRandomRange(1, self.q)
        s_other = getRandomRange(1, self.q)
        R_other = (pow(self.g, s_other, self.p) * pow(y_other, self.q - c_other, self.p)) % self.p
        # 2. Branche honnete : engagement R_known = g^r
        r_known = getRandomRange(1, self.q)
        R_known = pow(self.g, r_known, self.p)
        # 3. Assembler (R1, R2) en position fixe + challenge global
        if known_idx == 1:
            R1, R2 = R_known, R_other
        else:
            R1, R2 = R_other, R_known
        c = self._challenge(y1, y2, R1, R2)
        c_known = (c - c_other) % self.q          # la somme c1+c2 doit egaler c
        s_known = (r_known + c_known * x_known) % self.q
        # 4. Renvoyer les champs en position fixe (y1->slot1, y2->slot2)
        if known_idx == 1:
            return {"R1": R1, "R2": R2, "c1": c_known, "c2": c_other,
                    "s1": s_known, "s2": s_other}
        return {"R1": R1, "R2": R2, "c1": c_other, "c2": c_known,
                "s1": s_other, "s2": s_known}

    def verify(self, y1, y2, proof):
        """Le verificateur reconstruit les engagements et verifie c1 + c2 == c."""
        R1, R2 = proof["R1"], proof["R2"]
        c1, c2, s1, s2 = proof["c1"], proof["c2"], proof["s1"], proof["s2"]
        R1p = (pow(self.g, s1, self.p) * pow(y1, self.q - c1, self.p)) % self.p
        R2p = (pow(self.g, s2, self.p) * pow(y2, self.q - c2, self.p)) % self.p
        c_prime = self._challenge(y1, y2, R1p, R2p)
        return (c1 + c2) % self.q == c_prime


# Reutiliser le groupe de Schnorr (p=2q+1, g d'ordre q)
or_pf = ORProofZKP(schnorr.p, schnorr.q, schnorr.g)

# Deux cles publiques : le prouveur connait le secret de la 1ere, pas de la 2eme
or_x1 = getRandomRange(1, schnorr.q);  or_y1 = pow(schnorr.g, or_x1, schnorr.p)
or_x2 = getRandomRange(1, schnorr.q);  or_y2 = pow(schnorr.g, or_x2, schnorr.p)

print("OR-PROOF (CRAMER-DAMGARD-SCHOENMAKERS 1994)")
print("=" * 60)
print("Statement public : je connais log_g(y1) OU log_g(y2)")
print(f"  or_y1 = g^or_x1  (le prouveur connait or_x1)")
print(f"  or_y2 = g^or_x2  (le prouveur NE connait PAS or_x2)")
print()

# Cas 1 : le prouveur connait or_x1 (branche 1 honnete, branche 2 simulee)
proof1 = or_pf.prove(1, or_x1, or_y1, or_y2)
v1 = or_pf.verify(or_y1, or_y2, proof1)
print(f"Cas 1 - prouveur connait or_x1 (branche 1) : {'VALIDE' if v1 else 'INVALIDE'}")
print("  -> Le verificateur accepte, SANS savoir si c'etait or_x1 ou or_x2")

# Cas 2 : symetrique, le prouveur connait or_x2 (branche 2 honnete)
proof2 = or_pf.prove(2, or_x2, or_y1, or_y2)
v2 = or_pf.verify(or_y1, or_y2, proof2)
print(f"Cas 2 - prouveur connait or_x2 (branche 2) : {'VALIDE' if v2 else 'INVALIDE'}")
print("  -> Symetrique : la preuve est aussi valable depuis l'autre branche")

# Cas 3 : preuve truquee (on falsifie s1)
proof_fake = dict(proof1)
proof_fake["s1"] = (proof1["s1"] + 1) % schnorr.q
v3 = or_pf.verify(or_y1, or_y2, proof_fake)
print(f"Cas 3 - preuve truquee (s1 falsifie)      : {'VALIDE' if v3 else 'INVALIDE'}")
print("  -> Modifier s1 casse l'equation de Schnorr -> rejet")
print()

# Indistinguabilite : c1 et c2 sont uniformes, le verificateur ne sait pas
print("Indistinguabilite :")
print(f"  c1 = {proof1['c1']}")
print(f"  c2 = {proof1['c2']}")
print("  (c1, c2) sont uniformement aleatoires ; le verificateur ne peut pas")
print("  determiner quelle branche etait honnete et laquelle etait simulee.")
print()
print("Applications : vote anonyme (prouver 'mon bulletin est 0 OU 1' sans")
print("  dire lequel), signatures en anneau (ring signatures, Monero).")

OR-PROOF (CRAMER-DAMGARD-SCHOENMAKERS 1994)
============================================================
Statement public : je connais log_g(y1) OU log_g(y2)
  or_y1 = g^or_x1  (le prouveur connait or_x1)
  or_y2 = g^or_x2  (le prouveur NE connait PAS or_x2)

Cas 1 - prouveur connait or_x1 (branche 1) : VALIDE
  -> Le verificateur accepte, SANS savoir si c'etait or_x1 ou or_x2
Cas 2 - prouveur connait or_x2 (branche 2) : VALIDE
  -> Symetrique : la preuve est aussi valable depuis l'autre branche
Cas 3 - preuve truquee (s1 falsifie)      : INVALIDE
  -> Modifier s1 casse l'equation de Schnorr -> rejet

Indistinguabilite :
  c1 = 173715152155086992504867928616150111419
  c2 = 78732757464543599505291839292615484734
  (c1, c2) sont uniformement aleatoires ; le verificateur ne peut pas
  determiner quelle branche etait honnete et laquelle etait simulee.

Applications : vote anonyme (prouver 'mon bulletin est 0 OU 1' sans
  dire lequel), signatures en anneau (ring signatures, Monero).

---

5. zk-SNARKs : vue d’ensemble

Les protocoles vus jusqu’ici prouvent des relations algebriques simples (logarithme discret, egalite de logarithmes). Les zk-SNARKs generalisent les ZKP a des calculs arbitraires.

Qu’est-ce qu’un zk-SNARK ?

zk-SNARK = Zero-Knowledge Succinct Non-interactive ARgument of Knowledge

Composante	Signification
Zero-Knowledge	Ne revele rien au-dela de la veracite
Succinct	Preuve courte (~200 octets), verification rapide (~ms)
Non-interactive	Pas d’echange entre prouveur et verificateur
ARgument	Securite computationnelle (pas information-théorique)
of Knowledge	Le prouveur connait reellement le temoin (extractabilite)

Pipeline de construction

Programme -> Circuit Arithmetique -> R1CS -> QAP -> Preuve

1. Circuit arithmetique : le calcul est decompose en additions et multiplications sur un corps fini (comme une puce electronique logique)
2. R1CS (Rank-1 Constraint System) : chaque porte du circuit devient une contrainte de la forme (A.s) * (B.s) = (C.s) ou s est le vecteur temoin
3. QAP (Quadratic Arithmetic Program) : les contraintes R1CS sont encodees comme des polynomes, et la verification se reduit a une identite polynomiale
4. Preuve : le prouveur calcule la preuve via des pairings sur courbes elliptiques

Applications blockchain

Projet	Utilisation des zk-SNARKs
Zcash	Transactions privees (montants et adresses caches)
zk-Rollups (zkSync, StarkNet)	Scalabilite L2 : prouver N transactions en 1 preuve
Tornado Cash	Mixer : prouver l’appartenance a un ensemble sans reveler laquelle
Filecoin	Proof-of-Replication (stocker des données)
Mina Protocol	Blockchain de taille fixe (22 Ko) grace aux preuves recursives

# Demonstration simplifiee : circuit arithmetique et R1CS
# On veut prouver que l'on connait x tel que x^3 + x + 5 == 35 (reponse : x=3)
# sans reveler x

print("CIRCUIT ARITHMETIQUE SIMPLIFIE")
print("=" * 60)
print("Equation a prouver : x^3 + x + 5 == 35")
print("(Le prouveur connait x=3, le verificateur ne doit pas l'apprendre)")
print()

# Decomposition en circuit (chaque ligne = une porte multiplication)
# Variables : x, sym1, y, sym2, out
# Porte 1 : sym1 = x * x        (x^2)
# Porte 2 : y    = sym1 * x      (x^3)
# Porte 3 : sym2 = y + x         (x^3 + x)  -- addition, pas une porte R1CS
# Porte 4 : out  = sym2 + 5      (x^3 + x + 5)
# Contrainte : out == 35

# Le "temoin" complet (toutes les variables intermediaires)
x_secret = 3
sym1 = x_secret * x_secret       # 9
y_val = sym1 * x_secret          # 27
sym2 = y_val + x_secret          # 30
out = sym2 + 5                   # 35

witness = {
    "1": 1,          # Constante
    "x": x_secret,
    "sym1": sym1,    # x^2
    "y": y_val,      # x^3
    "sym2": sym2,    # x^3 + x
    "out": out,      # x^3 + x + 5
}

print("Temoin (witness) - toutes les variables intermediaires :")
for name, val in witness.items():
    print(f"  {name:5s} = {val}")
print()

# Contraintes R1CS : (A.s) * (B.s) = (C.s)
# Format : chaque contrainte est un triplet (A, B, C) de vecteurs
# Les vecteurs indexent : [1, x, sym1, y, sym2, out]
constraints = [
    # Porte 1 : sym1 = x * x -> (0,1,0,0,0,0)*(0,1,0,0,0,0) = (0,0,1,0,0,0)
    {"A": {"x": 1}, "B": {"x": 1}, "C": {"sym1": 1}},
    # Porte 2 : y = sym1 * x -> (0,0,1,0,0,0)*(0,1,0,0,0,0) = (0,0,0,1,0,0)
    {"A": {"sym1": 1}, "B": {"x": 1}, "C": {"y": 1}},
    # Porte 3+4 combinee : (y + x + 5) * 1 = out
    {"A": {"y": 1, "x": 1, "1": 5}, "B": {"1": 1}, "C": {"out": 1}},
]

print("Contraintes R1CS (Rank-1 Constraint System) :")
print("  Chaque contrainte : (A . witness) * (B . witness) = (C . witness)")
print()

all_valid = True
for i, con in enumerate(constraints):
    # Calculer les produits scalaires
    a_val = sum(coeff * witness[var] for var, coeff in con["A"].items())
    b_val = sum(coeff * witness[var] for var, coeff in con["B"].items())
    c_val = sum(coeff * witness[var] for var, coeff in con["C"].items())

    valid = (a_val * b_val) == c_val
    all_valid = all_valid and valid

    a_str = " + ".join(f"{c}*{v}" for v, c in con["A"].items())
    b_str = " + ".join(f"{c}*{v}" for v, c in con["B"].items())
    c_str = " + ".join(f"{c}*{v}" for v, c in con["C"].items())
    print(f"  Contrainte {i+1}: ({a_str}) * ({b_str}) = ({c_str})")
    check = "OK" if valid else "ECHEC"
    print(f"    => {a_val} * {b_val} = {c_val} ? {check}")

print(f"\nToutes les contraintes satisfaites : {all_valid}")
print(f"Le prouveur connait x tel que x^3 + x + 5 == {out}")
print()
print("En vrai zk-SNARK :")
print("  1. Le temoin serait encode comme polynomes sur un corps fini")
print("  2. La preuve serait ~200 octets (2 elements de courbe elliptique)")
print("  3. La verification prendrait ~5ms (3 pairings)")
print("  4. Le verificateur n'apprendrait pas x")

CIRCUIT ARITHMETIQUE SIMPLIFIE
============================================================
Equation a prouver : x^3 + x + 5 == 35
(Le prouveur connait x=3, le verificateur ne doit pas l'apprendre)

Temoin (witness) - toutes les variables intermediaires :
  1     = 1
  x     = 3
  sym1  = 9
  y     = 27
  sym2  = 30
  out   = 35

Contraintes R1CS (Rank-1 Constraint System) :
  Chaque contrainte : (A . witness) * (B . witness) = (C . witness)

  Contrainte 1: (1*x) * (1*x) = (1*sym1)
    => 3 * 3 = 9 ? OK
  Contrainte 2: (1*sym1) * (1*x) = (1*y)
    => 9 * 3 = 27 ? OK
  Contrainte 3: (1*y + 1*x + 5*1) * (1*1) = (1*out)
    => 35 * 1 = 35 ? OK

Toutes les contraintes satisfaites : True
Le prouveur connait x tel que x^3 + x + 5 == 35

En vrai zk-SNARK :
  1. Le temoin serait encode comme polynomes sur un corps fini
  2. La preuve serait ~200 octets (2 elements de courbe elliptique)
  3. La verification prendrait ~5ms (3 pairings)
  4. Le verificateur n'apprendrait pas x

Interpretation : Circuit arithmetique et R1CS

Le circuit decompose x^3 + x + 5 = 35 en 3 contraintes elementaires :

Contrainte	Opération	Verification
1	x * x = sym1	3 * 3 = 9 (carre)
2	sym1 * x = y	9 * 3 = 27 (cube)
3	(y + x + 5) * 1 = out	35 * 1 = 35 (sortie)

Points cles : - Le temoin (witness) contient toutes les variables intermediaires, pas seulement x - Chaque contrainte R1CS est de la forme (A.s) * (B.s) = (C.s) ou s est le temoin - Les additions sont absorbees dans les vecteurs (pas de porte d’addition separee) - En zk-SNARK reel, ces contraintes sont encodees comme polynomes puis verifiees par pairings de courbes elliptiques, sans jamais reveler le temoin

Exercice 3 : Ecrire des contraintes R1CS pour un circuit

En vous basant sur l’exemple R1CS ci-dessus (x^3 + x + 5 == 35), ecrivez les contraintes R1CS pour un circuit plus simple.

Equation a prouver : a * b + c == out (sans reveler a, b, ni c)

Objectif : Définir les contraintes R1CS et le temoin pour cette equation.

Indice : - Decomposez en portes : d’abord a * b = temp, puis temp + c = out - Variables du temoin : [1, a, b, c, temp, out] - Les additions sont absorbees dans les vecteurs (pas de porte d’addition separee)

Étapes : 1. Construire le temoin avec a=4, b=5, c=3 (donc temp=20, out=23) 2. Ecrire la contrainte pour a * b = temp 3. Ecrire la contrainte pour (temp + c) * 1 = out

# Exercice 3 : Contraintes R1CS pour a * b + c == out
# TODO etudiant : definissez les contraintes R1CS et le temoin

# Temoin : [1, a, b, c, temp, out]
# Indice : temp = a * b, puis out = temp + c
# Etape 1 : choisir des valeurs pour a, b, c (par exemple a=4, b=5, c=3)

witness_ex3 = {}  # TODO etudiant : construire le dictionnaire du temoin
# Exemple : {"1": 1, "a": 4, "b": 5, "c": 3, "temp": ..., "out": ...}

# Etape 2 : definir les contraintes R1CS
# Chaque contrainte est un triplet {"A": {...}, "B": {...}, "C": {...}}
# ou les cles sont les noms de variables et les valeurs sont les coefficients
# Contrainte 1 : a * b = temp
# Contrainte 2 : (temp + c) * 1 = out
constraints_ex3 = []  # TODO etudiant : ajouter les 2 contraintes

# Etape 3 : verifier que toutes les contraintes sont satisfaites
# (decommentez apres avoir complete le temoin et les contraintes)
# all_valid = True
# for i, con in enumerate(constraints_ex3):
#     a_val = sum(coeff * witness_ex3[var] for var, coeff in con["A"].items())
#     b_val = sum(coeff * witness_ex3[var] for var, coeff in con["B"].items())
#     c_val = sum(coeff * witness_ex3[var] for var, coeff in con["C"].items())
#     valid = (a_val * b_val) == c_val
#     all_valid = all_valid and valid
#     print(f"Contrainte {i+1}: {a_val} * {b_val} = {c_val} ? {'OK' if valid else 'ECHEC'}")
# print(f"Toutes contraintes satisfaites : {all_valid}")

print("Exercice a completer")
print("Definissez le temoin et les contraintes R1CS pour a * b + c == out")

Exercice a completer
Definissez le temoin et les contraintes R1CS pour a * b + c == out

Comparaison des systèmes de preuves

Système	Taille preuve	Temps verif.	Setup de confiance	Utilise par
Schnorr	~64 octets	~1ms	Non	Bitcoin (Taproot)
Groth16 (zk-SNARK)	~200 octets	~5ms	Oui (trusted setup)	Zcash, Tornado Cash
PLONK (zk-SNARK)	~400 octets	~10ms	Universel	zkSync, Aztec
zk-STARK	~50 Ko	~50ms	Non	StarkNet, Polygon Miden
Bulletproofs	~700 octets	~50ms	Non	Monero

Compromis fondamental : taille de preuve vs. hypotheses de confiance. Les zk-STARKs sont plus gros mais n’ont pas besoin de “trusted setup”, ce qui les rend plus transparents pour les systèmes decentralises.

Note : les implementations completes de zk-SNARKs et zk-STARKs depassent le cadre de ce notebook. Elles reposent sur des pairings de courbes elliptiques (BN254, BLS12-381) et de l’algebre polynomiale avancee.

---

6. Exemple guide : ZKP de preimage de hash

Solution proposee par Clovis Lefebvre, Evariste Balvay.

Objectif

Implementer un protocole ZKP qui prouve que l’on connait la preimage d’un hash SHA-256 sans la reveler.

Concretement : etant donne h = SHA256(secret), prouver que l’on connait secret sans le communiquer au verificateur.

Approche

On utilise une approche basee sur le logarithme discret. Le prouveur encode son secret comme exposant et utilise le protocole de Schnorr.

La classe HashPreimageZKP ci-dessous implemente les trois étapes : 1. register : calcule le hash public et derive la cle publique via exponentiation modulaire 2. prove : protocole de Schnorr non-interactif (Fiat-Shamir) pour generer une preuve 3. verify : verification de la preuve en recalculant le challenge

import hashlib
from Crypto.Util.number import getRandomRange


class HashPreimageZKP:
    """ZKP prouvant la connaissance d'une preimage de hash.

    Strategie : convertir le secret en un scalaire dans le groupe de Schnorr,
    puis utiliser le protocole de Schnorr pour prouver la connaissance.

    Le verificateur connait :
      - Le hash public h_pub = SHA256(secret)
      - Les parametres du groupe (p, q, g)
      - La valeur y = g^(int(h_pub) mod q) mod p

    Le prouveur connait :
      - Le secret (dont le hash donne h_pub)
    """

    def __init__(self, p, q, g):
        """Initialiser avec les parametres du groupe."""
        self.p = p
        self.q = q
        self.g = g

    def register(self, secret: bytes):
        """Enregistrer un secret et publier (h_pub, y, x_derived).

        1. Calculer h_pub = SHA256(secret).hexdigest()
        2. Convertir h_pub en entier x_derived = int(h_pub, 16) % self.q
        3. Calculer y = pow(self.g, x_derived, self.p)
        4. Retourner (h_pub, y, x_derived)
        """
        h_pub = hashlib.sha256(secret).hexdigest()
        x_derived = int(h_pub, 16) % self.q
        y = pow(self.g, x_derived, self.p)
        return h_pub, y, x_derived

    def prove(self, x_derived: int, y: int, h_pub: str) -> tuple:
        """Protocole de Schnorr non-interactif (Fiat-Shamir).

        1. Generer un nonce aleatoire r
        2. Calculer l'engagement R = g^r mod p
        3. Calculer le defi via Fiat-Shamir :
             c = H(g || y || R || h_pub) mod q
        4. Calculer la reponse s = (r - c * x_derived) mod q

        Retourne le tuple de preuve (R, s, c).
        """
        r = getRandomRange(1, self.q)
        R = pow(self.g, r, self.p)

        c_input = f"{self.g}|{y}|{R}|{h_pub}".encode()
        c = int(hashlib.sha256(c_input).hexdigest(), 16) % self.q

        s = (r - c * x_derived) % self.q

        return R, s, c

    def verify(self, proof: tuple, y: int, h_pub: str) -> bool:
        """Verifier une preuve de Schnorr.

        1. Reconstruire R' = g^s * y^c mod p
        2. Recalculer le defi c' = H(g || y || R' || h_pub) mod q
        3. Accepter si et seulement si c' == c
        """
        R, s, c = proof
        R_prime = (pow(self.g, s, self.p) * pow(y, c, self.p)) % self.p

        challenge_input = f"{self.g}|{y}|{R_prime}|{h_pub}".encode()
        c_prime = int(hashlib.sha256(challenge_input).hexdigest(), 16) % self.q

        return c_prime == c


# --- Validation ---
# Parametres RFC 3526 MODP Group 14 (2048 bits, pedagogique simplifie)
p = int(
    "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
    "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
    "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
    "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
    "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
    "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
    "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
    "670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B"
    "E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9"
    "DE2BCBF6955817183995497CEA956AE515D2261898FA0510"
    "15728E5A8AACAA68FFFFFFFFFFFFFFFF", 16
)
q = (p - 1) // 2
g = 2

zkp = HashPreimageZKP(p, q, g)

secret = b"mon_secret_super_prive"
h_pub, y, x_derived = zkp.register(secret)

proof = zkp.prove(x_derived, y, h_pub)
valid = zkp.verify(proof, y, h_pub)
print(f"Preuve valide pour secret correct : {valid}")

# Preuve forgee : doit echouer
fake_proof = (proof[0], proof[1] + 1, proof[2])
print(f"Preuve valide pour preuve forgee  : {zkp.verify(fake_proof, y, h_pub)}")

Preuve valide pour secret correct : True
Preuve valide pour preuve forgee  : False

Interpretation de l’exemple guide

Test	Résultat attendu	Explication
Secret correct	True	Le prouveur honnete : R' = g^s * y^c = g^(r-cx) * g^(cx) = g^r = R
Preuve forgee	False	Modifier s casse l’equation : g^(s+1) != R * y^c

Points cles de l’implementation : - register derive un expose secret x_derived a partir du hash SHA-256 du secret, puis calcule la cle publique y = g^x_derived mod p - prove utilise le protocole de Schnorr avec la variante s = (r - c*x) mod q et un challenge Fiat-Shamir H(g|y|R|h_pub) - verify reconstruit R' = g^s * y^c et verifie que le challenge recalcule correspond au challenge original : si c' == c, la preuve est valide - L’utilisation de paramètres RFC 3526 (2048 bits) assure une securite production-grade pour le groupe multiplicatif

---

7. Exercice : ZKP de double preimage de hash

Objectif

Etendre la classe HashPreimageZKP pour prouver la connaissance de deux secrets dont les hashes sont connus publiquement, sans reveler aucun des deux secrets.

Contexte

Dans un système de vote electronique, un electeur doit prouver qu’il connait les preimages de deux hashes h1 = SHA256(secret1) et h2 = SHA256(secret2) (pour un vote a deux tours, par exemple) sans reveler ses secrets.

A implementer

Completez la méthode prove_double de la classe DoubleHashZKP ci-dessous.

Indice : utilisez deux preuves de Schnorr independantes, une pour chaque secret, et combinez-les en un seul tuple de preuve.

class DoubleHashZKP(HashPreimageZKP):
    """ZKP prouvant la connaissance de deux preimages de hash."""

    def prove_double(self, x1_derived: int, y1: int, h1_pub: str,
                     x2_derived: int, y2: int, h2_pub: str) -> tuple:
        """Prouver la connaissance de deux secrets en une seule operation.

        TODO etudiant : generer deux preuves de Schnorr independantes
        (une pour chaque secret) et les retourner combinees.

        Retourne un tuple ((R1, s1, c1), (R2, s2, c2)).
        """
        # TODO etudiant : implementez prove_double
        return (None, None, None), (None, None, None)


# Validation
print("Exercice a completer : implementez prove_double dans DoubleHashZKP")

Exercice a completer : implementez prove_double dans DoubleHashZKP

---

8. Resume

Recapitulatif des protocoles

Protocole	Prouve que…	Interactif ?	Complexite
Caverne Ali Baba	“Je connais le mot de passe”	Oui (N rounds)	O(N)
Schnorr	“Je connais x tel que g^x = y”	Les deux	O(1)
Chaum-Pedersen	“log_g(y1) = log_h(y2)”	Les deux	O(1)
OR-proof	“Je connais x1 ou x2”	Les deux	O(1)
zk-SNARK	“Je connais un temoin w pour C(w)=1”	Non	O(1) verification
HashPreimageZKP	“Je connait la preimage de h”	Non (Fiat-Shamir)	O(1)

Concepts cles

Concept	Description
Completude	Le prouveur honnete convainc toujours
Solidite	Le fraudeur echoue avec forte probabilite
Zero-knowledge	Le verificateur n’apprend rien de plus
Fiat-Shamir	Transformer interactif en non-interactif via hash
Sigma protocol	Framework general : engagement -> challenge -> reponse
R1CS	Representation des calculs en contraintes rang-1

Points cles

• Les ZKP permettent de prouver sans reveler : un changement de paradigme en cryptographie
• Le protocole de Schnorr est la brique de base, utilisee dans Bitcoin (Taproot)
• La transformation de Fiat-Shamir convertit toute preuve interactive en signature
• Les zk-SNARKs generalisent les ZKP a des calculs arbitraires (zk-rollups, confidentialite)
• Les applications blockchain sont en pleine explosion : scalabilite L2, votes, identite

---

Notebook suivant : SC-16-Homomorphic-Encryption-Python - Chiffrement homomorphe

Resume et perspectives

Ce notebook a constitue une plongee approfondie dans les preuves a divulgation nulle (Zero-Knowledge Proofs), des la fondation conceptuelle (analogie de la caverne d’Ali Baba) jusqu’aux architectures zk-SNARKs industrielles. Nous avons implemente le protocole de Schnorr en version interactive puis non-interactive (transformation de Fiat-Shamir), decouvert que cette dernière est exactement une signature numérique – utilisee dans Bitcoin Taproot (BIP-340). Le protocole de Chaum-Pedersen a illustre la preuve d’egalite de logarithmes discrets, brique essentielle du vote electronique. Enfin, la decomposition d’un calcul arbitraire en circuit arithmetique puis en contraintes R1CS a demystifie le pipeline de construction des zk-SNARKs.

Les ZKP representent un changement de paradigme en cryptographie : prouver sans reveler. Cette propriete trouve des applications majeures dans les zk-rollups (scalabilite L2 sur zkSync, StarkNet), les transactions privees (Zcash, Tornado Cash), et l’identite decentralisee. Le compromis entre taille de preuve et hypotheses de confiance (trusted setup pour Groth16, transparence pour zk-STARKs) guide le choix du système selon le contexte. Les implementations completes, reposant sur des pairings de courbes elliptiques (BN254, BLS12-381), depassent le cadre de ce notebook mais les concepts fondamentaux sont maintenant en place.

Le prochain notebook explore le chiffrement homomorphique, une technique complementaire aux ZKP qui permet d’effectuer des calculs directement sur des données chiffrees, sans les dechiffrer : SC-16-Homomorphic-Encryption-Python.

---

<< Formal Verification | Homomorphic Encryption >>