⚛️ quantum physics

Certified-Everlasting Quantum NIZK Proofs

Gli autori superano le barriere esistenti per costruire prove NIZK quantistiche non interattive per NP con sicurezza statistica e zero-knowledge certificata ed eterna, proponendo due costruzioni nel modello CRS basate su LWE e nel modello EPR condiviso che richiede solo misurazioni di singoli qubit.

Autori originali: Nikhil Pappu

Pubblicato 2026-02-13

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Nikhil Pappu

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Il Problema: La "Fotografia" che non si può cancellare

Immagina di voler dimostrare a un amico che sai la soluzione a un Sudoku molto difficile, senza però rivelargli la soluzione stessa.
Nella crittografia classica, usi un "NIZK" (una prova zero-knowledge non interattiva): mandi un messaggio che dice "Sì, so la soluzione", e lui ti crede.

Il problema è la memoria. Una volta che il tuo amico ha ricevuto quel messaggio, lo può salvare per sempre. Anche se tra 100 anni i computer diventeranno così potenti da rompere la crittografia e leggere la soluzione, lui avrà ancora la sua copia del messaggio. Non c'è modo di fargliela "dimenticare" o cancellare in modo sicuro.

La Soluzione Quantistica: Il "Biglietto d'Autobus" che si autodistrugge

Il paper di Nikhil Pappu introduce un concetto rivoluzionario: le Prove Zero-Knowledge Quantistiche con Cancellazione Certificata (CE-NIZK).

Immagina che invece di un messaggio scritto su carta, tu mandi al tuo amico un biglietto d'autobus fatto di ghiaccio (uno stato quantistico).

La Prova: Il biglietto ti permette di salire sull'autobus (verificare che la soluzione esiste).
La Cancellazione: Dopo aver salito, il biglietto deve sciogliersi. Ma come fai a essere sicuro che si sia sciolto davvero e non che il tuo amico lo abbia nascosto in tasca?
La Certificazione: Il tuo amico ti deve restituire un "scontrino" che prova che il biglietto di ghiaccio si è sciolto. Se il scontrino è valido, sai che il biglietto non esiste più. Se il biglietto non esiste più, e il biglietto conteneva la prova della soluzione, allora la prova è sparita per sempre. Anche se tra 100 anni avrai un computer super-potente, non potrai ricostruire la soluzione perché il "ghiaccio" è davvero fuso.

I Due Scenari del Paper

L'autore affronta questo problema in due modi diversi, come se stesse costruendo due tipi di case su terreni diversi.

1. Il Modello CRS (La Casa con il Terreno Comune)

Immagina che tu e il tuo amico abbiate accesso a una "scatola magica" pubblica (chiamata Common Reference String o CRS) che tutti possono vedere, ma che nessuno controlla.

La Sfida: I ricercatori avevano provato a usare vecchie tecniche per creare questa scatola magica, ma si sono scontrati con un muro: se il biglietto di ghiaccio fosse stato troppo facile da dividere in due parti (una per la prova, una per la cancellazione), il trucco non avrebbe funzionato. Sarebbe stato come se il tuo amico potesse fotocopiare il biglietto prima di scioglierlo.
La Soluzione: L'autore ha inventato un trucco complesso usando due livelli di "scatole" e stati quantistici intrecciati (come se il biglietto fosse fatto di fili invisibili collegati tra loro).
- Invece di mandare la prova diretta, la nasconde dentro un "codice a strappo" (One-Time Pad) basato su stati quantistici speciali (stati BB84).
- Per verificare la cancellazione, il biglietto viene "smontato" e ricontrollato. Se il controllo passa, significa che il codice è stato distrutto in modo irreversibile.
- Risultato: Si ottiene una prova sicura basata su problemi matematici difficili (LWE), che sono resistenti anche ai computer quantistici.

2. Il Modello EPR Condiviso (La Casa con il Giardino Magico)

Qui la situazione è diversa. Immagina che tu e il tuo amico abbiate già in mano due metà di una moneta magica entangled (stati EPR). Queste due monete sono coltele da un filo invisibile: se giri la tua, la sua cambia istantaneamente, anche se è dall'altra parte del mondo.

Il Vantaggio: In questo scenario, il "terreno" non è controllato da nessuno, ma è condiviso. Questo rompe il muro che abbiamo visto prima. Non puoi "dividere" la prova in due parti perché una metà della prova è già nelle mani del tuo amico, non tua!
La Soluzione: L'autore usa un metodo molto più semplice ed elegante, basato su un vecchio concetto chiamato "Generatore di Bit Nascosti".
- Tu e il vostro amico misurate le vostre monete magiche in direzioni specifiche.
- Le misure che ottenete diventano i "bit nascosti" della prova.
- Per cancellare la prova, il tuo amico deve misurare le sue monete in una direzione diversa (quella "di cancellazione"). Questa misurazione distrugge l'informazione originale in modo permanente.
- Risultato: Questo protocollo è molto più efficiente. Richiede solo misurazioni semplici (come guardare una moneta) e calcoli classici, senza bisogno di creare stati quantistici complessi. È come se invece di costruire una casa di ghiaccio complessa, usaste un semplice ghiacciolo che si scioglie da solo.

Perché è Importante?

Privacy Eterna: Anche se in futuro qualcuno scoprirà come rompere la crittografia attuale, le prove che hai "cancellato" oggi rimarranno segrete per sempre. È come bruciare una lettera: anche se qualcuno trova i resti, non può rileggerla.
Sicurezza contro i Giganti: Immagina che una grande azienda (il "prover") voglia dimostrare a un utente comune (il "verifier") che i suoi dati sono corretti. Se l'utente vende i dati a un concorrente potente, il concorrente potrebbe in futuro decifrare tutto. Con questo sistema, l'utente può "cancellare" i dati in modo certificato, rendendo impossibile al concorrente recuperarli, anche con computer infinitamente potenti.
Fattibilità: Il paper dimostra che questo non è solo un sogno teorico, ma può essere costruito usando assunzioni matematiche che oggi consideriamo sicure (come LWE), sia nel modello classico condiviso che in quello quantistico condiviso.

In Sintesi

Il paper ci dice: "Sì, possiamo creare prove matematiche che, una volta verificate, possono essere cancellate in modo che nessuno, nemmeno un dio dell'informatica del futuro, possa mai recuperarle."

È come se potessimo scrivere un segreto su un foglio di carta che, una volta letto, si trasforma in cenere e il lettore deve consegnarti la cenere per provare che non ha più il foglio. E la cosa incredibile è che questo sistema funziona davvero, sia con le regole del mondo classico (ma con un tocco quantistico) sia con le regole del mondo quantistico puro.

1. Il Problema

Il lavoro si concentra sullo sviluppo di Proofs of Non-Interactive Zero-Knowledge (NIZK) per la classe di complessità NP che soddisfino tre proprietà critiche simultaneamente:

Sicurezza Statistica (Soundness): Un prover disonesto non può convincere il verificatore di una dichiarazione falsa, anche se possiede potenza di calcolo illimitata.
Zero-Knowledge Computazionale: Un verificatore onesto ma computazionalmente limitato non apprende nulla oltre alla validità della dichiarazione.
Zero-Knowledge Certificato-Eterno (Certified-Everlasting Zero-Knowledge - CE-ZK): Questa è la proprietà innovativa. Permette al verificatore di "revocare" la prova fornendo un certificato di cancellazione. Se la cancellazione viene verificata con successo, lo stato del verificatore può essere simulato in modo statisticamente indistinguibile basandosi solo sulla dichiarazione, garantendo che l'informazione sia stata distrutta in modo permanente, anche se il verificatore diventa successivamente computazionalmente illimitato.

La sfida principale risiede nel fatto che, nel modello classico, è impossibile ottenere simultaneamente soundness statistica e zero-knowledge statistica (a meno di linguaggi molto ristretti). L'approccio quantistico cerca di risolvere questo compromesso permettendo la cancellazione certificata, ma l'estensione di queste proprietà ai protocolli non interattivi (NIZK) ha finora rappresentato un ostacolo teorico significativo.

2. Metodologia e Approcci

L'autore analizza due modelli di setup distinti per costruire questi protocolli: il modello Common Reference String (CRS) e il modello Shared EPR (entanglement condiviso).

A. Identificazione di un Ostacolo Teorico (Impossibilità)

Il lavoro inizia identificando una barriera fondamentale per i protocolli NIZK nel modello CRS. Viene definita una classe di protocolli chiamati "Deletion-Resistant CE-NIZK", in cui l'algoritmo di cancellazione separa lo stato della prova in due registri: uno per la verifica della cancellazione e uno per la verifica della prova stessa.

Risultato: Viene dimostrato che l'esistenza di tali protocolli implicherebbe l'esistenza di un NIZK che è sia statisticamente sicuro (soundness) che statisticamente zero-knowledge, una combinazione che è considerata improbabile (o impossibile) per NP.
Conseguenza: Le generalizzazioni dirette dei protocolli interattivi esistenti (basati su commitment o paradigmi Fiat-Shamir) cadono in questa categoria e falliscono nel contesto non interattivo.

B. Soluzione nel Modello CRS (Common Reference String)

Per aggirare l'impossibilità nel modello CRS, l'autore propone una costruzione originale che evita la separazione diretta dello stato:

Idea Chiave: Utilizzare uno stato quantistico "non clonabile" (stati BB84) intrecciato con prove NIZK.
Costruzione a Due Livelli:
1. Viene generata una prova NIZK interna ( $\pi_{in}$ ) per la dichiarazione.
2. Questa prova viene cifrata con una One-Time Pad (OTP) derivata da stati BB84.
3. Vengono generate prove NIZK "esterne" in sovrapposizione quantistica che dimostrano la validità della dichiarazione cifrata.
Tecniche Avanzate:
- Tecnica dei Due Slot (Two-Slot Technique): Utilizzata per gestire la sostituzione bit-per-bit della prova reale con una prova simulata senza violare la sicurezza.
- Prova OR: Le prove esterne dimostrano una disgiunzione logica che permette di sostituire la prova interna con una simulata mantenendo la validità.
- Zero-Knowledge Quantistico-Sicuro: Si richiede che il NIZK sottostante sia sicuro contro avversari quantistici che fanno query in sovrapposizione.
Assunzioni: Il protocollo si basa sull'ipotesi di difficoltà polinomiale del problema LWE (Learning With Errors) e sull'esistenza di funzioni pseudo-casuali quantistiche (QPRF).

C. Soluzione nel Modello Shared EPR (Entanglement Condiviso)

L'autore osserva che l'ostacolo dell'impossibilità non si applica quando prover e verificatore condividono inizialmente coppie EPR (stati entangled).

Vantaggio: Nel modello EPR, il prover non controlla l'intero stato quantistico (poiché metà appartiene al verificatore), rendendo impossibile l'attacco di "splitting" (separazione) che porta all'impossibilità nel modello CRS.
Costruzione: Si utilizza il paradigma dei Hidden Bits (bit nascosti).
- Le coppie EPR vengono misurate in basi scelte casualmente per generare bit nascosti condivisi.
- Un generatore di bit nascosti (HBG) vincola le basi di misurazione.
- Il verificatore cancella i bit non aperti misurando le proprie metà EPR nella base di Hadamard.
Efficienza: Questo protocollo è estremamente efficiente dal punto di vista quantistico: richiede solo misurazioni di singoli qubit (in base computazionale o di Hadamard) e calcolo classico, a differenza del protocollo CRS che richiede operazioni su stati altamente entangled.

3. Contributi Chiave

Definizioni Formali: Introduzione delle definizioni precise per i CE-NIZK nei modelli CRS e Shared EPR.
Teorema di Impossibilità: Dimostrazione che una classe naturale di approcci (Deletion-Resistant) per i CE-NIZK nel modello CRS porta a contraddizioni teoriche (soundness e ZK statistica simultanee).
Costruzione CRS: Prima realizzazione di CE-NIZK per NP nel modello CRS basata su assunzioni standard (LWE), superando la barriera identificata tramite l'uso di prove NIZK in sovrapposizione quantistica e stati BB84.
Costruzione EPR: Realizzazione di un CE-NIZK altamente efficiente nel modello Shared EPR basato su qualsiasi generatore di bit nascosti statisticamente vincolante (HBG), anch'esso derivabile da LWE.
Analisi Comparativa: Distinzione chiara tra CE-NIZK e altre primitive quantistiche come i NIZK "unclonable" (non clonabili), evidenziando che la proprietà di cancellazione certificata non implica necessariamente l'impossibilità di clonazione nel senso stretto di altri lavori recenti.

4. Risultati Principali

Teorema 2.4 & Corollario 2.5: Esistono CE-NIZK per NP nel modello CRS basati sulla durezza polinomiale di LWE, soddisfacenti soundness statistica, ZK computazionale e CE-ZK.
Teorema 2.6 & Corollario 2.7: Esistono CE-NIZK per NP nel modello Shared EPR basati su generatori di bit nascosti (HBG) statisticamente vincolanti (realizzabili con LWE). Questo protocollo richiede solo misurazioni a singolo qubit, rendendolo molto più pratico per l'implementazione hardware rispetto alla versione CRS.
Sicurezza: Entrambi i protocolli garantiscono che, una volta verificata la cancellazione, lo stato residuo del verificatore è statisticamente indistinguibile da uno stato simulato, anche se l'avversario diventa illimitato in futuro.

5. Significato e Impatto

Questo lavoro è significativo per diversi motivi:

Superamento di Limiti Teorici: Risolve il problema aperto della fattibilità dei NIZK con proprietà di cancellazione certificata eterna, un obiettivo che sembrava irraggiungibile a causa delle barriere di impossibilità nel modello non interattivo.
Sicurezza a Lungo Termine: Offre una soluzione per scenari in cui la privacy deve essere garantita non solo contro avversari attuali, ma anche contro futuri avversari con potenza di calcolo illimitata (es. computer quantistici futuri), purché venga eseguita una procedura di cancellazione verificabile.
Flessibilità dei Modelli: Dimostra che la scelta del modello di setup (CRS vs EPR) è cruciale. Mentre il modello CRS richiede complessità quantistiche elevate (sovrapposizione di prove), il modello EPR offre un'alternativa efficiente e pratica, aprendo la strada a implementazioni reali in reti quantistiche dove l'entanglement è disponibile.
Fondamento per Future Applicazioni: Stabilisce le basi per primitive crittografiche avanzate (come firme digitali, identificazione, calcolo verificabile) che devono resistere a minacce future, integrando la cancellazione certificata come feature nativa.

In sintesi, il paper di Pappu fornisce un quadro teorico solido e costruzioni concrete per i NIZK quantistici con cancellazione certificata, risolvendo problemi di impossibilità e offrendo soluzioni pratiche ed efficienti basate su assunzioni standard della crittografia post-quantistica.