Avevo parlato delle dimostrazioni a conoscenza zero una decina d’anni fa, sul Post. Magari la prossima settimana ne scrivo ancora. Per il momento vi lascio una dimostrazione pratica: una dimostrazione si dice a conoscenza zero se io riesco a convincerti che conosco un segreto senza rivelartelo. Per esempio, potrei dirti che ho una tecnica infallibile per lanciare una moneta e farla cascare su testa o croce: tu mi dai una moneta, mi dici quale faccia vuoi che esca, e io ci riesco una, dieci, cento volte di fila. A un certo punto tu ti fiderai che io sono effettivamente in grado di decidere quale faccia mostrare (e ovviamente non giocherai più a testa o croce con me), anche se non hai nessuna idea di come io faccia. La parola chiave è “fidarsi”: le dimostrazioni a conoscenza zero sono inerentemente probabilistiche, proprio perché non possiamo controllare la dimostrazione. Quello che conta è che la probabilità che io sia stato semplicemente fortunato sia piccola a piacere: con un solo lancio capiterebbe una volta su due, con dieci lanci una volta su 1000, con cento lanci la probabilità di essere stato fortunato sarebbe inconcepibilmente piccola.
Passiamo ora al logaritmo discreto. Probabilmente vi ricordate che se avete l’equazione $b^x = y$ allora $b$ è la radice x-sima di $y$, mentre $x$ è il logaritmo di $y$ in base $b$: a differenza di addizione e moltiplicazione, l’elevazione a potenza non è commutativa e quindi ci sono due operazioni inverse. Quello che a scuola non insegnano è che è possibile anche calcolare il logaritmo in un gruppo finito, se la dimensione del gruppo è un numero primo $p$ (insomma, se stiamo usando i numeri modulo $p$). Prendiamo per esempio $p = 7$: le potenze di 3 in base 7 sono le seguenti.
$$\begin{matrix}
n & 1 & 2 & 3 & 4 & 5 & 6 \\
3^n & 3 & 2 & 6 & 4 & 5 & 1 \\
\end{matrix}$$
Notate che non consideriamo lo 0, perché ci interessa il gruppo moltiplicativo e non quello additivo; notate anche come tutti i valori da 1 a 6 sono presenti nella riga delle potenze. Da qui è facile ricavare il logaritmo discreto:
$$\begin{matrix}
n & 1 & 2 & 3 & 4 & 5 & 6 \\
\log_3 n & 6 & 2 & 1 & 4 & 5 & 3 \\
\end{matrix}$$
In questo caso la tabella è facile da calcolare, ma se partissimo da un numero primo di centinaia di cifre sarebbe ancora facile elevare un numero a una qualche potenza, ma non lo sarebbe affatto partire da quel risultato e risalire al numero. Il logaritmo discreto è insomma una di quelle “funzioni a senso unico” che servono per la crittografia. Come si può sfruttare il logaritmo discreto per convincere il mio interlocutore che conosco $x$, il logaritmo in base $b$ di $y$, senza rivelarglielo? Ecco un protocollo di comunicazione, come spiegato da John Cook.
(1) Io scelgo un numero (naturale) casuale $r$, calcolo $t = b^r$, e mando al mio interlocutore il numero $t$.
(2) Lui mi spedisce a sua volta un altro numero casuale $c$.
(3) Io calcolo $s = r + cx$ e glielo mando.
(4) Lui verifica ce effettivamente $b^s = ty^c$. In caso affermativo si fida (oppure riprova più volte, se pensa che io abbia avuto fortuna).
Cosa conosce il mio interlocutore, oltre alla base $b$ e a $y$? Due numeri: $t$ e $s$. Il primo, $t$, è l’esponenziale (in base $b$ di un numero casuale, e quindi è anch’esso casuale: non dà dunque nessuna informazione. Il secondo, $s$, di per sé è basato su $x$, ma per trovarlo bisognerebbe conoscere $r$ e per riuscirci dovrebbe essere in grado di calcolare rapidamente il logaritmo discreto, cosa che al momento non è fattibile. Infine, abbiamo che $b^s = b^{r+cx} = b^r b^{cx} = t (b^x)^c = ty^c$. Inoltre, visto che io non potevo conoscere a priori $c$, non potevo fare il calcolo in anticipo. Anche questo punto è importante, perché altrimenti potrei usare dei trucchi: tornando all’esempio del lancio di monete, non è così difficile fare un video in cui io per dieci volte di fila lancio una moneta dicendo ciascuna volta cosa uscirà. Comincio a filmare finché non mi capita la successione di dieci risultati corretti, e taglio tutta la parte precedente del video…
[Disclaimer: Ho ricevuto il libro grazie al programma Early Reviewer di LibraryThing]