💻 computer science

Efficient Fuzzy PSI under One-Sided Assumptions

Questo articolo introduce i primi protocolli di intersezione di insiemi privati fuzzy concretamente efficienti per distanze $L_p$ generali sotto assunzioni unidirezionali, sfruttando primitive a chiave simmetrica leggere e tecniche di prefix trie per raggiungere una complessità $O(\log \delta)$ e superare significativamente i precedenti lavori allo stato dell'arte sia in termini di velocità di calcolo che di overhead di comunicazione.

Autori originali: Xinpeng Yang, Meng Hao, Yanxue Jia, Chenkai Weng, Yonggang Wen, Tianwei Zhang

Pubblicato 2026-08-19

📖 7 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Xinpeng Yang, Meng Hao, Yanxue Jia, Chenkai Weng, Yonggang Wen, Tianwei Zhang

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

Nell'era digitale, due organizzazioni spesso hanno bisogno di trovare un terreno comune senza rivelare tutti i propri segreti l'una all'altra. Immaginate un ospedale che detiene un elenco di pazienti con una specifica condizione e un istituto di ricerca che detiene un elenco di volontari. Vogliono sapere quali volontari sono anche pazienti, ma nessuna delle due parti vuole consegnare il proprio elenco completo, poiché ciò esporrebbe i dati privati di tutti gli altri presenti nell'elenco. I protocolli informatici standard possono risolvere questo identico problema di corrispondenza in modo efficiente, ma falliscono quando i dati sono leggermente "sporchi". Nel mondo reale, i nomi sono scritti male, le località sono leggermente imprecise e le scansioni biometriche variano da un giorno all'altro. Se il record dell'ospedale riporta "John Smith" e il record del volontario riporta "Jon Smyth", un sistema standard non vede alcuna corrispondenza, anche se si tratta della stessa persona. È qui che entra in gioco il "fuzzy matching" (corrispondenza approssimativa), un metodo progettato per trovare queste connessioni approssimative. Tuttavia, eseguire questo processo in modo sicuro è incredibilmente difficile. Se il sistema tenta di confrontare ogni possibile variazione di ogni nome contro ogni altra variazione, la quantità di dati scambiati diventa così massiccia che il processo si blocca, oppure richiede una strumentazione matematica così pesante da diventare impraticabile per l'uso quotidiano.

Un team di ricercatori ha ora sviluppato un nuovo modo per eseguire questo fuzzy matching che sia al contempo veloce e leggero. Il loro lavoro si concentra su uno scenario in cui solo una delle due parti deve seguire regole rigide su come i propri dati siano organizzati, mentre l'altra parte può avere dati in qualsiasi ordine caotico. I tentativi precedenti di risolvere questo problema in condizioni così rilassate si basavano su strumenti crittografici pesanti e lenti o richiedevano che entrambe le parti avessero dati perfettamente organizzati, il che è raramente il caso nella realtà. Il nuovo metodo, creato da Xinpeng Yang e dai suoi colleghi provenienti da istituzioni di Singapore e degli Stati Uniti, raggiunge lo stesso obiettivo utilizzando solo componenti fondamentali semplici e veloci. Sono riusciti a ridurre drasticamente il tempo e i dati richiesti per questi confronti, rendendo il fuzzy matching sicuro fattibile per la prima volta in molti contesti del mondo reale.

Il cuore del traguardo risiede nel modo in cui i ricercatori gestiscono la "distanza" tra i punti dati. In questo contesto, la distanza è una misura di quanto due pezzi di informazione siano diversi, come ad esempio quanti caratteri differiscono tra due nomi o quanto siano distanti due coordinate GPS. L'obiettivo è trovare coppie in cui questa distanza sia inferiore a una specifica soglia. I ricercatori si sono resi conto che i metodi precedenti cercavano di controllare ogni possibile variazione di un punto dato, il che creava uno spazio di ricerca che cresceva in modo esplosivo all'aumentare della differenza consentita. Per risolvere il problema, hanno introdotto una tecnica che agisce come un filtro intelligente. Invece di controllare ogni singola possibilità, il sistema organizza i dati in una struttura ad albero che permette di saltare istantaneamente enormi blocchi di informazioni irrilevanti. Questo cambiamento ha ridotto lo sforzo computazionale da un livello che cresceva esponenzialmente con la dimensione della ricerca a un livello che cresce solo logaritmicamente. In termini pratici, questo significa che anche se la differenza consentita tra i punti dati viene raddoppiata o triplicata, il tempo necessario per eseguire il controllo aumenta di pochissimo.

Il team ha testato i nuovi protocolli contro i migliori metodi esistenti attualmente disponibili. I risultati sono stati drammatici. Quando confrontato con un recente protocollo del 2024, il loro nuovo sistema è stato fino a 239 volte più veloce e ha utilizzato fino a 20 volte meno larghezza di banda per la comunicazione. Contro un metodo del 2025, l'accelerazione è stata di 518 volte, con una riduzione del trasferimento dati di 63 volte. In un confronto specifico con un'altra costruzione del 2025, il nuovo sistema è stato quasi 5.000 volte più veloce e ha richiesto 282 volte meno comunicazione. Questi numeri non erano solo teorici; i ricercatori hanno implementato il sistema completo ed eseguito estesi esperimenti attraverso una vasta gamma di dimensioni e impostazioni dei dati. Hanno confermato che il loro approccio funziona sia che il mittente che il destinatario siano il lato con i dati organizzati, e supporta vari tipi di misurazioni di distanza, non solo quelle semplici.

Una chiave innovazione nel loro lavoro è stata la capacità di gestire le assunzioni "unilaterali". In molti sistemi sicuri precedenti, entrambe le parti dovevano concordare regole rigide, come garantire che i propri punti dati fossero distanziati quanto basta per evitare confusione. Questo è spesso impossibile nella vita reale, dove i dati arrivano in cluster o schemi casuali. Il nuovo metodo richiede solo che un lato abbia un dataset parzialmente organizzato, mentre l'altro lato può avere dati completamente arbitrari e disordinati. Questa flessibilità rende la tecnologia applicabile a scenari come il tracciamento dei contatti o i servizi basati sulla posizione, dove un'entità potrebbe avere un database strutturato di posizioni note, mentre l'altra ha un flusso di input utente non strutturati. Basandosi esclusivamente su tecniche a chiave simmetrica leggere — essenzialmente strumenti di crittografia standard che sono veloci ed efficienti — i ricercatori hanno evitato le pesanti e lente operazioni matematiche che avevano precedentemente rallentato sforzi simili.

I ricercatori hanno anche esplorato come rendere il sistema ancora più efficiente quando i dati sono sparsi, ovvero quando i punti sono distribuiti piuttosto che raggruppati. In questi casi, hanno scoperto che scambiare i ruoli delle due parti nel processo di abbinamento poteva bilanciare ulteriormente il carico di lavoro e migliorare le prestazioni. Questa adattabilità suggerisce che il sistema può essere tarato per diversi tipi di applicazioni senza la necessità di una riprogettazione completa. Il lavoro dimostra che è possibile costruire sistemi sicuri e che preservano la privacy che non siano solo teoricamente solidi, ma anche praticamente abbastanza veloci per l'implementazione nel mondo reale.

Le implicazioni di questo lavoro vanno oltre la semplice velocità. Rendendo il fuzzy matching efficiente, i ricercatori hanno aperto la porta ad applicazioni più sofisticate che preservano la privacy. Organizzazioni che da tempo evitavano la condivisione dei dati per timore di fughe di privacy o perché il processo di abbinamento era troppo lento, possono ora considerare la collaborazione sicura. Che si tratti di abbinare i record dei pazienti per la ricerca medica, verificare l'identità degli utenti senza esporre i template biometrici o trovare articoli simili in grandi cataloghi senza rivelare il contenuto del catalogo, la barriera all'ingresso è stata significativamente abbassata. Lo studio dimostra che, con l'approccio algoritmico corretto, il compromesso tra privacy e prestazioni può essere risolto, permettendo ai dati di fluire in modo sicuro anche quando sono imperfetti o rumorosi.

In definitiva, il documento presenta una soluzione concreta a un problema che persiste da anni: come trovare abbinamenti approssimativi in dati privati senza sacrificare la velocità o richiedere condizioni irrealistiche. I ricercatori non si sono limitati a proporre una nuova idea; l'hanno costruita, l'hanno testata e hanno dimostrato che supera tutto ciò che è venuto prima per ordini di grandezza. Il loro lavoro è una testimonianza della potenza del raffinamento della logica sottostante di un problema, piuttosto che del semplice tentativo di applicare più potenza di calcolo. Per l'osservatore curioso, il risultato è un sistema che appare meno come una macchina pesante e goffa e più come uno strumento preciso ed efficiente, pronto per essere utilizzato nel mondo disordinato e imperfetto dei dati reali.

Riepilogo Tecnico: Fuzzy PSI Efficiente sotto Assunzioni Unilaterali

Definizione del Problema

Il Fuzzy Private Set Intersection (PSI) consente a due parti, un mittente (sender) e un ricevitore (receiver), di identificare gli elementi nei rispettivi insiemi di input che corrispondono approssimativamente. Nello specifico, dato una soglia di distanza $\delta$ e una metrica $dist(\cdot, \cdot)$ , il ricevitore apprende tutti gli elementi del mittente $\mathbf{q}$ per i quali esiste un elemento del ricevitore $\mathbf{w}$ tale che $dist(\mathbf{q}, \mathbf{w}) \le \delta$ .

Mentre il PSI standard ha visto progressi significativi, il fuzzy PSI affronta un compromesso tra efficienza e la forza delle assunzioni sottostanti. Le costruzioni esistenti per distanze $L_p$ generali ( $p \in [1, \infty]$ tipicamente rientrano in due categorie:

Assunzioni bilaterali (two-sided): Protocolli che richiedono che gli input di entrambe le parti soddisfino forti separazioni geometriche (ad es. i punti sono separati tra loro da $2\delta$ o $4\delta$ ). Questi sono efficienti ma spesso irrealistici per dati reali rumorosi.
Assunzioni unilaterali (one-sided): Protocolli in cui solo una delle parti deve soddisfare vincoli di separazione, permettendo all'altra parte di detenere input arbitrari. Tuttavia, le soluzioni unilaterali esistenti si affidano o a primitive crittografiche pesanti (ad es. Crittografia Omomorfica Additiva) o incorrono in un overhead asintotico sostanziale rispetto alla soglia $\delta$ (ad es. $O(\delta)$ o $O((\log \delta)^d)$ ).

La sfida centrale affrontata è la costruzione di protocolli di fuzzy PSI concretamente efficienti per distanze $L_p$ generali sotto deboli assunzioni unilaterali, facendo affidamento esclusivamente su leggere primitive a chiave simmetrica.

Metodologia

Gli autori propongono un framework basato su Funzioni Pseudo-casuali Programmabili Obligue Secret-Shared (so-OPPRF) e Hashing Spaziale, potenziati da tecniche di Prefix Trie.

1. Primitive di Fuzzy Matching Multi-punto

Per gestire input arbitrari da una parte senza perdita di privacy, il documento introduce due protocolli di fuzzy matching multi-punto privi di assunzioni:

Matching 1-a- $n$ (Il ricevitore detiene punti arbitrari): Il mittente programma una so-OPPRF con intervalli attorno al suo singolo punto. Per evitare che il ricevitore inferisca la distribuzione dell'input del mittente tramite collisioni nelle share aggregate (un problema di leakage in lavori precedenti), gli autori introducono la Randomizzazione Condizionale all'Uguaglianza (EqRand). Questa primitiva re-randomizza le share segrete per gli input non corrispondenti preservando al contempo la somma corretta per gli input corrispondenti, garantendo la privacy anche quando più punti del ricevitore mappano allo stesso intervallo programmato.
Matching $m$ -a-1 (Il mittente detiene punti arbitrari): I ruoli sono invertiti. Il ricevitore programma la so-OPPRF con intervalli attorno al suo singolo punto. Il mittente valuta la funzione sui suoi molteplici punti. Poiché il ricevitore non ricostruisce i valori aggregati dal lato del mittente, il problema del leakage viene evitato naturalmente e non è richiesta la EqRand.

2. Fuzzy PSI sotto Assunzioni Unilaterali

Costruendo sulle primitive sopra descritte, gli autori costruiscono protocolli fuzzy PSI $m$ -a- $n$ completi sotto due specifiche assunzioni unilaterali:

Assunzione di Cellula Unica (Unique Cell Assumption): Ogni cella spaziale (di lato $2\delta$ ) contiene al massimo un punto della parte vincolata.
Assunzione di Blocco Unico (Unique Block Assumption - più sparsa): Ogni cella spaziale interseca al massimo una ball $L_\infty$ della parte vincolata.

Il protocollo utilizza l'hashing spaziale per partizionare lo spazio. La parte vincolata programma la so-OPPRF con chiavi derivate dai propri punti e dagli identificatori delle celle, garantendo l'assenza di collisioni. L'altra parte valuta la funzione sui propri punti e sulle celle vicine. L'uso di so-OPPRF assicura che gli output siano secret-shared, impedendo a ciascuna parte di apprendere i dati grezzi dell'altra.

3. Ottimizzazione Prefix Trie

Per affrontare la complessità lineare o superlineare scalante con $\delta$ presente in lavori precedenti, gli autori incorporano tecniche di Prefix Trie.

Meccanismo: Invece di enumerare tutti i punti in un intervallo $[w - \delta, w + \delta]$ (che richiede $O(\delta)$ ), l'intervallo viene codificato in $O(\log \delta)$ nodi di prefisso utilizzando l'algoritmo PxTrie.
Filtraggio Dimensione per Dimensione: I lavori precedenti richiedevano la valutazione di tutte le combinazioni di prefissi attraverso $d$ dimensioni, portando a una complessità di $O((\log \delta)^d)$ . Gli autori introducono una primitiva di Selezione Condizionale (ConSel) che filtra i prefissi dimensione per dimensione. Poiché al massimo un prefisso per dimensione può corrispondere al target, lo spazio di ricerca viene ridotto da $O((\log \delta)^d)$ a $O(d \cdot \log \delta)$ .
Risultato: Questo raggiunge una complessità di $O(\log \delta)$ nella soglia $\delta$ per distanze $L_p$ generali, un miglioramento significativo rispetto ai precedenti limiti $O((\log \delta)^d)$ o $O(\delta)$ .

4. Gestione di Distanze $L_p$ Generali

Per le distanze $L_p$ ( $p > 1$ ), il protocollo codifica la $p$ -esima potenza del contributo della distanza per dimensione ( $|t|^p$ ) nei valori della so-OPPRF. Le parti eseguono quindi calcoli multi-party sicuri (addizione e moltiplicazione) per aggregare queste share e verificare se la distanza totale è entro la soglia $\delta^p$ .

Contributi Chiave

Primo Fuzzy PSI Unilaterale Efficiente per $L_p$ Generali: Il documento presenta i primi protocolli concretamente efficienti per distanze $L_p \in [1, \infty]$ generali sotto assunzioni unilaterali, facendo affidamento esclusivamente su primitive a chiave simmetrica leggere (so-OPPRF, OKVS, silent OT).
Complessità Logaritmica in $\delta$ : Integrando in modo non banale le tecniche di prefix trie con un meccanismo di filtraggio dimensione per dimensione, i protocolli raggiungono una complessità di $O(\log \delta)$ nella soglia di distanza, superando le complessità $O((\log \delta)^d)$ o $O(\delta)$ dei lavori allo stato dell'arte.
Supporto a Assunzioni Flessibili: Il framework supporta sia l'impostazione lato Mittente (Sender-sided) che quella lato Ricevitore (Receiver-sided), così come le assunzioni di Cellula Unica e Blocco Unico. L'assunzione di Blocco Unico permette ulteriori ottimizzazioni invertendo i ruoli di programmazione e valutazione per sfruttare il minor costo della programmazione rispetto alla valutazione della so-OPPRF.
Valutazione Estesa: Gli autori hanno implementato i protocolli e li hanno confrontati con i lavori allo stato dell'arte (van Baarsen & Pu [31], Dang et al. [10], Bui et al. [6], ecc.).

Risultati Sperimentali

La valutazione è stata condotta su un server con un processore AMD EPYC 9554. I risultati dimostrano miglioramenti significativi sia nella comunicazione che nel calcolo:

Contro van Baarsen e Pu (EUROCRYPT'24): Calcolo fino a 239 $\times$ più veloce e comunicazione fino a 20 $\times$ inferiore.
Contro Dang et al. (CCS'25): Accelerazione fino a 518 $\times$ e riduzione della comunicazione del 63 $\times$ .
Contro Bui et al. (ASIACRYPT'25): Calcolo fino a 4818 $\times$ più veloce e riduzione della comunicazione fino a 282 $\times$ .

Le varianti ottimizzate con prefisso (Ours-Px) mostrano prestazioni superiori in termini di comunicazione per grandi $\delta$ e alte dimensioni, mentre le varianti non ottimizzate (Ours) sono altamente competitive per soglie più piccole grazie al minor overhead computazionale.

Significato e Rivendicazioni

Il documento sostiene di aver risolto il persistente compromesso tra la forza delle assunzioni geometriche e l'efficienza dei protocolli di fuzzy PSI. Dimostrando che il fuzzy PSI per $L_p$ generali può essere ottenuto sotto deboli assunzioni unilaterali utilizzando solo leggere primitive a chiave simmetrica, questo lavoro rende il fuzzy PSI più applicabile a scenari reali dove i dati sono rumorosi e non è possibile garantire rigide assunzioni di separazione.

Gli autori sottolineano che i loro protocolli superano significativamente i lavori precedenti a parità di assunzioni, ottenendo miglioramenti di ordini di grandezza nell'efficienza. L'introduzione del meccanismo di filtraggio dimensione per dimensione tramite prefix trie è evidenziata come una chiave innovazione tecnica che rompe la dipendenza esponenziale dalla dimensionalità rispetto al parametro della soglia, rendendo i protocolli scalabili per dati ad alta dimensionalità e grandi soglie di matching.