Efficient Fuzzy Private Set Intersection from Secret-shared OPRF

1. Il Problema

Il Private Set Intersection (PSI) consente a due parti (un mittente e un ricevente) di calcolare l'intersezione dei loro insiemi senza rivelare informazioni aggiuntive oltre agli elementi comuni. Tuttavia, nelle applicazioni reali come l'autenticazione biometrica (impronte digitali, riconoscimento facciale) o il matching genomico, i dati possono subire piccole variazioni a causa di rumore ambientale o errori di estrazione delle caratteristiche. In questi scenari, il matching esatto è spesso impraticabile.

Il Fuzzy PSI (FPSI) risolve questo problema permettendo al ricevente di apprendere gli elementi $q$ dell'insieme del mittente per i quali esiste un elemento $w$ nell'insieme del ricevente tale che la distanza $dist(q, w) \le \delta$ (dove $\delta$ è una soglia di distanza).

Sfide attuali:

• Le soluzioni esistenti per metriche di distanza $L_p$ (con $p \in [1, \infty]$) si basano spesso su crittografia omomorfa additiva (AHE) costosa (es. ElGamal, Paillier), portando a un'efficienza pratica scarsa.
• Altre approcci hanno complessità esponenziale rispetto alla dimensionalità degli elementi ($d$), rendendoli inutilizzabili in spazi ad alta dimensionalità.
• Le soluzioni lineari più recenti (es. Gao et al., Dang et al.) dipendono ancora pesantemente da operazioni AHE, limitando le prestazioni concrete.

2. Metodologia

Gli autori propongono un protocollo FPSI efficiente che evita la crittografia a chiave pubblica costosa, basandosi principalmente su operazioni simmetriche (chiave segreta). L'approccio si articola in due fasi principali: mappatura "grezza" (coarse mapping) e filtraggio raffinato (refined filtering).

Componenti Chiave e Costruzioni:

1. so-OPPRF (Oblivious Programmable PRF con Output Condivisi):

   • È il blocco costruttivo fondamentale. A differenza di un OPPRF standard, l'output non viene rivelato interamente a una delle parti, ma viene diviso in share segreti tra mittente e ricevente.
   • Viene costruito combinando un OKVS (Oblivious Key-Value Store) con un so-OPRF (OPRF con output condivisi).
   • Permette di programmare il PRF su punti specifici senza rivelare i valori programmati o gli input di query.

2. Mappatura Fuzzy Modulare:

   • Mappatura Locale: Ogni parte mappa i propri elementi in ID locali. Per gestire la distanza $\delta$, gli intervalli attorno a ogni coordinata vengono mappati allo stesso valore casuale.
   • Mappatura Globale: Le parti calcolano un ID globale combinando le mappature locali usando un PRF. Per evitare perdite di informazioni (es. rivelare se due elementi sono vicini su una singola dimensione), viene introdotto un nuovo blocco: si-OPRF (OPRF con input condivisi). In questo schema, sia la chiave che l'input del PRF sono condivisi tra le parti, garantendo che gli ID globali siano corretti solo se gli elementi sono vicini in tutte le dimensioni.

3. Filtraggio Raffinato:

   • Dopo aver ottenuto gli ID, le parti verificano se gli elementi con lo stesso ID sono effettivamente entro la soglia $\delta$.
   • Utilizzano il so-OPPRF per generare share segreti di un valore (es. 0 per $L_\infty$ o la distanza calcolata per $L_p$).
   • Viene eseguito un test di uguaglianza privata (PEQT) o un test di intervallo per verificare se la somma degli share corrisponde al valore atteso. Se sì, l'elemento viene selezionato tramite Oblivious Transfer (OT).

4. Ottimizzazione con Prefissi:

   • Per soglie di distanza $\delta$ grandi, la complessità lineare in $\delta$ diventa proibitiva.
   • Gli autori integrano una tecnica di rappresentazione a prefissi (prefix representation). Invece di programmare l'intero intervallo $[q-\delta, q+\delta]$, si programmano solo $O(\log \delta)$ prefissi che coprono l'intervallo.
   • Questo riduce la complessità di comunicazione e calcolo da $O(\delta)$ a $O(\log \delta)$.

3. Contributi Chiave

1. Nuovo Blocco Costruttivo (so-OPPRF): Introduzione di un OPPRF con output condivisi, che permette valutazioni oblivious senza rivelare i risultati a nessuna delle parti singolarmente.
2. Protocollo FPSI Efficiente: Proposta di protocolli per metriche $L_p$ ($p \in [1, \infty]$) con complessità lineare rispetto alle dimensioni degli insiemi ($m, n$), alla dimensionalità ($d$) e alla soglia ($\delta$).
3. Ottimizzazione Logaritmica: Integrazione di tecniche a prefisso che riducono la dipendenza da $\delta$ a $O(\log \delta)$, rendendo il protocollo scalabile per soglie ampie.
4. Prestazioni Superiori: Sostituzione delle costose operazioni AHE con operazioni simmetriche leggere (OT, VOLE, PRF), ottenendo guadagni significativi in velocità e riduzione del traffico di rete.

4. Risultati Sperimentali

Gli autori hanno implementato i protocolli in C++ e confrontato le prestazioni con gli stati dell'arte (Gao et al., ASIACRYPT '24 e Dang et al., CCS '25).

• Tempo di Esecuzione: I protocolli proposti sono 12-145 volte più veloci rispetto a Gao et al. e 9-80 volte più veloci rispetto a Dang et al.
• Costo di Comunicazione: Riduzione dei costi di comunicazione di 3-8 volte rispetto a Gao et al. e 5-19 volte rispetto a Dang et al.
• Scalabilità: Le prestazioni migliorano ulteriormente su insiemi di grandi dimensioni ($m=n=2^{16}$) e in condizioni di rete con larghezza di banda limitata, grazie alla riduzione dell'overhead di comunicazione.
• Metriche: I risultati sono validi per distanze $L_\infty$, $L_1$ e $L_2$, con overhead minimo per le metriche $L_p$ rispetto a $L_\infty$.

5. Significato e Impatto

Questo lavoro rappresenta un passo significativo verso l'adozione pratica del Fuzzy PSI in scenari reali ad alta dimensionalità.

• Efficienza Pratica: Dimostra che è possibile ottenere sicurezza crittografica per il matching fuzzy senza ricorrere a primitive a chiave pubblica pesanti, rendendo il protocollo fattibile per applicazioni come la verifica biometrica distribuita o il matching di dati sanitari sensibili.
• Fondamenta Teoriche: L'introduzione di so-OPPRF e si-OPRF offre nuovi strumenti per la costruzione di protocolli MPC (Multi-Party Computation) efficienti, potenzialmente utili anche al di fuori del contesto FPSI.
• Scalabilità: La soluzione con ottimizzazione a prefissi risolve il collo di bottiglia delle grandi soglie di distanza, un limite critico delle soluzioni precedenti.

In sintesi, il paper fornisce una soluzione concretamente efficiente, scalabile e basata su primitive simmetriche per il calcolo dell'intersezione fuzzy privata, superando i limiti di complessità e costo delle tecniche attuali.