Quantum Multi-Party Threshold Private Set Intersection with Explicit Cardinality Testing

Sintesi Tecnica: Intersezione di Insiemi Privati con Soglia Multi-Party Quantistica con Test di Cardinalità Esplicito

Definizione del Problema
L'Intersezione di Insiemi Privati (PSI) consente alle parti di calcolare l'intersezione dei propri insiemi privati senza rivelare gli elementi non intersecanti. La Threshold PSI (TPSI) estende questo concetto permettendo di rivelare l'intersezione solo se la sua cardinalità soddisfa o supera una soglia pubblica $\tau$. Sebbene esistano protocolli classici di TPSI, i protocolli quantistici di TPSI esistenti (ad es. [MSD+24, LZY+26, WLS+26]) si affidano tipicamente a una Terza Parte (TP) per eseguire le misurazioni finali e interpretare i risultati. In questi schemi, la TP recupera l'esatta cardinalità dell'intersezione e poi la confronta con $\tau$. Questo approccio devia dal paradigma ideale di TPSI, poiché espone la statistica esatta della cardinalità alla TP anziché rivelare solo il predicato a un bit $\mathbb{1}[|\bigcap X_i| \ge \tau]$. Ciò crea un disallineamento funzionale e una concentrazione di autorità in cui la TP funge sia da fornitore di risorse quantistiche che da interprete semantico dei dati privati.

Metodologia
Gli autori propongono un protocollo di Multi-Party Quantum TPSI (MP-QTPSI) che scinde il ruolo di misurazione dal ruolo di interpretazione semantica. Il protocollo coinvolge $n$ partecipanti ($P_1, \dots, P_n$) e una TP semi-onesta.

1. Fase Quantistica (Costruzione delle Etichette Nascoste):

   • Setup: I partecipanti stabiliscono una chiave master tramite un Quantum Conference Key Agreement (QCKA) privo di TP per derivare una chiave di occultamento della posizione $k$, un vettore di flip delle etichette nascoste $\mathbf{b}$ e quote di rotazione $\Delta_i$. La TP e ogni partecipante stabiliscono chiavi pairwise per le maschere di rotazione $T_i$.
   • Codifica: I partecipanti aumentano i propri insiemi con insiemi ancora positivi (anchor sets) e applicano una mappa di occultamento della posizione $x \mapsto kx \mod M$. Codificano i propri insiemi in vettori di indicatore $Y_i$.
   • Interazione: La TP prepara sequenze di singoli fotoni e applica una rotazione di blinding iniziale. Le sequenze attraversano i partecipanti sequenzialmente. Ogni partecipante $P_i$ applica una rotazione basata sui propri dati ($0$o$\pi/n$), sulla propria maschera pairwise $T_i$ e sulla propria quota di rotazione $\Delta_i$.
   • Misurazione: La TP rimuove le proprie maschere note e misura le sequenze. A causa delle rotazioni aggregate correlate, gli esiti della misurazione sono deterministici solo per le posizioni in cui tutti i partecipanti possiedono l'elemento (intersezione) o nessuno lo possiede (non-intersezione), ma il significato semantico di questi esiti è oscurato dal vettore di flip nascosto $\mathbf{b}$. La TP ottiene vettori di indicatore di etichette nascoste $z_S$ (stesso) e $z_O$ (opposto), ma non può interpretarli senza le informazioni lato partecipante.

2. Fase Classica (Test di Cardinalità):

   • Test di Coerenza Mascherato: Il protocollo converte le misurazioni nascoste in un test di coerenza delle etichette mascherate. I partecipanti possiedono etichette di riferimento $\rho$ e maschere di selezione per i domini reali e di ancoraggio (anchor).
   • Oblivious Linear Evaluation (OLE): La TP e i partecipanti utilizzano l'Oblivious Inner Product (OIP) basato su OLE per calcolare le quote additive dei conteggi di coerenza (inconsistenze $d_{\mathcal{R}}$ e $d_{\mathcal{A}}$) senza rivelare i vettori l'uno all'altro.
   • Decisione della Soglia: Un circuito garbled leggero valuta il predicato $\text{flag} = 1 \iff (d_{\mathcal{A}} = 0) \land (d_{\mathcal{R}} \le |\mathcal{R}| - \tau)$. Questo restituisce solo il risultato booleano, garantendo che l'esatta cardinalità non venga mai rivelata alla TP.
   • Ricostruzione: Se $\text{flag}=1$, la TP trasmette i vettori nascosti e i partecipanti utilizzano le loro etichette di riferimento e la chiave inversa $k^{-1}$ per ricostruire l'intersezione.

Contributi Chiave

• Test di Cardinalità Esplicito: Il protocollo è il primo TPSI quantistico che aderisce rigorosamente al paradigma del test di cardinalità, restituendo solo il predicato di soglia $\mathbb{1}[|\bigcap X_i| \ge \tau]$ senza rivelare la cardinalità esatta alla TP.
• Design Quantistico a Etichetta Nascosta: Utilizzando le rotazioni aggregate correlate dei partecipanti e un vettore di flip nascosto, il protocollo assicura che gli esiti di misurazione della TP siano semanticamente oscurati. La TP agisce esclusivamente come parte di misurazione, incapace di mappare gli esiti su specifici elementi dell'insieme o sulla cardinalità.
• Sicurezza contro Collusione e TP: Il protocollo dimostra la sicurezza contro intercettatori esterni (tramite fotoni decoy) la TP semi-onesta (che non apprende né gli insiemi né la cardinalità) e i partecipanti collusi (che non possono inferire gli insiemi altrui a causa delle maschere pairwise e delle rotazioni di blinding sconosciute).
• Rilevamento di Manomissioni: L'inclusione di insiemi ancora (anchor sets) nascosti consente un controllo di coerenza ($d_{\mathcal{A}}=0$) che può rilevare se la TP modifica i vettori di misurazione riportati.

Risultati

• Correttezza: Le prove teoriche dimostrano che il protocollo codifica correttamente il pattern di intersezione e che il sottoprocesso classico valuta correttamente la condizione di soglia.
• Simulazione: Gli autori hanno implementato la fase quantistica sulla piattaforma IBM Qiskit utilizzando un modello semplificato (toy model) ($n=3$, dimensione del dominio 8). La simulazione ha incluso errori di depolarizzazione, di smorzamento di fase (phase-damping) e di lettura (readout). I risultati della simulazione rumorosa (Tabella 3) hanno corrisposto strettamente alle probabilità teoriche, superando con successo il controllo dell'ancora e il test di soglia per ricostruire l'intersezione corretta $\{1, 3\}$.
• Complessità: Il costo di comunicazione quantistica è $\mathcal{O}(n(\ell M + \delta))$, e il costo computazionale è simile, dove $M$ è la dimensione aumentata del dominio, $\ell$ è il numero di ripetizioni e $\delta$ è il numero di decoy.

Significatività e Rivendicazioni
Il documento afferma che la sua principale significatività risiede nella risoluzione del "gap di funzionalità" nei protocolli quantistici di TPSI esistenti. Separando il ruolo di misurazione quantistica dal ruolo di interpretazione semantica, il protocollo proposto si allinea alla definizione ideale di TPSI classico, dove la decisione della soglia è un predicato diretto piuttosto che un passaggio di post-elaborazione su statistiche rivelate. Gli autori sottolineano che la loro costruzione si basa solo su rotazioni di singoli fotoni e su un passaggio di post-elaborazione classica leggero (OLE e circuiti garbled), evitando la complessità della Quantum Homomorphic Encryption (QHE) utilizzata in altri lavori recenti. Asseriscono che questo design offre un approccio più preservativo della privacy per contesti multi-party in cui la TP non dovrebbe apprendere la dimensione dell'intersezione. Il documento conclude notando che il framework è flessibile e potrebbe potenzialmente essere esteso a soglie basate su pesi o rapporti, sebbene attualmente operi sotto un modello di TP semi-onesta.