Experimental asymmetric relativistic zero-knowledge proofs with unconditional security

Questo articolo presenta un protocollo di prova a conoscenza zero relativistico asimmetrico, efficiente e verificato sperimentalmente, che raggiunge una sicurezza incondizionata contro gli attacchi quantistici sfruttando la relatività speciale e la non località quantistica, superando così l'impraticabile complessità di round dei precedenti approcci simmetrici.

L'essenziale

Il quadro generale: Dimostrare di conoscere un segreto senza rivelarlo

Immagina di avere la mappa segreta per un tesoro e di voler convincere una guardia scettica che in realtà possiedi quella mappa. Non vuoi mostrargli la mappa (perché potrebbe rubartela) e non vuoi dirgli dove si trova il tesoro. Vuoi solo dimostrare: "Io conosco la strada".

Nel mondo digitale, questo viene chiamato Zero-Knowledge Proof (ZKP). È il trucco magico che ti permette di dimostrare chi sei o che hai abbastanza denaro per una transazione, senza rivelare la tua password o il tuo saldo bancario.

Il problema: Il mostro Quantistico

Per decenni, questi trucchi magici digitali si sono basati su enigmi matematici difficili da risolvere per gli umani ma facili per i computer. Tuttavia, gli scienziati stanno costruendo i Computer Quantistici, che sono come mostri super veloci. Questi mostri possono risolvere quei vecchi enigmi matematici quasi istantaneamente, rompendo la sicurezza delle nostre attuali serrature digitali.

Abbiamo bisogno di un nuovo tipo di serratura che non si basi su enigmi matematici, ma che si basi sulle leggi della fisica.

La soluzione: La serratura alla "Velocità della Luce"

Questo articolo introduce un nuovo tipo di prova chiamata Relativistic Zero-Knowledge Proof (Prova a Conoscenza Zero Relativistica). Invece di affidarsi a una matematica difficile, si affida alla Velocità della Luce.

L'analogia: Il Drago a due teste
Immagina di avere un drago con due teste (chiamiamole Testa A e Testa B). Vuoi dimostrare a un giudice che il drago è reale, ma non puoi permettere alle due teste di comunicare tra loro.

• Il giudice sta lontano dalla Testa A.
• Un altro giudice sta lontano dalla Testa B.
• La distanza è così grande che nemmeno un raggio di luce (la cosa più veloce dell'universo) può viaggiare dalla Testa A alla Testa B nel tempo necessario per rispondere a una domanda.

Poiché la Testa A e la Testa B non possono comunicare abbastanza velocemente per coordinare una bugia, sono costrette a dire la verità. Se provano a imbrogliare, le leggi della fisica (specificamente, che nulla viaggia più veloce della luce) le incastrano.

Cosa ha fatto questo team

I ricercatori hanno costruito una versione funzionante di questa prova basata sulla "Velocità della Luce". Ecco come l'hanno migliorata:

1. Il vecchio metodo era troppo lento: I tentativi precedenti di questa prova del "drago a due teste" erano come cercare di risolvere un labirinto gigante percorrendo ogni singolo sentiero uno alla volta. Se la mappa (il grafo) era grande, ci sarebbero voluti migliaia di anni per completare la prova. Era teoricamente possibile ma praticamente inutile.
2. Il nuovo metodo è veloce: Il team ha progettato una versione asimmetrica più intelligente. Pensa a questo come ad avere una testa del drago che fa tutto il lavoro pesante mentre l'altra tiene solo la guardia.
   • Il Risultato: Hanno ridotto il tempo necessario da "migliaia di anni" a 0,22 secondi.
   • Il Costo: Hanno utilizzato un po' più di "casualità" (come mescolare un mazzo di carte più volte), ma la quantità totale di dati utilizzati era comunque piccola abbastanza da poter stare su un moderno hard disk (circa 430 MB).

L'esperimento

Per dimostrare che questo funziona nel mondo reale, hanno allestito un esperimento presso l'Università di Nanjing:

• Hanno posizionato due computer (le "teste") in edifici diversi a 300 metri di distanza.
• Hanno utilizzato laser ad alta velocità e orologi GPS per garantire che i computer non potessero comunicare tra loro più velocemente della luce.
• Hanno chiesto ai computer di dimostrare di sapere come colorare una mappa complessa con solo tre colori (un classico enigma matematico) senza mostrare i colori.
• L'Esito: I computer hanno completato l'intera prova in 0,22 secondi.

Perché questo è importante

L'articolo sostiene che questo sia un passo avanti fondamentale perché:

• È Quantum-Safe (Sicuro contro i computer quantistici): Anche se un computer quantistico cercasse di rompere il codice, non può imbrogliare perché non può infrangere le leggi della fisica (la velocità della luce).
• È Pratico: A differenza delle versioni precedenti che erano troppo lente per essere utilizzate, questa è abbastanza veloce per un uso reale, come proteggere l'online banking o il voto elettronico.
• È Incondizionato: Non si basa sul "pensiamo che questa matematica sia difficile". Si basa sul "sappiamo che la luce ha un limite di velocità".

Riassunto

I ricercatori hanno preso un'idea teorica — usare la velocità della luce per fermare i bugiardi — e hanno costruito una macchina funzionante che lo fa in una frazione di secondo. Hanno risolto il problema della lentezza facendo sì che un lato del sistema facesse più lavoro, il che ha permesso all'intero processo di essere incredibilmente veloce e sicuro contro i futuri computer quantistici.

Sommario tecnico

Riepilogo Tecnico: Sperimentazione di Prove a Conoscenza Zero Relativistiche Asimmetriche con Sicurezza Incondizionata

Definizione del Problema

Le prove a conoscenza zero (Zero-Knowledge Proofs, ZKP) sono fondamentali per stabilire fiducia e privacy nelle economie digitali, come le criptovalute e gli smart contract. Tuttavia, i protocolli ZKP classici si basano su assunzioni computazionali (ad esempio, l'esistenza di funzioni unidirezionali), il che li rende vulnerabili a futuri attacchi quantistici. Sebbene le ZKP quantistiche offrano un potenziale alternativa, esse affrontano ostacoli significativi nell'implementazione, tra cui il teorema di non clonazione che complica il riavvolgimento (rewinding) quantistico, e l'impossibilità di un impegno di bit (bit commitment) quantistico a sicurezza incondizionata.

Le RZKP (Relativistic Zero-Knowledge Proofs) sono emerse come una soluzione, sostituendo le assunzioni computazionali con i principi della relatività speciale (nello specifico, il principio di no-signaling). Un recente progresso ha dimostrato una RZKP simmetrica per il problema del tre-colore dei grafi. Tuttavia, questo protocollo simmetrico soffre di inefficienze proibitive quando deve garantire la sicurezza quantistica (sicurezza contro prover che condividono entanglement quantistico). Per ottenere la sicurezza quantistica, il protocollo simmetrico richiede una complessità di round pari a $O(|E|^4)$ (dove $|E|$ è il numero di archi), portando a tempi di esecuzione irragionevoli e costi di casualità massicci per grafi di dimensioni realistiche.

Metodologia

Gli autori propongono e implementano sperimentalmente un protocollo ZKP GMW relativistico asimmetrico, progettato per superare i limiti di efficienza degli approcci simmetrici precedenti, mantenendo al contempo la sicurezza incondizionata contro prover correlati quantisticamente.

Design del Protocollo

Il protocollo coinvolge due coppie prover-verifier spazialmente separate ($P_1-V_1$ e $P_2-V_2$) e opera su $m$ round interattivi per dimostrare che un grafo $G(V, E)$ è tre-colorabile senza rivelare la colorazione.

1. Preparazione: I prover $P_1$ e $P_2$ condividono una permutazione casuale dei colori $\pi$ e un insieme di valori casuali $B = \{b_k\}$.
2. Fase di Query: Il verifier $V_1$ invia query casuali $X = \{x_k\}$ a $P_1$.
3. Fase di Commitment: $P_1$ calcola i commitment $A = \{a_k\}$ dove $a_k = x_k \cdot y_k - b_k$ (con $y_k$ che rappresenta il colore) e li invia a $V_1$.
4. Fase di Challenge: Il verifier $V_2$ seleziona un arco casuale $C = \{i, j\}$ e lo invia a $P_2$.
5. Fase di Reveal: $P_2$ rivela i colori $Y(C)$ e i corrispondenti valori $B(C)$ a $V_2$.
6. Fase di Controllo: I verifier controllano i vincoli relativistici (assicurando l'assenza di segnalazione tra $P_1$ e $P_2 verificando i ritardi temporali$|t_1 - t_4| < \tau$e$|t_2 - t_3| < \tau$, dove $\tau = d/c$) e la coerenza logica (i colori sono distinti e corrispondono ai commitment).

Analisi Teorica

Gli autori affrontano la sfida della sicurezza quantistica. A differenza dei protocolli classici dove il bit commitment è fortemente vincolante (strongly binding), i bit commitment relativistici garantiscono solo una "somma-vincolatività" (sum-binding). Gli autori dimostrano che la probabilità che prover quantistici maliziosi riescano a barare su un arco non valido è limitata superiormente dal valore quantistico di un gioco non locale CHSH$_{Q(2)}$. Relazionando l'errore di sicurezza del protocollo a questo gioco, derivano un limite superiore rigoroso per l'errore di sicurezza quantistica $\delta$.

Implementazione Sperimentale

Il team ha implementato un esperimento di prova di concetto utilizzando:

• Hardware: FPGA per l'elaborazione a bassa latenza e server di sincronizzazione temporale GPS ad alta precisione (con orologi atomici).
• Setup: Due coppie prover-verifier separate da 300 metri (corrispondenti a una separazione temporale $\tau = 1000$ ns).
• Grafo: Un grafo tre-colorabile con $|V| = 588$ vertici e $|E| = 1097$ archi.
• Esecuzione: L'esperimento ha completato tutti i round interattivi richiesti in circa 0,22 secondi.

Contributi Chiave

1. Protocollo Asimmetrico Efficiente: Gli autori hanno progettato una ZKP GMW relativistica asimmetrica che riduce la complessità di round da $O(|E|^4)$ (nei precedenti protocolli simmetrici con sicurezza quantistica) a $O(|E|)$. Ciò è ottenuto utilizzando bit commitment relativistici a due prover all'interno del framework GMW, permettendo che la prova e i controlli di coerenza avvengano simultaneamente in un singolo round.
2. Prova di Sicurezza Quantistica: Hanno fornito una prova rigorosa della sicurezza quantistica relazionando la probabilità di frode dei prover entangled al gioco non locale CHSH$_{Q(2)}$, stabilendo un limite superiore sull'errore di sicurezza senza fare affidamento su assunzioni computazionali.
3. Realizzazione Sperimentale: Hanno eseguito con successo il protocollo su una separazione di 300 metri, dimostrando che il tempo di esecuzione e il costo di casualità richiesti sono fattibili per un dispiegamento nel mondo reale.

Risultati

• Complessità di Round: Il protocollo richiede $m = 2k|E|$ round per ottenere un errore di sicurezza di $e^{-k}$. Per i parametri sperimentali ($|E|=1097, k=100$), ciò ha comportato circa $2,2 \times 10^5$ round.
• Tempo di Esecuzione: L'intero esperimento si è concluso in 0,22 secondi. Al contrario, il precedente protocollo simmetrico con sicurezza quantistica [23] avrebbe richiesto circa $6,72 \times 10^4$ anni per raggiungere lo stesso livello di sicurezza con lo stesso grafo.
• Costo di Casualità: Il costo totale di casualità per l'esperimento è stato di 430,81 MB. Il protocollo simmetrico [23] avrebbe richiesto circa $5,92 \times 10^9$ GB (5,92 exabyte) per lo stesso compito.
• Sicurezza: Le differenze temporali $|t_1 - t_4|$ e $|t_2 - t_3|$ sono state misurate costantemente al di sotto della soglia di 1000 ns, soddisfacendo i vincoli di no-signaling relativistici anche tenendo conto degli errori di sincronizzazione GPS.

Significato e Rivendicazioni

Il documento afferma che questo lavoro illustra il potente potenziale dell'integrazione della relatività speciale con la teoria quantistica per creare sistemi di fiducia (trustless) sicuri contro attacchi quantistici senza dipendere da assunzioni di durezza computazionale.

Le rivendicazioni chiave riguardanti la significatività includono:

• Fattibilità Pratica: La riduzione della complessità di round da $O(|E|^4)$ a $O(|E|)$ trasforma le RZKP da costrutti teorici in tecnologie effettivamente dispiegabili per scenari reali che coinvolgono grafi di dimensioni ragionevoli.
• Sicurezza Incondizionata: Il protocollo offre sicurezza quantistica e proprietà di zero-knowledge basate esclusivamente sul principio di no-signaling, rendendolo robusto contro i futuri progressi del calcolo quantistico.
• Potenziale di Scalabilità: Sebbene la natura asimmetrica imponga un carico computazionale maggiore su una coppia prover-verifier ($V_1-P_1$), gli autori sostengono che il compromesso sia necessario per ottenere tempi di esecuzione fattibili. Suggeriscono che il protocollo potrebbe essere implementato su dispositivi quotidiani come gli smartphone.
• Applicazioni Future: Gli autori evidenziano potenziali applicazioni in domini sensibili alla privacy come blockchain, smart contract, voto elettronico anonimo e aste online. Notano inoltre la possibilità di estendere questo framework alle Prove di Conoscenza (Zero-Knowledge Proofs of Knowledge, ZKPoK) per la verifica dell'identità.

Gli autori rimangono modesti riguardo alle sfide di scalabilità, riconoscendo che il dispiegamento pratico nelle reti in fibra ottica deve ancora affrontare ostacoli come la verifica della posizione precisa dei prover e la gestione dei carichi computazionali, che identificano come problemi aperti per la ricerca futura.