#MT04 – Dimostrare di conoscere un segreto senza rivelarlo
Questo è il quarto di una serie di articoli che ci accompagneranno, durante una breve gita nella “tana del coniglio” matematico, alla scoperta di un argomento che tange – come molti altri – lo studio di #bitcoin: la crittografia.
Tradotto dall’originale di Sheon Han – pubblicato il 11 ott 2022
Immaginate di avere una conoscenza utile, magari una ricetta segreta o la chiave di un codice. Potreste dimostrare a un amico di possedere quella conoscenza, senza rivelare nulla? Gli scienziati informatici hanno dimostrato più di 30 anni fa che è possibile, se si utilizza la cosiddetta prova a conoscenza zero (Zero-knowledge proof, n.d.t.).
Per comprendere questa idea in modo semplice, supponiamo di voler mostrare a un amico che si sa come attraversare un labirinto, senza divulgare alcun dettaglio sul percorso. Potreste semplicemente attraversare il labirinto entro un limite di tempo, mentre al vostro amico è vietato guardare. (Il limite di tempo è necessario perché, dato il tempo sufficiente, chiunque può trovare la via d’uscita attraverso tentativi ed errori). Il vostro amico saprebbe che siete in grado di farlo, ma non saprebbe come.
Le prove a conoscenza zero sono utili ai crittografi, che lavorano con informazioni segrete, ma anche ai ricercatori della complessità computazionale, che si occupano di classificare la difficoltà di diversi problemi. “Molta della crittografia moderna si basa su ipotesi di complessità – sull’ipotesi che certi problemi siano difficili da risolvere, quindi c’è sempre stata qualche connessione tra i due mondi“, ha detto Claude Crépeau, informatico della McGill University. “Ma queste prove hanno creato un intero mondo di connessioni“.
Le prove a conoscenza zero appartengono a una categoria nota come prove interattive, quindi per imparare come funzionano le prime è utile capire le seconde. Descritte per la prima volta in un articolo del 1985 dagli informatici Shafi Goldwasser, Silvio Micali e Charles Rackoff, le prove interattive funzionano come un interrogatorio: Attraverso una serie di messaggi, una parte (il prover) cerca di convincere l’altra (il verificatore) che una data affermazione è vera. Una prova interattiva deve soddisfare due proprietà. In primo luogo, un’affermazione vera convincerà sempre un verificatore onesto. In secondo luogo, se l’affermazione data è falsa, nessun prover – anche se finge di possedere una conoscenza certa – può convincere il verificatore, se non con una probabilità trascurabile.
Le prove interattive sono di natura probabilistica. Il prover potrebbe rispondere correttamente a una o due domande semplicemente per fortuna, quindi è necessario un numero sufficientemente elevato di sfide, tutte corrette da parte del prover, perché il verificatore si convinca che il prover sa che l’affermazione è vera.
L’idea delle interazioni è nata quando Micali e Goldwasser – allora studenti laureati presso l’Università della California, Berkeley – si sono interrogati sulla logistica del gioco del poker in rete. Come possono tutti i giocatori verificare che quando uno di loro prende una carta dal mazzo virtuale, il risultato è casuale? Le prove interattive potrebbero aprire la strada. Ma poi, come possono i giocatori verificare che l’intero protocollo – l’insieme delle regole – sia stato seguito correttamente, senza rivelare la mano di ogni giocatore lungo il percorso?
Per raggiungere questo obiettivo, Micali e Goldwasser hanno aggiunto una terza proprietà alle due necessarie per una prova interattiva: La prova non deve rivelare nulla della conoscenza stessa, ma solo la veridicità dell’affermazione. “C’è la nozione di passare attraverso un protocollo, alla fine del quale si crede che [i giocatori di poker] non sappiano nulla di più di ciò che si suppone che sappiano“, ha detto Goldwasser.
Consideriamo l’esempio classico. Alice vuole dimostrare a Bob che un certo grafo G – un insieme unico di vertici (punti) collegati da spigoli (linee) – ha un “ciclo hamiltoniano“. Ciò significa che il grafo ha un percorso che visita ogni punto esattamente una volta e termina nello stesso punto da cui è partito. Alice potrebbe farlo semplicemente mostrando a Bob il percorso che fa questo, ma ovviamente anche lui lo conoscerebbe.
Ecco come Alice può convincere Bob di sapere che esiste un percorso di questo tipo, senza mostrarglielo. Per prima cosa disegna un nuovo grafo, H, che non assomiglia a G ma è simile in un modo cruciale: Ha lo stesso numero di vertici, connessi nello stesso modo. (Se G ha davvero un ciclo hamiltoniano, questa somiglianza significa che lo avrà anche H.) Poi, dopo aver coperto ogni spigolo di H con del nastro adesivo, chiude H in una scatola e la consegna a Bob. Questo impedisce a lui di vederlo direttamente, ma impedisce anche a lei di alterarlo. A questo punto Bob può scegliere: Può chiedere ad Alice di dimostrare che H è davvero simile a G, oppure può chiederle di mostrargli il ciclo hamiltoniano in H. Entrambe le richieste dovrebbero essere facili per Alice, supponendo che H sia davvero abbastanza simile a G e che conosca davvero il percorso.
Naturalmente, anche se Alice non conosce il ciclo hamiltoniano in G, può cercare di ingannare Bob, disegnando grafi non simili a G o presentando grafi di cui non conosce il percorso. Ma dopo aver giocato più volte, la possibilità che Alice inganni Bob ogni volta diventa irrisoria. Se riesce a fare tutto bene, alla fine Bob si convincerà che Alice conosce un ciclo hamiltoniano nel grafo G, senza che Bob l’abbia mai visto.
Dopo l’articolo iniziale che descriveva tali prove, Micali e due matematici – Oded Goldreich e Avi Wigderson – hanno scoperto una conseguenza inaspettata con effetti di vasta portata. Ha a che fare con una grande categoria di problemi di difficoltà approssimativamente uguale, nota come NP. Questi problemi sono difficili da risolvere, ma le loro soluzioni sono facili da verificare. I tre ricercatori hanno scoperto che, se è possibile una crittografia veramente sicura, anche la soluzione di ogni problema NP può essere dimostrata con una prova a conoscenza zero. Questo studio ha aiutato i ricercatori a concepire varianti di prove a conoscenza zero che non richiedono nemmeno una crittografia sicura; queste sono note come prove interattive multi-prover.
Nel 1988 Micali e altri dimostrarono che se un prover e un verificatore condividono una breve stringa di bit casuali, non è necessaria alcuna interazione. In teoria, ciò significa che le prove a conoscenza zero non devono essere interattive, il che implica che non è necessaria una comunicazione costante tra due parti. Ciò le renderebbe molto più utili per i ricercatori, ma solo dopo l’inizio del XXI secolo tali prove hanno preso piede.
“Alla fine degli anni 2000 abbiamo iniziato a vedere l’evoluzione di tecniche efficienti per la costruzione di prove a conoscenza zero“, ha dichiarato Matthew D. Green, crittografo della John Hopkins University. “Siamo arrivati al punto in cui ci siamo resi conto: ‘Aspetta un attimo, potrebbe esserci un modo per usarle in pratica‘”.
Ora un prover può inviare un singolo messaggio a un verificatore senza che entrambi debbano essere online e i ricercatori possono creare una prova molto breve che può essere verificata rapidamente, anche per problemi molto complicati. Questo ha portato a diversi utilizzi pratici, come la possibilità di verificare rapidamente la blockchain dopo una transazione di criptovaluta nascondendo i dettagli della transazione. Nel 2016, inoltre, un gruppo di fisici ha dimostrato come le prove a conoscenza zero possano contribuire al disarmo nucleare: Senza rivelare alcun segreto sulla progettazione della propria testata nucleare, un Paese potrebbe ora dimostrare agli ispettori nucleari se la testata è attiva o inattiva.
Più di recente, i progressi dell’informatica quantistica hanno costretto Crépeau a sottoporre a stress test le ricerche passate per assicurarsi che i protocolli a conoscenza zero siano ancora validi. Nel 2021 ha contribuito a dimostrare che le prove interattive multi-prover mantengono la loro segretezza anche quando sono coinvolti i computer quantistici, ma il raggiungimento dello stesso livello di sicurezza rende il protocollo molto più lento. La scoperta è una buona notizia, ha detto, ma con il progredire della tecnologia sorgeranno nuove preoccupazioni.
“Ogni tipo di calcolo che potremo fare in futuro coinvolgerà i computer quantistici“, ha detto Crépeau. “Quindi, da bravi crittografi paranoici, ogni volta che valutiamo la sicurezza di un sistema, vogliamo assicurarci che il nostro sistema sia sicuro“.
Come acquistare Bitcoin?
Reputo il miglior servizio quello offerto da Relai.
Per acquistare bitcoin risparmiando lo 0,5% in commissioni puoi usare il codice “REL3166”.
Si tratta di un’applicazione sviluppata da un’azienda svizzera che applica una politica di KYC light: a differenza dei grandi exchange non richiede registrazioni o dati personali, tutto ciò che serve per acquistare è il tuo IBAN.
E’ lo strumento ottimale per impostare dei piani di accumulo (DCA).
Per ridurre al massimo le commissioni di acquisto, ti consiglio di:
effettuare acquisti maggiori di 100€ (-0,5%)
impostare un piano di accumulo settimanale o mensile (-0,5%)
applicare il codice invito REL3166 (-0,5%)
Una delle migliori caratteristiche è il servizio non-custodial. Gli euro bonificati a Relai vengono convertiti automaticamente in bitcoin e trasferiti su un wallet di cui sei solo tu ad avere il controllo. I grossi exchange, al contrario, non forniscono le chiavi private ai clienti. In più Relai non vende centinaia di inutili criptovalute, ma solo bitcoin.
Cosa ci guadagno? Quello che fanno guadagnare i referral code. In questo caso se acquisti usando il codice “REL3166” risparmi lo 0,5% sulle commissioni e io ricevo (in bitcoin) lo 0,5% dell’importo che hai deciso di investire.
Per ulteriori informazioni, o per effettuare il primo acquisto, premi sul pulsante sottostante e ti verrà mostrata una dettagliata guida in italiano.
NOTA – Questo NON è un messaggio pubblicitario. Relai è un servizio che utilizzo personalmente e che reputo tra i migliori sul mercato in termini di affidabilità, sicurezza e facilità d’uso. Lo consiglio spesso ad amici e parenti.
Articolo originale: Read More
