Il protocollo a conoscenza zero
Il protocollo o prova a conoscenza zero (Zero-Knowledge Proof) è un modo per dimostrare di conoscere un certo segreto (un numero \( x \)) senza rivelarle il segreto stesso.
E' un protocollo basato su una prova interattiva. Un utente A deve dimostrare a un utente B di conoscere un numero segreto \( x \) senza riverarlo o comunicarlo.
Tramite diverse iterazioni, l'utente B potrà capire se l'utente A conosce davvero \( x \), senza che A l'abbia mai svelato, oppure no.
Questo è l'obiettivo delle Zero-Knowledge Proofs: dimostrare di sapere qualcosa senza rivelarne il contenuto.
Un esempio pratico
L'utente A conosce la password di una stanza (il segreto) e vuole convincere l'utente B di conoscerla senza rivelare la password stessa.
La stanza dispone di due porte, denominate porta 1 e porta 2.
L'utente A può:
- entrare da una delle due porte (porta 1 o porta 2) senza bisogno di conoscere la password
- uscire dalla stessa porta da cui è entrato senza utilizzare la password
- uscire dalla porta diversa da quella di accesso solo dopo aver digitato la password.
L'utente B non conosce la password, ma può osservare il comportamento di A. Il processo si sviluppa così:
- L'utente A sceglie la porta di ingresso. L'utente A entra nella cassaforte attraverso una porta scelta a caso (ad esempio, la porta 1), ma non dice a B da quale porta è entrato.
- L'utente B sceglie la porta di uscita. L'utente B, senza sapere da quale porta A è entrato, gli chiede di uscire da una porta specifica (porta 1 o porta 2).
- Se B chiede ad A di uscire dalla porta 1, A può farlo senza problemi, poiché è quella da cui è entrato.
- Se B chiede ad A di uscire dalla porta 2, A può farlo solo se conosce la password per aprire la cassaforte dall’interno.
- Ripetizione della prova. Il processo viene ripetuto più volte facendo scelte casuali.
Dopo numerosi test, se A li supera tutte le volte, B sarà convinto che A conosce la password perché ha superato ogni prova, ma non avrà mai ricevuto informazioni sulla password stessa.
Questo è il principio delle Zero-Knowledge Proofs: dimostrare la conoscenza di un segreto senza rivelarne il contenuto.
Esempio 2
L'utente A conosce \( x \), tale che \( b^x \mod N = y \), e vuole convincere B di conoscere \( x \) senza rivelarlo.
$$ b^x \mod N = y $$
In questo esempio utilizzo \( b = 3 \) (base), \( N = 17 \) (modulo) e \( y = 13 \)
$$ 3^x \mod 17 = 13 $$
Quindi \( x = 4 \) perché \( 3^4 \mod 17 = 13 \).
$$ 3^4 \mod 17 = 13 $$
$$ 81 \mod 17 = 13 $$
Gli utenti A e B conoscono \( b \), \( N \) e \( y \) ma solo A conosce \( x \).
L'utente A sceglie un valore casuale
L'utente A sceglie un valore casuale \( e = 6 \) e calcola \( b^e \mod N \):
$$ b^e \mod N $$
$$ 3^6 \mod 17 $$
$$ 729 \mod 17 = 15 $$
L'utente A invia \( b' = 15 \) all'utente B.
L'utente B sceglie la domanda
L'utente B decide casualmente se;
- chiedere ad A di rivelare \( e \)
- chiedere ad A di rivelare \( x + e \mod N \)
Nel primo caso l'utente A rivela \( e = 6 \) all'utente B.
Questo corrisponde a \( b' \), quindi l'utente B è soddisfatto perché il calcolo corrisponde.
$$ b^e \mod N = 3^6 \mod 17 = 15 $$
Nel secondo caso l'utente A rivela \( x + e \mod N \) all'utente B
$$ x + e \mod N = 4 + 6 \mod 17 = 10 $$
In questo modo l'utente B calcola $ b^{x+e} \mod N $
$$ b^{x+e} \mod N = 3^{10} \mod 17 = (3^4 \cdot 3^6) \mod 17 = (4 \cdot 15) \mod 17 = 60 \mod 17 = 9 $$
e verifica se è lo stesso risultato di $ y \cdot b' \mod N $.
$$ b^{x+e} = y \cdot b' \mod N = 4 \cdot 15 \mod 17 = 60 \mod 17 = 9 $$
Il risultato è lo stesso, quindi anche in questo caso l'utente B è soddisfatto.
La ripetizione del processo
Questo processo viene ripetuto molte volte, con A che sceglie un nuovo valore casuale \( e \) ogni volta.
L'utente B sceglie casualmente e verifica che A riesca sempre a rispondere correttamente.
Se l'utente A conosce \( x \), può rispondere correttamente in entrambi i casi.
Viceversa, se l'utente A non conosce \( x \), può rispondere correttamente solo in uno dei due casi, quindi verrà scoperto con alta probabilità dopo molte ripetizioni.
Questo esempio dimostra come A possa convincere B di conoscere \( x \) senza rivelare il suo valore.
E così via.
