⚛️ quantum physics

MPC in the Quantum Head (or: Superposition-Secure (Quantum) Zero-Knowledge)

Questo articolo generalizza il paradigma MPC-in-the-head all'ambito quantistico, consentendo la costruzione di argomenti di conoscenza zero a tre round sia per NP che per QMA nel modello a stringa di riferimento comune che rimangono sicuri contro gli attacchi di sovrapposizione basati sul paradigma standard Learning With Errors (LWE).

Autori originali: Andrea Coladangelo, Ruta Jawale, Dakshita Khurana, Giulio Malavolta, Hendrik Waldner

Pubblicato 2026-07-08

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Andrea Coladangelo, Ruta Jawale, Dakshita Khurana, Giulio Malavolta, Hendrik Waldner

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 quadro generale: Dimostrare di conoscere un segreto senza rivelarlo

Immagina di avere una password segreta (un "testimone") che dimostra che hai il permesso di entrare in un edificio sicuro. Vuoi convincere una guardia (il "verificatore") che conosci la password senza però dirgli effettivamente quale sia. Questo è chiamato Zero-Knowledge Proof (Prova a Conoscenza Zero).

Nel mondo classico (il mondo dei computer normali), esiste un trucco famoso chiamato "MPC-in-the-Head" per farlo.

L'analogia: Immagina di essere una singola persona, ma fingi di essere un team di cinque amici seduti in una stanza. Dividi la tua password segreta in cinque pezzi (share) e dai un pezzo a ciascuno di questi "amici" dentro la tua testa.
Il gioco: Gestisci una conversazione tra questi cinque amici per dimostrare che la password funziona. Poi, la guardia chiede di vedere gli appunti di appena due di loro.
Il risultato: Se gli appunti corrispondono e hanno senso, la guardia è convinta che l'intero team (e quindi tu) conosca la password. Ma poiché la guardia ha visto solo due amici, non può capire la password completa.

Il nuovo problema: Il ladro della "Sovrapposizione"

Questo saggio affronta un nuovo e spaventoso problema: E se la guardia fosse un computer quantistico?

Nel mondo quantistico, una "sovrapposizione" è come essere in due posti contemporaneamente. Un avversario quantistico (il cattivo) non chiede solo di vedere gli appunti dell'Amico A o dell'Amico B. Può chiedere di vedere una sovrapposizione di entrambi contemporaneamente.

La metafora: Immagina che la guardia non si limiti a guardare il foglio; metta il foglio in una scatola magica che gli permette di sbirciare in ogni possibile combinazione di appunti degli amici simultaneamente.
Il rischio: Nei vecchi trucchi, se mostravi solo due amici, il segreto era al sicuro. Ma se la guardia può sbirciare in una "sovposizione" degli appunti, potrebbe essere in grado di ricostruire matematicamente l'intera password, rompendo la sicurezza.

Gli autori si chiedono: Possiamo costruire una prova a conoscenza zero che rimanga sicura anche se la guardia usa questo superpotere della "sovrapposizione"?

La soluzione: "MPC in the Quantum Head"

Gli autori dicono di sì, e lo fanno aggiornando il trucco "MPC-in-the-Head" per il mondo quantistico. Chiamano il loro nuovo metodo "MPC in the Quantum Head".

Ecco come risolvono le due sfide principali:

1. Per segreti regolari (Problemi NP)

Il vecchio problema: I tentativi precedenti di rendere questo metodo sicuro per il mondo quantistico si basavano su un tipo speciale di "serratura magica" (un sistema di impegno o commitment scheme) che fosse perfettamente nascosto. Ma nessuno sa come costruire queste serrature usando la matematica standard.
Il nuovo trucco: Gli autori utilizzano un tipo diverso di serratura chiamato "Dual-Mode Commitment".
- L'analogia: Immagina una cassaforte che ha due chiavi.
  - Chiave A (Binding/Vincolante): La cassaforte è chiusa ermeticamente. Una volta messo un appunto all'interno, non puoi più cambiarlo. Ma se hai un computer super potente, potresti essere in grado di indovinare l'appunto.
  - Chiave B (Hiding/Nascosta): La cassaforte è così opaca che nemmeno un computer super potente può vedere cosa c'è dentro. Ma, se hai una "porta sul retro" speciale (che il prover possiede), puoi aprirla per rivelare qualsiasi cosa tu voglia.
- Come funziona: Il prover usa la modalità "Hiding" per inviare gli appunti. Poiché gli appunti sono nascosti, la guardia quantistica non può apprendere il segreto anche se li guarda in sovrapposizione. Gli autori dimostrano che anche con questa serratura leggermente più debole, la matematica regge.

2. Per segreti quantistici (Problemi QMA)

Questa è la parte più difficile. E se il segreto stesso fosse uno stato quantistico (come una delicata, invisibile nuvola di probabilità) piuttosto che una semplice password?

La sfida: Nella versione classica, gli "amici" si passano appunti avanti e indietro. Nella versione quantistica, gli "amici" si passano particelle quantistiche (qubit). Non puoi semplicemente "scrivere" gli appunti di una particella quantistica senza distruggere il segreto. Non esiste una "trascrizione" da controllare.
Il nuovo trucco: Gli autori utilizzano una tecnica chiamata "Circuit-to-Hamiltonian Reduction".
- L'analogia: Immagina che la conversazione quantistica tra gli amici sia un film. Di solito, non puoi controllare il film senza guardarlo tutto.
- Inveve, trasformano il film in una scultura congelata (un Hamiltoniano). Questa scultura ha una forma specifica. Se gli amici hanno giocato correttamente, la scultura ha un'energia molto bassa (è liscia e perfetta). Se hanno imbrogliato, la scultura è irregolare e ha un'energia alta.
- Il controllo: La guardia non chiede di vedere l'intero film. Si limita a toccare la scultura in alcuni punti casuali per misurarne l'energia.
  - Se l'energia è bassa, il gioco è stato giocato correttamente.
  - Poiché la scultura è fatta di molte piccole parti, toccare alcuni punti non rivela l'intero film (il segreto).
Il "Quantum Head": Il prover divide il segreto quantistico tra gli amici, lo cripta e crea questa "scultura congelata" della conversazione. La guardia controlla l'energia della scultura.

Perché questo è importante (secondo il saggio)

Il saggio sostiene di aver costruito due strumenti specifici:

Una prova per segreti regolari (NP): Funziona sulla base di un problema matematico standard chiamato LWE (Learning With Errors), che si ritiene sia difficile anche per i computer quantistici.
Una prova per segreti quantistici (QMA): Questo è un grande passo avanti. È la prima volta che una prova a conoscenza zero per problemi quantistici è stata costruita in modo da essere sicura contro questi attacchi di "sovrapposizione", basandosi anch'essa sull'assunzione LWE.

Riassunto

Il saggio prende un classico trucco per dimostrare segreti ("MPC-in-the-Head"), lo aggiorna per gestire la meccanica quantistica e risolve il problema degli "attacchi di sovrapposizione". Lo fanno:

Utilizzando serrature speciali a "doppia modalità" che sono difficili da scassinare anche per i computer quantistici.
Trasformando le conversazioni quantistiche in "sculture congelate" (Hamiltoniani) che possono essere controllate senza rivelare il segreto.

Ciò assicura che anche se un futuro computer quantistico cercasse di sbirciare in una prova in una "sovrapposizione" di tutte le possibilità, il segreto rimarrebbe al sicuro.

Sintesi Tecnica: MPC nella Testa Quantistica (Superposition-Secure Zero-Knowledge)

Definizione del Problema

Il documento affronta la costruzione di protocolli di Zero-Knowledge (ZK) che rimangano sicuri anche quando un verificatore malizioso può emettere sfide e ricevere risposte in superposizione quantistica. Questa "sicurezza in superposizione" è un rafforzamento critico della sicurezza classica, motivato da scenari in cui avversari quantistici potrebbero interagire con dispositivi crittografici classici o dove primitivi classici sono inseriti all'interno di protocolli quantistici più ampi.

Sebbene Damgård et al. [19] abbiano anticipato questa nozione per NP, la loro costruzione si basava su impegni dual-mode perfettamente occulti e incondizionatamente vincolanti (perfectly hiding and unconditionally binding dual-mode commitments), un primitivo che non è noto esistere sotto assunzioni crittografiche standard. Inoltre, le loro tecniche non si estendevano naturalmente a QMA (Quantum Merlin-Arthur), l'analogo quantistico di NP, a causa della difficoltà fondamentale di verificare computazioni quantistiche senza rivelare la testimonianza (witness) quantistica.

Le alternative esistenti, come le prove Non-Interactive Zero-Knowledge (NIZK), sono o sconosciute per QMA sotto assunzioni standard o si basano su modelli euristici (ad esempio, oracoli quantistici casuali o obfuscation). Inoltre, le NIZK sono generalmente più pesanti rispetto ai $\Sigma$ -protocol a tre round preferiti per efficienza.

Metodologia

Gli autori propongono una generalizzazione del paradigma MPC-in-the-Head [30] nel contesto quantistico, denominata "MPC nella Testa Quantistica" (MPC in the Quantum Head). La metodologia principale prevede due costruzioni distinte ma correlate:

1. ZK Sicuro in Superposizione per NP

Gli autori rivisitano il protocollo di Damgård et al. [19] ma sostituiscono il requisito di impegni perfettamente occulti con impegni dual-mode (statisticamente occulti e computazionalmente vincolanti in un modo; perfettamente vincolanti e computazionalmente occulti nell'altro).

Tecnica: La strategia di prova utilizza un argomento ibrido. Nel mondo reale, gli impegni sono verso le viste (views) dell'MPC. In un ibrido, gli impegni vengono commutati nella modalità statisticamente occulta. Crucialmente, gli autori introducono un ibrido in cui il prover si impegna su 0 (invece che sulle viste oneste) ma può comunque aprirli alle viste oneste utilizzando la proprietà di vincolo computazionale (che viene violata da un simulatore illimitato).
Argomento di Sicurezza: Una volta che gli impegni sono su 0, le viste aperte (un sottoinsieme di share) e gli impegni non aperti formano uno schema di condivisione segreta (secret sharing) perfettamente sicuro. Gli autori sfruttano un lemma di [19] affermando che la condivisione segreta perfetta rimane sicura contro attacchi in superposizione se meno di $2t$ share vengono interrogati (dove $t$ è la soglia di privacy). Ciò consente alla prova di sicurezza di procedere senza richiedere impegni perfettamente occulti.

2. MPC nella Testa Quantistica per QMA

Estendere questo a QMA richiede la gestione di testimonianze quantistiche e circuiti di verifica quantistici.

L'Ostacolo: Nella classica MPC-in-the-Head, il prover rivela le "viste" (transcripts) delle parti. Nella Computazione Multiparty Quantistica (MPQC), le parti scambiano messaggi quantistici, il che significa che non esiste un transcript classico da rivelare; una parte possiede solo uno stato quantistico finale.
La Soluzione: Gli autori modellano il protocollo MPQC globale come un circuito quantistico (sostituendo il passaggio di messaggi con gate SWAP). Applicano la riduzione Circuito-all'Hamiltoniana di Kitaev [34] a questo circuito.
- La "testimonia" diventa lo stato di storia (history state) dell'Hamiltoniana, che ha energia bassa se e solo se l'MPQC accetta.
- Il prover si impegna su questo stato di storia (qubit per qubit) utilizzando un Quantum One-Time Pad (QOTP) e si impegna sulle chiavi del QOTP usando impegni dual-mode.
- Il verificatore sfida il prover ad aprire specifici qubit corrispondenti ai termini locali dell'Hamiltoniana.
Verifica: Il verificatore misura i qubit aperti per controllare i termini dell'Hamiltoniana locale. Se l'energia è bassa, lo stato di storia corrisponde a un'esecuzione valida.
Zero-Knowledge: La proprietà ZK si basa sul fatto che l'apertura di un sottoinsieme di qubit corrispondenti a un termine dell'Hamiltoniana locale non rivela più informazioni di quanto non rivelerebbe il controllo di un sottoinsieme di parti nel sottostante MPQC. Gli autori utilizzano un protocollo MPQC perfettamente $2t$ -privato [17, 39] per garantire che lo stato di storia della computazione su una testimonianza condivisa segretamente rimanga indistinguibile da uno stato di storia su un input fittizio (dummy), anche sotto query in superposizione.

Contributi Chiave

Generalizzazione di MPC-in-the-Head: Il documento presenta la prima istanziazione del paradigma MPC-in-the-Head per funzionalità quantistiche (MPQC), creando efficacemente una "Quantum MPC-in-the-Head".
ZK Sicuro in Superposizione per NP: Gli autori costruiscono un $\Sigma$ -protocol a tre round per NP sicuro contro attacchi in superposizione basato su qualsiasi impegno dual-mode post-quantum (ad esempio, da LWE). Questo migliora [19] eliminando la necessità di impegni non standard perfettamente occulti.
ZK Sicuro in Superposizione per QMA: Il documento costruisce il primo $\Sigma$ -protocol a tre round per QMA sicuro contro attacchi in superposizione, basato sull'assunzione Learning With Errors (LWE). Questo colma una lacuna per cui non esistono NIZK per QMA sotto assunzioni standard.
Nuove Tecniche di Prova:
- Un nuovo argomento ibrido per NP che commuta gli impegni su 0 per sfruttare le proprietà della condivisione segreta perfetta contro gli attacchi in superposizione.
- Una tecnica per QMA che combina la riduzione Circuito-all'Hamiltoniana con MPQC e QOTP, utilizzando l'indistinguibilità delle coppie EPR e dei one-time pad per simulare il protocollo in presenza di query in superposizione.

Risultati

Il documento stabilisce i seguenti teoremi (informali):

Teorema 1.1: Assumendo la sicurezza post-quantum di LWE, esistono $\Sigma$ -protocol a tre round per QMA nel modello della Stringa di Riferimento Comune (CRS) che soddisfano lo zero-knowledge contro verificatori maliziosi che effettuano query in superposizione.
Teorema 1.2: Assumendo l'esistenza di qualsiasi impegno dual-mode post-quantum, esistono $\Sigma$ -protocol a tre round per NP nel modello CRS che soddisfano lo zero-knowledge contro verificatori maliziosi che effettuano query in superposizione.

I protocolli raggiungono la solidità statistica (statistical soundness) e lo zero-knowledge computazionale (anche contro avversari quantistici a tempo polinomiale con accesso alla superposizione).

Significato e Rivendicazioni

Gli autori posizionano questo lavoro come un'estensione naturale e necessaria della crittografia zero-knowledge nel regime quantistico.

Importanza Teorica: Risolve il problema aperto della costruzione di ZK sicuro in superposizione per QMA sotto assunzioni standard, un compito precedentemente ritenuto difficile a causa della mancanza di NIZK o schemi di impegno adeguati.
Rilevanza Pratica: La struttura a tre round rende questi protocolli significativamente più leggeri rispetto alle NIZK, offrendo una via pratica per firme post-quantum e compilatori di computazione multiparty sicura (ad esempio, compilatori stile GMW) che devono rimanere sicuri contro avversari quantistici capaci di attacchi in superposizione.
Avanzamento Concettuale: Il framework "MPC nella Testa Quantistica" è presentato come una tecnica generalizzabile che potrebbe essere applicata ad altri protocolli commit-and-open o cut-and-choose che richiedono la verifica parziale di computazioni quantistiche.

Il documento nota esplicitamente che, sebbene esistano NIZK per QMA in modelli a oracolo o con verificatori designati, il loro focus su protocolli a tre round con assunzioni standard e setup pubblico (CRS) fornisce una soluzione più diretta ed efficiente per il modello di minaccia specifico degli attacchi in superposizione.