Alice, Bob e Eva — Zero Knowledge

“Conoscenza zero?”.

“Sì”.

“E cosa significa?”.

“Significa che io so un segreto, ti dimostro che lo conosco, ma non ti dico qual è”.

“Ma dai. E come è possibile?”.

“Con le conoscenze che possediamo ora, è possibile. Ti faccio un esempio facile, che semplifica un po' le cose, ma che fa capire come funziona il tutto. Si tratta di giocare a testa o croce”.

“Dici il gioco con la moneta?”.

“Sì, si scommette sull'esito del lancio di una moneta. Però ci giochiamo via telefono. Tu sei a un capo del telefono, io all'altro, e naturalmente non ci possiamo vedere. Quindi se io lancio la moneta tu non vedi il risultato”.

“E dovrei fidarmi di quello che mi dici tu?”.

“Sì”.

“Figuriamoci”.

“Ma io devo fare in modo che tu ti possa fidare al di sopra di ogni ragionevole dubbio. Questo significa che io ti devo dimostrare di conoscere il segreto (cioè l'esito del lancio) senza però rivelartelo subito, perché altrimenti tu non puoi scommettere”.

“Ma come fai?”.

“Ci accordiamo su questa procedura: io lancio la moneta, se viene testa genero due numeri primi grandi e congruenti a 1 modulo 4. Se viene croce genero due numeri primi grandi e congruenti a 3 modulo 4”.

“Uhm, perchè?”.

“Ora li moltiplico. Supponi che sia uscita testa: se calcolo il resto della divisione per 4 del prodotto cosa ottengo?”.

“Dunque, hai due numeri congruenti a 1, se li moltiplichi tra loro ottieni due numeri congruenti a 1², cioè ancora 1”.

“Perfetto. Ora supponi che sia uscita croce. Se moltiplichi i due numeri cosa ottieni, questa volta?”.

“Questa volta ottengo un numero congruente a 3², cioè 9. Un momento, 9 è congruente a 1 modulo 4”.

“Esatto. Quindi, sia in un caso che nell'altro il numerone che ottengo è congruente a 1. Te lo trasmetto via telefono”.

“Forse comincio a capire”.

“Appena tu ricevi il numero devi scommettere: testa o croce? Naturalmente analizzando il numero non puoi sapere se è uscita testa o croce, perché puoi, in modo veloce, solo calcolare la sua congruenza modulo 4, ma non fattorizzarlo”.

“Ah, di nuovo il problema della fattorizzazione… Quindi io ricevo il numero, scommetto, e poi tu mi dici quello che è uscito? Come faccio a fidarmi?”.

“Io non ti comunico quello che è uscito, ma ti comunico i due numeri. Tu puoi moltiplicarli e vedere se il loro prodotto è uguale al numerone oppure no. Dopo aver fatto la verifica, puoi calcolare la congruenza modulo 4 dei due numeri: se è uguale a 1 è uscita testa, se invece è 3 allora è uscita croce”.

“Bella roba: ci si riesce, non l'avrei mai detto. Certo che testa o croce è proprio il gioco più facile che ci sia”.

“Se vuoi, si può giocare anche a poker via telefono”.

“Poker? Vuoi dire che si riesce a gestire un mazzo di carte senza poterle vedere?”.

“Certo. Per essere precisi: in un articolo i nostri amici Shamir, Rivest e Adleman prima dimostrano che è matematicamente impossibile giocare a poker via telefono, poi mostrano un protocollo corretto, completo e funzionante per farlo”.

“Cosa? Ma così cadono tutte le mie certezze nei confronti della matematica!”.

“Già. Shamir, Rivest e Adleman devono essersi divertiti un sacco a scriverlo”.

⇐ · ⇒