Ultima puntata, almeno per il futuro prevedibile, sulle dimostrazioni a conoscenza zero. Stavolta il punto di vista è però un po’ diverso: spiegherò cosa c’è filosoficamente dietro a questo tipo di dimostrazioni, basandomi essenzialmente su questo vecchio post di Matthew Green.
Per prima cosa, il concetto nacque una quarantina d’anni fa, come spinoff degli studi sui sistemi di dimostrazione interattiva, dove un Dimostratore deve convincere un Verificatore che una certa affermazione matematica è vera. Il Verificatore ha a disposizione molte meno risorse computazionali del Dimostratore, altrimenti il problema non si porrebbe nemmeno. Fino alla metà degli anni ’80 del secolo scorso gli studi erano orientato sul vedere se il Verificatore poteva avere fiducia del Dimostratore, oppure quest’ultimo poteva fregarlo: Shafi Goldwasser, Silvio Micali e Charles Rackoff hanno pensato invece di rovesciare il punto di vista, chiedendosi “e se fosse il Verificatore quello di cui non ci fidiamo?” L’esempio che fa Green è quello delle password Unix. Il server salva una versione codificata (hash) della password più alcuni caratteri casuali (il salt); quando l’utente si collega manda la password, il sistema ricalcola l’hash e se coincide con quello salvato fa entrare l’utente, perché sa che l’utente conosce la password. Questo però significa che se il server è compromesso allora il cracker vede la password in chiaro: non esattamente una bella idea. Si può fare di meglio? La risposta è stata “(statisticamente) sì: posso avere una probabilità alta a piacere che il Verificatore riesca solo a sapere il bit di informazione “l’affermazione è vera”.
L’esempio fatto è diverso da quello delle due porte fatto la scorsa settimana, e rende forse più l’idea di come vanno le cose: poi il raccontino, pensato originariamente da Micali, è anche divertente. Io ho un grafo molto grande, e vorrei che i vertici fossero colorati con solo tre colori in modo che due vertici adiacenti non abbiano mai lo stesso colore. Questo mi può per esempio servire per una rete di trasmissione radio: due celle troppo vicine non possono usare le stesse frequenze, perché altrimenti i segnali interferirebbero. Il problema è computazionalmente pesante, NP completo: Google ha dirottato un bel po’ delle sue TPU dai chatbot per risolverlo, e adesso mi dice che ha la soluzione e mi chiede i soldi. Siamo però in un vicolo cieco: io non pago se non sono sicuro che la soluzione ci sia davvero, e Google non me la vuole mostrare finché non pago. Che fare? Basta avere un capannone abbastanza grande; pennarelli di tre colori; tanta, tanta carta. E un bel po’ di cappelli, come omaggio ai problemi di logica. Io disegno il mio grafo (diciamo con 1000 archi che uniscono i vertici) su un enorme foglio di carta ed esco; gli amici di Google scelgono a caso un associazione tra i colori dei pennarelli e la colorazione del grafo, e poi mettono un cappello sopra ogni vertice. Quando sono rientrato, scelgo un arco qualunque che connette due vertici. Google toglie i cappelli che coprono i due vertici: se i colori sono identici sono certo che mi aveva preso in giro e non aveva la soluzione, se invece sono diversi potrebbe avere ragione. Certo, avrebbe ancora una probabilità dell’ordine del 99,9% di avere solo avuto fortuna, visto che non posso sapere cosa c’è dietro tutti gli altri archi. Però Google mi dice che posso rifare l’esperimento quante volte voglio. Ogni volta si partirà da un’associazione casuale dei colori, quindi non posso sperare di costruirmi man mano una mappa; in compenso posso sempre scegliere l’arco che voglio. A furia di moltiplicare fattori 0,999 (il 99,9%), la probabilità che sia solo questione di fortuna può essere resa piccola a piacere. C’è persino un gioco interattivo, se volete divertirvi.
La definizione di un protocollo a conoscenza zero, secondo gli autori, deve soddisfare tre proprietà:
- Completezza: se il Dimostratore ha effettivamente una dimostrazione, deve convincere il Verificatore con una probabilità prossima a piacere al 100%.
- Validità: il Dimostratore può convincere il Verificatore solo se effettivamente ha una dimostrazione.
- Conoscenza zero Il Verificatore non avrà nessuna idea di quale possa essere la soluzione.
L’esperimento visto soddisfa sicuramente i primi due punti. Per il terzo, l’equivalente del video editato nell’esempio della settimana scorsa, le cose si fanno più fantascientifiche. Supponiamo che Google non sia in realtà riuscita a trovare una colorazione. In compenso uno dei loro progetti segreti è il prototipo di una macchina del tempo. Essa funziona perfettamente: l’unico problema è che al momento permette di tornare indietro solo di 314,15926… secondi. Avere poco più di cinque minuti è però sufficiente: se si acccorgono che sto scegliendo un arco i cui vertici hanno lo stesso colore, mandano un segnale e un tecnico torna indietro nel tempo, cambiando la colorazione ma lasciandola sempre casuale: il tutto fino a che non si ha uno schema dove i vertici hanno colori diversi. Il tutto senza che io mi possa accorgere di niente, ovviamente. Cosa significa tutto questo? Che se per assurdo io avessi una strategia che “estrae” informazione dopo avere osservato i due colori, estrarrei la stessa informazione anche nel caso che la macchina del tempo fosse stata messa in funzione. Ma in questo secondo caso la soluzione al mio problema non esiste: quindi l’assunto di partenza è falso e io non posso estrarre informazione.
Nell’ambito informatico, tutto questo si ottiene mediante uno “schema d’impegno” (commitment scheme). Il ruolo della macchina del tempo è banalmente il rilanciare il programma corrispondente al Dimostratore più volte. La morale di tutto ciò è che viviamo in un mondo difficile, dove non ci si può mai fidare di nessuno, ma per fortuna la matematica ci aiuta a ritrovare questa fiducia!