💻 computer science

Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold

Questo articolo presenta nuovi protocolli di Fuzzy Private Set Intersection (FPSI) per distanze $L_p$ generali che raggiungono una dipendenza logaritmica ottimale rispetto alla soglia di distanza $\delta$ utilizzando solo l'oblivious transfer e primitive a chiave simmetrica, eliminando così la necessità della costosa crittografia omomorfica e superando significativamente le soluzioni allo stato dell'arte in termini di tempo di esecuzione e comunicazione.

Autori originali: Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

Pubblicato 2026-06-16

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

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

Immaginate due persone, Alice e Bob, che vogliono scoprire se hanno degli oggetti "simili" nelle rispettive collezioni senza mostrarsi l'intero elenco l'uno all'altro.

Il Problema: In un gioco standard, farebbero il match solo su elementi che sono esattamente uguali (ad esempio, entrambi hanno una "Mela Rossa").
Il Colpo di Scena (Fuzzy PSI): In questo nuovo gioco, vogliono far combaciare elementi che sono abbastanza vicini. Per esempio, se Alice ha una "Mela Rossa" e Bob ha una "Mela Rossa Leggermente Ammaccata", questi devono essere conteggiati come un match. La regola è: "Se la differenza tra i nostri elementi è minore di una specifica distanza (chiamiamola Soglia, o Threshold), allora c'è un match".

La sfida è farlo in modo sicuro. Alice non deve conoscere l'intero elenco di Bob, e Bob non deve conoscere l'intero elenco di Alice. Vogliono sapere solo quali elementi sono abbastanza vicini.

Il Vecchio Modo: La Ricerca Lenta e Costosa

I metodi precedenti per questo gioco di "Matching Fuzzy" avevano due grandi problemi:

La Trappola "Lineare": Se la soglia di "vicinanza" era ampia (diciamo 100 unità), i computer dovevano controllare 100 diverse possibilità per ogni singolo elemento. Era come cercare un ago in un pagliaio controllando ogni singola paglia una alla volta. Più grande era la soglia, più lento diventava il processo.
Il Problema dei "Macchinari Pesanti": Per far sì che questo funzionasse in modo sicuro, i vecchi metodi utilizzavano strumenti crittografici molto pesanti e lenti (come la Crittografia Omomorfica Additiva). Pensate a questo come al tentativo di inviare un messaggio segreto usando un enorme camion che consuma tantissimo carburante, quando una bicicletta sarebbe bastata.

Il Nuovo Breakthrough: La Scorciatoia del "Prefisso"

Questo articolo introduce un nuovo modo di giocare che è veloce, leggero e intelligente.

1. L'Analogia del "Codice di Aviazione" (Prefissi)

Inveve di controllare ogni singolo numero in un intervallo (come controllare se un numero è 10, 11, 12... fino a 100), gli autori utilizzano un trucco chiamato Prefissi.

Immaginate di cercare una casa in una città.

Vecchio Modo: Bussate a ogni porta nel quartiere per vedere se il residente è un vostro amico.
Nuovo Modo: Guardate il Codice di Aviazione (o CAP). Se il vostro amico vive nel prefisso "10001", dovete controllare solo le case con quel prefisso. Non c'è bisogno di controllare tutta la città.

Gli autori si sono resi conto che qualsiasi "intervallo" di numeri (la soglia) può essere scomposto in pochi "Codici di Aviazione" (prefissi).

La Magia: Il tempo necessario per controllare questi prefissi non cresce con la dimensione della soglia; cresce logaritmicamente.
- Se la soglia raddoppia, il lavoro aumenta solo di un pochino.
- Se la soglia diventa 100 volte più grande, il lavoro solo raddoppia.
- Analogia: È come trovare un libro in una biblioteca. Controllare ogni singolo libro richiede una eternità. Controllare l'etichetta sullo scaffale (il prefisso) richiede pochi secondi, indipendentemente da quanti libri ci siano sullo scaffale.

2. Strumenti "Leggeri" (Primitive Simmetriche)

Gli autori hanno sostituito i "camion" pesanti (crittografia costosa) con "biciclette" (primitive a chiave simmetrica e Oblivious Transfer).

Oblivious Transfer (OT): Immaginate un cameriere che può darvi uno tra due articoli segreti del menu senza che voi sappiate quale avete scelto, e senza che il cameriere sappia quale avete richiesto. Gli autori usano questo per scambiare informazioni in modo sicuro senza rivelare l'intero elenco.
Il Risultato: Il loro sistema è costruito interamente partendo da questi strumenti leggeri e veloci.

I Due Scenari: Stanze Piccole vs Grandi Sale

L'articolo offre due diverse strategie a seconda di quanto è "affollato" il dato (dimensionalità):

Scenario A: Basse Dimensioni (L'Assunzione dell' "Appartamento")

L'Ambiente: Immaginate una stanza piccola dove le persone sono distanti tra loro (almeno 2 volte la distanza della soglia).
La Strategia: Utilizzano l'Hashing Spaziale. Immaginate di dividere la stanza in una griglia di piastrelle. Se due persone sono vicine, devono trovarsi nella stessa piastrella o in piastrelle vicine. Il protocollo controlla solo quelle specifiche piastrelle.
L'Innovazione: Hanno combinato questo sistema a griglia con il loro nuovo scorciatoia del "Prefisso" e uno speciale strumento di "Controllo di Uguaglianza" (chiamato ECSS). Questo permette loro di trovare i match istantaneamente senza dover controllare ogni singola coppia.

Scenario B: Alte Dimensioni (L'Assunzione della "Separazione")

L L'Ambiente: Immaginate un enorme magazzino multidimensionale. In alte dimensioni, dividere lo spazio in una griglia crea troppe piastrelle vuote (la "maledizione della dimensionalità").
La Strategia: Utilizzano la Generazione di ID Distribuita. Invece di una griglia, assegnano a ogni elemento una "carta d'identità" unica basata sulla sua posizione.
L'Innovazione: Hanno creato un nuovo modo per generare questi ID in modo sicuro utilizzando il loro trucco del "Prefisso". Anche in un magazzino gigante, possono generare questi ID in modo che, se due elementi sono vicini, i loro ID corrispondano, senza rivelare le posizioni reali degli elementi.

Il "Segreto": Somma Condizionale di Uguaglianza

Il cuore della loro invenzione è un nuovo strumento matematico chiamato Equality Conditional Sum (ECSS).

Come funziona: Immaginate che Alice e Bob abbiano entrambi un elenco di numeri. Vogliono sommare i numeri solo se viene soddisfatta una specifica condizione (ad esempio, "Somma i numeri solo se i prefissi corrispondono").
La Magia: Possono eseguire questa addizione in modo sicuro senza che nessuna delle due parti riveli i propri numeri. Se i prefissi non corrispondono, il risultato è solo rumore casuale. Se corrispondono, il risultato è la somma corretta. Questo permette loro di verificare la vicinanza degli elementi senza mai vedere i valori effettivi.

I Risultati: Un Incremento di Velocità Massiccio

Gli autori hanno costruito una versione funzionante del loro sistema e l'hanno testata contro i migliori metodi esistenti.

Velocità: Il loro sistema è fino a 43,7 volte più veloce rispetto al precedente miglior metodo.
Utilizzo dei Dati: Utilizza fino a 31,3 volte meno dati da trasmettere sulla rete.
Scalabilità: Mentre altri sistemi fallivano (andavano in esaurimento della memoria) quando i set di dati diventavano molto grandi, il loro sistema continuava a funzionare regolarmente.

Riassunto

In breve, questo articolo risolve il problema del "Fuzzy Matching" attraverso:

La sostituzione della crittografia lenta e pesante con strumenti veloci e leggeri.
L'uso dei "Prefissi" (come i Codici di Aviazione) per trasformare una ricerca lineare lenta in una ricerca logaritmica veloce.
La creazione di nuovi strumenti di "Somma Segreta" che permettono a due parti di controllare la vicinanza senza rivelare i propri segreti.

Il risultato è un sistema in grado di trovare elementi "simili" in enormi dataset privati quasi istantaneamente, rendendo il matching di dati preservando la privacy praticabile per la prima volta su larga scala.

Sintesi Tecnica: FPSI Fuzzy da Primitivi Simmetrici con Dipendenza Logaritmica Esatta dalla Soglia di Distanza

Problematica
L'Intersezione di Insiemi Privata Fuzzy (Fuzzy Private Set Intersection - FPSI) consente a un mittente con un insieme di vettori $d$ -dimensionali $Q$ e a un ricevitore con un insieme $W$ di identificare gli elementi $q \in Q$ tali che esista un $w \in W$ con $\text{dist}(q, w) \le \delta$ , senza rivelare ulteriori informazioni. Sebbene il PSI standard abbia raggiunto un'elevata efficienza, gli esistenti protocolli FPSI affrontano significativi colli di bottiglia teorici e pratici. I lavori precedenti mostrano tipicamente una scalabilità lineare rispetto alla soglia di distanza $\delta$ (ovvero $O(\delta)$ ), o raggiungono una dipendenza polilogaritmica solo per le distanze $L_\infty$ . I protocolli che supportano distanze di Minkowski generali ( $L_p$ per $p \in [1, \infty]$ con dipendenza logaritmica in $\delta$ ) si sono basati o su costosa Crittografia Omomorfica Additiva (AHE) o hanno sofferto di difetti di sicurezza e termini di complessità esponenziale nella dimensione $d$ . L'obiettivo è ottenere una dipendenza logaritmica esatta in $\delta$ per distanze $L_p$ generali utilizzando esclusivamente primitivi a chiave simmetrica.

Metodologia e Tecniche Core
Gli autori propongono nuovi protocolli FPSI costruiti interamente tramite Oblivious Transfer (OT) e primitivi a chiave simmetrica, evitando operazioni a chiave pubblica come l'AHE. La costruzione si basa su due assunzioni primarie: l'assunzione apart (adatta per contesti a bassa dimensionalità) e l'assunzione separate (adatta per contesti ad alta dimensionalità).

Rappresentazione dei Prefissi e Test degli Intervalli:
L'innovazione principale sostituisce l'enumerazione di tutti gli interi in un intervallo $[q_k - \delta, q_k + \delta]$ (che costa $O(\delta)$ ) con una rappresentazione dei prefissi utilizzando $O(\log \delta)$ prefissi. Ciò riduce il costo del test dell'intervallo a $O(\log \delta)$ per dimensione.
Somma Condizionale di Uguaglianza / Parte del Prodotto Interno Condizionale di Uguaglianza (ECSS/ECIPS):
Per gestire l'interazione richiesta dal matching dei prefissi senza rivelare l'input del mittente o incorrere in un overhead esponenziale, gli autori introducono due nuove primitive crittografiche:
- Equality Conditional Sum Share (ECSS): Utilizzata per la distanza $L_\infty$ . Permette alle parti di calcolare una somma di valori condizionata a un match di uguaglianza tra i vettori di input, restituendo le parti segrete (secret shares) del risultato.
- Equality Conditional Inner-Product Share (ECIPS): Utilizzata per le distanze $L_p$ generali. Calcola un prodotto interno condizionato all'uguaglianza, consentendo il calcolo di $|w_k - q_k|^p$ tramite espansione binomiale senza rivelare i termini specifici.
  Entrambe le primitive sono implementate efficientemente utilizzando OT, Oblivious Programmable PRF (OPPRF) e protocolli Permute+Share (PS).
Gestione di Elementi Multipli:
- Bassa Dimensionalità ( $L_\infty$ e $L_p$ ): I protocolli utilizzano lo spatial hashing (celle di griglia) combinato con il Cuckoo hashing per ridurre il numero di confronti a coppie. Gli autori introducono ottimizzazioni utilizzando l'OPRF condivisa (sOPRF) per eliminare la necessità di valori dummy nelle celle vuote, nascondendo così le posizioni di hashing del mittente e rimuovendo la necessità di passi di permutazione globale in determinate configurazioni.
- Alta Dimensionalità ( $L_\infty$ e $L_p$ ): Per evitare il costo esponenziale $O(2^d)$ dello spatial hashing, gli autori impiegano un protocollo di Generazione di ID Distribuita (dIDG). Questo protocollo genera ID unici per gli elementi tali che elementi vicini condividano lo stesso ID. Gli autori identificano falle di sicurezza in precedenti costruzioni dIDG (specificamente in [DZL25]) relative alla fuga di collisioni e propongono una dIDG sicura, basata su chiavi simmetriche, utilizzando sOPRF ed ECSS.

Contributi Chiave

Nuove Primitive: L'introduzione di ECSS e ECIPS, che consentono un matching fuzzy efficiente con dipendenza logaritmica esatta in $\delta$ utilizzando solo primitive simmetriche.
Complessità Ottimale: I primi protocolli FPSI per distanze $L_p$ generali $L_p \in [1, \infty]$ che raggiungono una complessità strettamente logaritmica $O(d \log \delta)$ nella soglia $\delta$ . Questo è teoricamente ottimale, poiché distinguere i valori in un intervallo di lunghezza $O(\delta)$ richiede $\Omega(\log \delta)$ bit di informazione.
Sicurezza ed Efficienza: I protocolli eliminano la dipendenza dall'AHE, sostituendola con operazioni OT e a chiave simmetrica. Gli autori identificano inoltre e correggono vulnerabilità di sicurezza in recenti protocolli basati su prefissi (es. [DZL25]) che soffrivano di riutilizzo delle maschere e fuga di collisioni.
Costruzioni Scalabili: Costruzioni separate per contesti a bassa dimensionalità (usando lo spatial hashing) e ad alta dimensionalità (usando la dIDG), entrambe raggiungendo una complessità asintotica ottimale.

Risultati Sperimentali
Gli autori hanno implementato i loro protocolli e li hanno confrontati con i lavori allo stato dell'arte ([GQL+24], [DZL25], [BGMP25]).

Performance: I nuovi protocolli superano significativamente l'arte precedente. In contesti a bassa dimensionalità, raggiungono un tempo di esecuzione fino a 43,7× più veloce e un overhead di comunicazione 31,3× inferiore.
Scalabilità: Mentre i lavori precedenti come [GQL+24] e [DZL25] incontravano overflow di memoria con set di dimensioni $2^{16}$ in contesti ad alta dimensionalità, i protocolli proposti sono stati eseguiti con successo sotto le stesse configurazioni.
Dipendenza dalla Soglia: Gli esperimenti confermano che i costi di runtime e di comunicazione scalano logaritmicamente con $\delta$ , contrastando con la scalabilità lineare osservata nei precedenti protocolli a dipendenza lineare.

Significatività
Il documento rivendica un breakthrough teorico nella scalabilità ottimale della soglia per l'FPSI, dimostrando che una dipendenza logaritmica esatta in $\delta$ è realizzabile per distanze $L_p$ generali senza ricorrere alla costosa crittografia a chiave pubblica. In termini pratici, ciò rende fattibile l'applicazione di FPSI scalabili in domini che richiedono il matching fuzzy, come il matching di sequenze genomiche, il recupero di immagini simili e il rilevamento di credenziali compromesse, eliminando i colli di bottiglia di efficienza associati alla soglia di distanza e alla dimensionalità.