Efficient Fuzzy Private Set Intersection from Secret-shared OPRF

1. El Problema

El Intersección de Conjuntos Privados (PSI) permite a dos partes (un remitente y un receptor) calcular la intersección de sus conjuntos sin revelar información adicional. Sin embargo, el PSI estándar requiere coincidencias exactas, lo cual es impráctico en aplicaciones con entradas multidimensionales ruidosas, como la autenticación biométrica (huellas dactilares, reconocimiento facial) o datos genómicos, donde pequeñas variaciones impiden una coincidencia exacta.

El PSI Difuso (FPSI) aborda esto permitiendo al receptor aprender los elementos del remitente que están dentro de una distancia $\delta$ de algún elemento en su propio conjunto, bajo una métrica de distancia $L_p$ (donde $p \in [1, \infty]$).

Limitaciones de los trabajos anteriores:

• Las soluciones existentes para métricas $L_p$ generales a menudo dependen de cifrado homomórfico aditivo (AHE) costoso (como ElGamal o Paillier), lo que genera una ineficiencia práctica significativa.
• Otras propuestas tienen complejidad exponencial en la dimensión de los elementos o dependen de supuestos restrictivos que limitan su escalabilidad.
• Aunque existen protocolos de complejidad lineal recientes (Gao et al., Dang et al.), su dependencia de operaciones de clave pública los hace lentos en comparación con las operaciones de clave simétrica.

2. Metodología Propuesta

Los autores proponen un nuevo marco de trabajo para FPSI que logra complejidad lineal en el tamaño de los conjuntos ($m, n$), la dimensión ($d$) y el umbral de distancia ($\delta$), utilizando principalmente operaciones de clave simétrica (más baratas) en lugar de criptografía de clave pública.

Componentes Clave:

1. OPPRF con Salidas Compartidas (so-OPPRF):

   • Introducen un nuevo bloque de construcción: una Función Pseudoaleatoria Programable Oblivious (OPPRF) donde las salidas no se revelan a ninguna de las partes individualmente, sino que se entregan como comparticiones secretas (secret shares) entre el remitente y el receptor.
   • Se construye combinando una OPRF con salidas compartidas (so-OPRF) y un Almacenamiento de Clave-Valor Oblivious (OKVS). Esto permite programar la PRF en puntos específicos sin revelar la función completa.

2. Mapeo Difuso Modular:

   • Dividen el protocolo en dos fases: Mapeo Grosero (asignar identificadores a elementos cercanos) y Filtrado Refinado (verificación exacta).
   • Utilizan el so-OPPRF para realizar el mapeo local y global. Para evitar fugas de información sobre coincidencias parciales en dimensiones individuales (un problema en trabajos previos), introducen una OPRF con Entradas Compartidas (si-OPRF). Esto asegura que los identificadores finales solo se revelen si se cumple la condición de distancia, manteniendo la privacidad incluso cuando hay superposiciones en los intervalos de mapeo.

3. Optimizaciones con Prefijos:

   • Para umbrales de distancia ($\delta$) grandes, la complejidad lineal en $\delta$ sigue siendo costosa.
   • Incorporan una técnica de representación de prefijos (similar a la usada en trabajos previos pero adaptada a su marco de clave simétrica). En lugar de programar todo el intervalo $[q - \delta, q + \delta]$, el remitente programa solo $O(\log \delta)$ prefijos que cubren el intervalo.
   • Esto reduce la complejidad de comunicación y computación de $O(\delta)$ a $O(\log \delta)$.

4. Protocolo de Filtrado Refinado:

   • Una vez obtenidos los identificadores candidatos, utilizan pruebas de igualdad privada (PEQT) y transferencias obliviosas (OT) para verificar si la distancia real es $\le \delta$, eliminando los falsos positivos generados en la fase de mapeo.

3. Contribuciones Clave

1. so-OPPRF: Definición y construcción eficiente de una OPPRF con salidas compartidas, un bloque fundamental que permite evitar la revelación de valores intermedios.
2. Diseño Modular de Mapeo Difuso: Un protocolo que combina so-OPPRF y si-OPRF para lograr un mapeo seguro y eficiente sin depender de AHE.
3. Protocolos FPSI Eficientes: Implementación de protocolos para métricas $L_p$ ($p \in [1, \infty]$) con complejidad lineal en todos los parámetros, utilizando operaciones de clave simétrica.
4. Optimizaciones de Prefijos: Adaptación de técnicas de prefijos para reducir la dependencia del umbral $\delta$ a logarítmica, mejorando el rendimiento en escenarios con grandes distancias.
5. Evaluación Exhaustiva: Implementación completa y comparación con el estado del arte (Gao et al. ASIACRYPT'24 y Dang et al. CCS'25).

4. Resultados Experimentales

Los autores implementaron sus protocolos en C++ y los compararon con las implementaciones públicas de los trabajos más recientes (Gao et al. y Dang et al.) bajo las mismas condiciones de hardware y red.

• Rendimiento General: Sus protocolos superan consistentemente a los trabajos existentes en todos los escenarios probados.
• Mejoras en Tiempo de Ejecución:
  • Comparado con Gao et al. (ASIACRYPT'24): Aceleración de 12x a 145x.
  • Comparado con Dang et al. (CCS'25): Aceleración de 9x a 80x.
• Mejoras en Costo de Comunicación:
  • Comparado con Gao et al.: Reducción de 3x a 8x.
  • Comparado con Dang et al.: Reducción de 5x a 19x.
• Escalabilidad: Las mejoras son más pronunciadas a medida que aumentan el tamaño del conjunto y la dimensión, debido a la amortización de la sobrecarga de las operaciones de OT silencioso (Silent OT).
• Optimizaciones con Prefijos: Para umbrales grandes ($\delta \ge 64$), la versión con prefijos reduce el costo de comunicación hasta en 11x y el tiempo de ejecución a la mitad en comparación con la versión sin prefijos, manteniendo una ventaja significativa sobre los competidores.

5. Significado e Impacto

Este trabajo representa un avance significativo en la criptografía aplicada a la privacidad de datos:

• Eficiencia Práctica: Demuestra que es posible lograr FPSI eficiente para métricas generales $L_p$ sin depender de primitivas de clave pública costosas (AHE), haciendo viable su uso en aplicaciones del mundo real como sistemas biométricos a gran escala.
• Nuevos Bloques de Construcción: La introducción de so-OPPRF y si-OPRF ofrece nuevas herramientas para el diseño de protocolos MPC (Cálculo Multi-Partidario) seguros y eficientes, que pueden ser de interés independiente para la comunidad de investigación.
• Superioridad Técnica: Al lograr complejidad lineal (o logarítmica con prefijos) con operaciones de clave simétrica, establece un nuevo estándar de rendimiento para el PSI difuso, superando las limitaciones de complejidad exponencial o alto costo computacional de las soluciones anteriores.

En resumen, el paper resuelve el cuello de botella de la eficiencia en el PSI difuso, proporcionando una solución escalable, segura y práctica para el análisis de datos sensibles en entornos multidimensionales.