Intuizione degli ZKP: la grotta di Ali Baba

Una prova a conoscenza zero (ZKP) consente al dimostrante di convincere il verificatore di conoscere un segreto (o che un'asserzione sia vera) senza rivelare il segreto stesso. Le tre proprietà sono: completezza, solidità e conoscenza zero.

Se il dimostrante conosce il segreto, può sempre convincere il verificatore. Un dimostrante onesto che segue il protocollo avrà successo con probabilità 1 (o con probabilità schiacciante). Il verificatore non rifiuterà una prova valida.

Un dimostrante disonesto (che non conosce il segreto) non può convincere il verificatore, se non con probabilità trascurabile. Ogni round di interazione riduce la probabilità di successo dell'imbroglio: dopo k round, la probabilità di successo di un truffatore è al massimo 2^{-k}.

Il verificatore non apprende nulla oltre al fatto che l'asserzione è vera. Formalmente: esiste un simulatore che, senza conoscere il segreto, produce una trascrizione indistinguibile da quella di una vera interazione tra dimostrante e verificatore. Il verificatore non acquisisce alcuna informazione aggiuntiva.

Una grotta ha un passaggio circolare con una porta magica al centro. Il dimostrante (Alice) afferma di conoscere la password. Il verificatore (Bob) aspetta all'esterno. Alice entra e va a sinistra o a destra. Bob urla da quale lato deve uscire. Se Alice conosce la password, esce sempre dal lato corretto. Probabilità di successo per un imbroglione a ogni round: 1/2.

Dopo 20 round, un imbroglione riesce con probabilità 2^{-20}, cioè circa 1 su un milione. Alice (che conosce la password) riesce ogni volta. Bob non apprende mai la password: vede soltanto Alice uscire dal lato richiesto. Questa è la conoscenza zero.

Le ZKP interattive richiedono uno scambio continuo tra dimostrante e verificatore. Le ZKP non interattive (NIZK) utilizzano la trasformazione di Fiat-Shamir: sostituiscono la sfida casuale del verificatore con un hash dell'impegno (hash = oracolo casuale). Il risultato è un'unica stringa di prova che chiunque può verificare.

Una ZKP è una prova di conoscenza (PoK) se la strategia del dimostrante implica che il segreto potrebbe essere estratto. È una proprietà più forte della semplice dimostrazione della verità di un'asserzione. Le firme ECDSA e Schnorr sono prove non interattive di conoscenza della chiave privata.

Autenticazione tramite password senza inviare la password. Verifica dell'età senza rivelare la data di nascita. Prove di intervallo (il proprio stipendio rientra in un intervallo) senza rivelare lo stipendio. Blockchain: dimostrare di conoscere una transazione valida senza rivelare la transazione.

Zero-knowledge perfetto: l'output del simulatore è identico alla trascrizione reale. ZK statistico: indistinguibile, salvo che con probabilità trascurabile. ZK computazionale: indistinguibile per verificatori a tempo polinomiale. Garanzie più deboli = prove più efficienti.

La caverna è un protocollo a 3 mosse: commitment → challenge → response. Formalmente, si chiama protocollo Sigma. La maggior parte delle ZKP pratiche (Schnorr, Pedersen, Fiat-Shamir) sono protocolli Sigma o loro composizioni. Il nome deriva dalla forma Σ del diagramma del flusso dei messaggi.

Dopo quanti round del protocollo della caverna di Ali Baba la probabilità di successo di un imbroglione scende al di sotto di 1/1000?

Le ZKP dimostrano la conoscenza di un segreto senza rivelarlo. Tre proprietà: completezza, solidità, zero-knowledge. La caverna di Ali Baba illustra una ZKP interattiva. Prossimo argomento: protocolli Sigma e identificazione Schnorr.