backup del Post

Dimostrazioni a conoscenza zero

Il biglietto da visita dice semplicemente “L’uomo che sa contare gli spilli”. Il proprietario del biglietto è un omino che afferma che se gli presentate un qualunque contenitore pieno di spilli, fossero una scatoletta o un tir, lui è in grado con una sola occhiata di dire quanti ce ne sono. Come possiamo fidarci che il tipo non ci stia prendendo in giro, senza metterci a contare tutti gli spilli?

Un modo per avere non proprio la certezza ma una probabilità grande a piacere di accorgerci che il tipo sta cercando di prenderci in giro è spiegato da Dennis Shasha nel suo libro Codes, Puzzles, and Conspiracy. Mostriamogli un mucchio di spilli e chiediamogli quanti ce ne sono. Poi lo facciamo uscire dalla stanza, togliamo dal mucchio un numero di spilli abbastanza piccolo perché lo possiamo contare senza troppa fatica, facciamo rientrare il Contatore e gli chiediamo “Bene: quanti spilli ci sono ora“? Se la differenza tra i due numeri da lui divinati coincide con il numero di spilli che abbiamo tolto, possiamo iniziare a fidarci del tipo; altrimenti siamo certi che sia un ciarlatano. Se siamo dei malfidenti, possiamo sempre rifare più volte l’esperimento. Ma c’è di meglio ancora! Immaginiamo che il Contatore di spilli non voglia rivelarci il numero esatto di spilli – chessò, sa che un nostro amico ha scommesso mille euro che noi non sappiamo dirgli quanti spilli ci sono nel mucchio, e vuole cento euro in anticipo per darci la risposta. Bene, noi possiamo allora chiedergli quanti spilli abbiamo tolto. Se sono relativamente pochi rispetto al numero totale, il Contatore di spilli non ha nessun problema a risponderci, ammesso naturalmente che sappia davvero quanti elementi ci sono nel mucchio: fornirci questa informazione anche per un numero ripetuto di tentativi non ci dà infatti nessuna informazione sul numero totale. Insomma, possiamo essere del tutto fiduciosi che il Contatore di spilli sappia davvero contarli senza che lui renda pubblica la risposta.

Dimostrazioni di questo tipo sono dette a conoscenza zero (in inglese, “Zero-knowledge proofs”), e come sempre Wikipedia è la nostra amica. Il concetto è relativamente recente, visto che è apparso in letteratura solo nel 1985 con il lavoro di Shafi Goldwasser, Silvio Micali e Charles Rackoff. (Nota a latere: Micali è diventato professore al MIT a 29 anni, e ha vinto il premio Gödel e il premio Turing. Insomma, un cervello in fuga niente male). Wikipedia presenta anche una “spiegazione per bambini” di cosa è una dimostrazione a conoscenza zero, ideata da Jean-Jacques Quisquater, Louis C. Guillou e Thomas A. Berson. Ci sono due personaggi: il possessore della dimostrazione Patrizia e il verificatore Valerio, e c’è una caverna con due ingressi, A e B. All’interno della caverna c’è una porta chiusa, che impedisce di entrare da una parte e uscire dall’altra a piacere. Patrizia afferma di avere la parola magica per aprire quella porta, ma non vuole rivelarla a Valerio prima che questi la paghi per l’informazione. Come può Patrizia convincere (ragionevolmente: tenetelo a mente) Valerio che lei effettivamente possiede quella parola magica, senza dargli nessun’altra informazione? Semplice. Patrizia entra nella caverna senza che Valerio la veda, e a questo punto Valerio le chiede di uscire da un ingresso specifico. Se Patrizia effettivamente conosce la parola magica non avrà problema a eseguire la richiesta; altrimenti c’è una possibilità su due che non possa farlo perché era entrata dall’altra parte. Valerio può ripetere l’operazione quante volte vuole, fino a che la probabilità che Patrizia sia solo molto fortunata diventa così bassa che Valerio si convincerà. Per esempio, dopo venti richeste la probabilità di riuscire sempre per pura fortuna è meno di una su un milione.

Traducendo l’esempio in modo formale, abbiamo un possessore e un verificatore; entrambi devono dimostrare all’altro di essere onesti, il verificatore seguendo un preciso modo di operazioni (un protocollo) e il possessore dando la risposta corretta alle domande del verificatore. Per avere una “dimostrazione” a conoscenza zero di un’affermazione, occorrerà che siano verificate tre condizioni:

1. Completezza: se l’affermazione è vera, un possessore onesto potrà convincere un verificatore onesto.
2. Correttezza: se l’affermazione è falsa, nessun possessore disonesto potrà convincere (sufficientemente) il verificatore onesto che essa è vera.
3. Conoscenza zero: se l’affermazione è vera, un verificatore potrà sapere solo tale informazione, e nulla più.

Ci sono due punti fondamentali da notare. Il primo, legato alla correttezza, ci ricorda che queste non sono dimostrazioni in senso matematico: non abbiamo mai la certezza ma solo una probabilità che possiamo rendere piccola a piacere di sbagliarci. Il secondo è un po’ più complicato da spiegare, e richiede l’introduzione di un terzo personaggio, il perfido simulatore Stanislao. Immaginiamo che Valerio, ormai convinto che Patrizia conosca effettivamente la parola magica per aprire la porta segreta, abbia filmato tutta la scena, con lui che per venti volte arriva, dice “destra” o “sinistra” e vede Patrizia uscire dalla parte giusta. Valerio porta il video al notaio Nicoletta per certificare la propria scoperta… e Nicoletta gli risponde “nulla da fare, questo video non ha alcun valore”. Come mai? Semplice. Stanislao le aveva appena consegnato un video taroccato nel quale una sosia di Patrizia sembrava fare esattamente le stesse cose, pur senza conoscere la parola magica. Come ha fatto? Beh, ci sono varie possibilità. Per esempio, ha filmato una cinquantina di tentativi e ha rimontato il video mostrandone solo venti coronati da successo: oppure si è messo d’accordo con la sosia spiegandole quale sarebbe stata la successione esatta di richieste che le avrebbe fatto. In pratica, dunque, il mero fatto di vedere le risposte esatte può sempre essere simulato, il che significa che non dà nessuna informazione aggiuntiva a quella “il possessore conosce effettivamente il segreto”.

Chi vuole divertirsi a vedere un giochino interattivo sulle dimostrazioni a conoscenza zero può andare su questa pagina, dove ci sono due grafi sulla 3-colorabilità di un grafo, vale a dire sulla possibilità di colorare i vertici un grafo con soli tre colori in modo che due vertici tra loro connessi non abbiano mai lo stesso colore. Il computer è il possessore del segreto, e colora il grafo (se possibile…) in quel modo. Noi siamo i verificatori, e possiamo indicare due vertici connessi: il computer ci mostrerà allora come sono colorati. Naturalmente dopo ogni nostra verifica il computer genererà una nuova colorazione, perché altrimenti potremmo man mano testare tutti i vertici e ricavare la colorazione completa del grafo. Il modo turbo fa fare tutto (in fretta) al computer, così potete vedere in pratica le probabilità che il grafo sia stato effettivamente 3-colorato dal computer.

E a chi invece si sta chiedendo perché mai si fa tutta questa fatica per creare dimostrazioni che dimostrazioni non sono, che si può dire? Semplice. Immaginate di dovervi connettere a un sistema non solo senza inviare la password in chiaro – quello lo fate facilmente cifrando il protocollo – ma anche senza che il sistema remoto sappia qual è la vostra password: si sa, fidarsi è bene ma non fidarsi è meglio. Un sistema a conoscenza zero è allora l’ideale: una successione abbastanza lunga di challenge-response darà al computer una sicurezza abbastanza alta che noi conosciamo effettivamente la password. Certo, non la certezza: ma come fa il computer a sapere che la password non ci sia stata rubata da qualcuno che ci sta impersonando? Ricordatevi che la teoria è sempre molto bella, ma bisogna anche tenere conto della pratica!