Riepilogo Tecnico: Operazioni su Insiemi Quantistici Privati Verificabili e Resistenti alla Collusione tra Più Parti

1. Definizione del Problema

Le Operazioni su Insiemi Privati (PSO), inclusi l'Intersezione di Insiemi Privata (PSI) e l'Unione (PSU), sono fondamentali per il Calcolo Multipartitico Sicuro (SMC). Sebbene esistano soluzioni crittografiche classiche, l'avvento degli algoritmi quantistici (ad es. l'algoritmo di Shor) minaccia gli attuali schemi basati sulla teoria dei numeri. Di conseguenza, la ricerca si è spostata verso la QPSI (Quantum Private Set Intersection).

Tuttavia, gli esistenti protocolli di QPSO (Quantum PSO) affrontano limitazioni significative:

• Modelli di Minaccia: La maggior parte degli schemi QPSI quantistici esistenti assume la presenza di un Terzo Parte (TP) semi-onesto o si basa sul presupposto che il TP non possa colludere con alcun partecipante.
• Resistenza alla Collusione: I precedenti protocolli di MP-QPSI (Multi-Party QPSI) spesso non riescono a resistere alla collusione tra il TP e un sottoinsieme di partecipanti, oppure tollerano solo la corruzione di un singolo partecipante.
• Verificabilità: Molti schemi mancano di meccanismi per verificare che il TP abbia eseguito correttamente il circuito quantistico prescritto, lasciando il sistema vulnerabile a deviazioni maliziose.

2. Metodologia

Gli autori propongono un protocollo di Intersezione di Insiemi Privati Quantistici Multipartitici (MP-QPSI) che integra la Crittografia Omomorfa Quantistica Completamente Fullemente Verificabile (vQFHE) con la Crittografia Omomorfa Completa a Soglia (TFHE). Il protocollo opera in un modello che coinvolge $n$ partecipanti detentori di dati, un potente TP quantistico e un'Autorità Fidata (TA).

Componenti Core

1. Gestione delle Chiavi a Soglia (TFHE):

   • La chiave segreta per la decrittazione è condivisa tra $n$ partecipanti utilizzando uno schema di condivisione del segreto a soglia $(t, n)$.
   • La decrittazione richiede la collaborazione di almeno $t$ partecipanti. Ciò garantisce che né un sottoinsieme di partecipanti corrotti né una collusione tra il TP e meno di $t$ partecipanti possano recuperare la chiave segreta o apprendere gli input privati.

2. Valutazione Quantistica Verificabile (vQFHE):

   • Il protocollo utilizza la costruzione TrapTP (da [ADS+17]) come livello vQFHE.
   • Cifratura: I partecipanti codificano i loro set privati in stati quantistici utilizzando codici CSS, aggiungono qubit di trappola ($|0\rangle$ e $|+\rangle$), applicano una permutazione casuale e mascherano il risultato con un Quantum One-Time Pad (QOTP). Le chiavi QOTP sono cifrate sotto TFHE e autenticate con codici di autenticazione del messaggio (MAC).
   • Valutazione: Il TP esegue l'evaluazione omomorfa di un circuito AND multi-party ($C_{\text{AND}}$) sugli stati quantistici cifrati. Il TP aggiorna le chiavi QOTP cifrate in modo omomorfo e consuma "gadget" (stati magici) per gestire i gate non-Clifford (T), seguendo il modello "garden-hose".
   • Verifica: Il TP genera un trascritto classico (log) dell'valutazione. I partecipanti e la TA verificano questo log rispetto ai MAC, al set di gate e alle misurazioni del codice di trappola per garantire che il TP non abbia deviato dal circuito target.

3. Flusso del Protocollo:

   • Fase 1 (Preparazione): La TA genera le chiavi, campiona le permutazioni, prepara i gadget per i gate T e distribuisce le quote segrete.
   • Fase 2 (Cifratura): I partecipanti codificano i loro set in stati quantistici, applicano le trappole e il QOTP, e inviano gli stati cifrati e le chiavi al TP.
   • Fase 3 (Valutazione): Il TP esegue il circuito $C_{\text{AND}}$ in modo omomorfo, aggiornando le chiavi e registrando un trascritto.
   • Fase 4 (Verifica e Decrittazione): I partecipanti eseguono la verifica classica (controllo di MAC, gate e trascritto) e la decrittazione a soglia per recuperare le chiavi QOTP. La TA esegue la verifica quantistica (controlli della trappola) e decripta lo stato finale per trasmettere il risultato dell'intersezione.

3. Contributi Principali

• Estensione Multipartitica: Gli autori estendono la vQFHE a un contesto multi-party combinandola con la TFHE, consentendo a $n$ parti di calcolare le intersezioni di set senza rivelare i dati privati.
• Resistenza alla Collusione: A differenza dei precedenti schemi QPSI, questo protocollo resiste alla collusione tra il TP e fino a $t-1$ partecipanti. Il meccanismo a soglia assicura che finché meno di $t$ parti sono corrotte, la chiave segreta e gli input privati rimangono sicuri.
• Verificabilità contro un TP Malizioso: Il protocollo fornisce sicurezza semantica e verificabilità. Può rilevare se un TP malizioso devia dal circuito prescritto (ad es. alterando il set di gate o l'output) attraverso una combinazione di verifica del trascritto classico e controlli del codice di trappola quantistico.
• Framework Modulare: La costruzione è presentata come un framework modulare. Gli autori dimostrano come:
  • Ridurre la complessità del circuito (ad es. usando gate CCCZ invece di $C_nX$ per ridurre il numero di gate T).
    • Estendere la funzionalità alla Unione di Insiemi Privata Quantistica (QPSU) sostituendo il circuito AND con un circuito OR tramite operazioni a controllo aperto.
  • Sostituire le istanze sottostanti di vQFHE per diversi compromessi tra efficienza e sicurezza.

4. Risultati e Analisi

• Correttezza: Gli autori hanno validato il gate AND multi-party logico utilizzando la piattaforma IBM Quantum e Qiskit. Le simulazioni hanno confermato che la distribuzione dell'output corrisponde alla tabella di verità ideale per l'operazione logica AND.
• Dimostrazioni di Sicurezza:
  • Privacy: Il protocollo è dimostrato essere sicura dal punto di vista dell'informazione contro il TP riguardo agli stati quantistici (grazie al QOTP e agli stati massimamente mescolati) e computazionalmente sicura riguardo ai dati classici (grazie a TFHE e MAC).
  • Collusione: Il Teorema 3 dimostra che qualsiasi coalizione di partecipanti corrotti (dimensione $<t$) in collusione con il TP non ottiene alcuna informazione oltre al risultato dell'intersezione.
  • Verificabilità: Sotto il modello di sicurezza semantica ($\kappa$-SEM-VER), il protocollo è mostrato essere verificabile. Un argomento ibrido dimostra che qualsiasi deviazione da parte del TP viene rilevata con una probabilità schiacciante.
• Performance:
  • Complessità di Comunicazione: Il costo di comunicazione quantistica è $O(n\kappa L)$, dove $n$ è il numero di parti, $\kappa$ è il parametro di sicurezza e $L$ è la dimensione del set.
  • Confronto: Rispetto agli schemi esistenti (ad es. [SMZ+15], [ZLS+20], [HZZ24]), il protocollo proposto è l'unico che supporta scenari multi-party con capacità sia di PSI che di PSU, offrendo al contempo resistenza alla collusione TP-partecipante e al comportamento malizioso del TP.

5. Significato e Rivendicazioni

Il documento afferma di offrire un avanzamento significativo nel campo del calcolo sicuro quantistico affrontando il vuoto della "collusione TP-partecipante" che affligge le attuali soluzioni QPSI.

• Robustezza: Integrando la TFHE, il protocollo raggiunge un livello di resistenza alla collusione precedentemente assente nella QPSI, garantendo la sicurezza anche se il TP e un sottoinsieme di partecipanti complottano.
• Minimizzazione della Fiducia: Lo strato di verificabilità consente al sistema di funzionare in modo sicuro anche se il TP è malizioso, eliminando la necessità di fidarsi dell'onestà del TP, richiedendo solo la sua capacità computazionale.
• Flessibilità: Il design modulare consente al framework di essere adattato per diverse operazioni su insiemi (Unione, Cardinalità) e ottimizzato per diversi vincoli hardware (ad es. riduzione della complessità dei gate T).

Gli autori riconoscono che, sebbene il protocollo offra una forte sicurezza, eredita l'overhead classico associato alla vQFHE basata su TrapTP. Si suggerisce che il lavoro futuro esplori la gestione dei gate T senza gadget e ulteriori ottimizzazioni per ridurre i costi di comunicazione classica.