Protocolli Sigma e identificazione Schnorr

Un protocollo Sigma ha 3 messaggi: (1) Commit: il prover invia un commitment a un valore casuale. (2) Challenge: il verifier invia una challenge casuale. (3) Response: il prover invia una risposta calcolata a partire dalla challenge e dal segreto. Il verifier accetta o rifiuta.

Il prover conosce il segreto x (chiave privata); la chiave pubblica = g^x mod p (oppure il punto X = x*G su una curva ellittica). Obiettivo: dimostrare di conoscere x senza rivelarlo. Questa è una prova di conoscenza del logaritmo discreto.

(1) Il prover sceglie un r casuale e invia il commitment R = r*G. (2) Il verifier invia la challenge c (un intero casuale). (3) Il prover invia la risposta s = r + c*x. (4) Il verifier verifica s*G == R + c*X. Se la verifica ha esito positivo, accetta. Il prover conosce x; la risposta s è calcolabile solo conoscendo x.

Completezza: un prover onesto soddisfa sempre s*G = r*G + c*x*G = R + c*X. Solidità: due trascrizioni con lo stesso R ma challenge diverse c, c' producono s, s', da cui è possibile ricavare x = (s-s')/(c-c') — quindi un imbroglione non può produrre due risposte valide per lo stesso R.

Simulatore (senza conoscere x): sceglie s e c casuali e imposta R = s*G - c*X. La tripla (R, c, s) ha la distribuzione di una trascrizione valida. Il verifier non può distinguere le trascrizioni reali da quelle simulate — Schnorr è zero-knowledge per un verifier onesto.

Rendere Schnorr non interattivo: sostituire la challenge del verifier con c = Hash(R || message). Il prover calcola autonomamente c e invia la risposta. Risultato: una prova composta da 2 elementi (R, s), che chiunque può verificare. Questo è lo schema di firma Schnorr.

Sign(x, m): r ← random; R = r*G; c = Hash(R||m); s = r + c*x. Signature = (R, s). Verify: s*G == R + Hash(R||m)*X. Compatta (64 byte per P-256), verificabile in batch e dimostrabilmente sicura nel ROM. Adottata in Bitcoin Taproot (BIP-340).

C = r*G + v*H, dove H è un secondo generatore indipendente. Crea un commitment al valore v usando la casualità r. Binding: non è possibile aprirlo a un valore v diverso (logaritmo discreto). Hiding: C è distribuito uniformemente. Utilizzato nelle range proof basate su Schnorr e nelle Bulletproofs.

Dimostrare la conoscenza di x1 AND x2 simultaneamente: eseguire due protocolli Schnorr con la stessa challenge (condividendo la challenge tramite Fiat-Shamir). Il verifier accetta solo se entrambe le sotto-prove sono valide. Consente di dimostrare più asserzioni con un'unica interazione.

Dimostrare la conoscenza di x1 OR x2 senza rivelare quale dei due: usare il simulatore per un ramo per calcolare una trascrizione falsa, quindi suddividere la challenge tra entrambi i rami. Il verifier vede due trascrizioni apparentemente valide la cui somma corrisponde alla challenge reale. Sono chiamate «ring signatures».

Schnorr ID: passaporti elettronici (protocollo PACE). Firme Schnorr: Bitcoin Taproot, Monero (RingCT usa prove OR Schnorr), Signal Protocol (accordo di chiavi X3DH). Commitment di Pedersen: Confidential Transactions, Bulletproofs, cifratura delle note Zcash Sapling.

Nel protocollo di identificazione Schnorr, che cosa verifica il verifier nel passaggio finale?

Protocolli Sigma: commit-challenge-respond. Schnorr dimostra la conoscenza di un logaritmo discreto. Fiat-Shamir lo rende non interattivo (firma Schnorr). Prossimo argomento: gli zk-SNARK per prove non interattive succinte.