💻 computer science

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

Este artículo presenta nuevos protocolos de Intersección de Conjuntos Privados Difusos (FPSI) para distancias $L_p$ generales que logran una dependencia logarítmica óptima respecto al umbral de distancia $\delta$ utilizando únicamente transferencia de información oblicua y primitivas de clave simétrica, eliminando así la necesidad de un cifrado homomórfico costoso mientras superan significativamente a las soluciones de vanguardia en tiempo de ejecución y comunicación.

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

Publicado 2026-06-16

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

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

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina a dos personas, Alice y Bob, que quieren averiguar si tienen objetos "similares" en sus respectivas colecciones sin mostrarse sus listas completas.

El Problema: En un juego estándar, solo emparejarían elementos que son exactamente iguales (por ejemplo, ambos tienen una "Manzana Roja").
El Giro (PSI Difuso): En este nuevo juego, quieren emparejar elementos que son lo suficientemente parecidos. Por ejemplo, si Alice tiene una "Manzana Roja" y Bob tiene una "Manzana Roja Ligeramente Magullada", deben contar como una coincidencia. La regla es: "Si la diferencia entre nuestros elementos es menor que una distancia específica (llamémosla Umbral, Threshold), emparejamos".

El desafío es hacer esto de forma segura. Alice no debería conocer la lista completa de Bob, y Bob no debería conocer la lista completa de Alice. Solo quieren saber cuáles elementos son lo suficientemente cercanos.

La Forma Antigua: La Búsqueda Lenta y Costosa

Los métodos anteriores para este juego de "Emparejamiento Difuso" tenían dos grandes problemas:

La Trampa "Lineal": Si el umbral de "cercanía" era grande (digamos, 100 unidades), las computadoras tenían que comprobar 100 posibilidades diferentes para cada elemento. Era como buscar una aguja en un pajar revisando cada brizna de paja una por una. Cuanto mayor era el umbral, más lento se volvía.
El Problema de la "Maquinaria Pesada": Para que esto funcionara de forma segura, los métodos antiguos utilizaban herramientas criptográficas muy pesadas y lentas (como el Cifrado Homomórfico Aditivo). Piensa en esto como intentar enviar un mensaje secreto usando un camión enorme y que consume mucho combustible cuando un bicicleta bastaría.

El Nuevo Avance: El Atajo del "Prefijo"

Este artículo introduce una nueva forma de jugar al juego que es rápida, ligera e inteligente.

1. La Analogía del "Código Postal" (Prefijos)

En lugar de comprobar cada número en un rango (como comprobar si un número es 10, 11, 12... hasta 100), los autores utilizan un truco llamado Prefijos.

Imagina que estás buscando una casa en una ciudad.

Forma Antigua: Llamas a la puerta de cada vecino del barrio para ver si el residente es tu amigo.
Nueva Forma: Miras el Código Postal. Si tu amigo vive en el "10001", solo necesitas revisar las casas que tengan ese prefijo. No necesitas revisar toda la ciudad.

Los autores se dieron cuenta de que cualquier "rango" de números (el umbral) puede dividirse en solo unos pocos "Códigos Postales" (prefijos).

La Magia: El tiempo que toma comprobar estos prefijos no crece con el tamaño del umbral; crece logarítmicamente.
- Si el umbral se duplica, el trabajo solo aumenta un poco.
- Si el umbral se hace 100 veces más grande, el trabajo solo se duplica.
- Analogía: Es como encontrar un libro en una biblioteca. Revisar cada libro lleva una eternidad. Revisar la etiqueta del estante (el prefijo) toma segundos, sin importar cuántos libros haya en el estante.

2. Las Herramientas "Ligeras" (Primitivas Simétricas)

Los autores reemplazaron los "camiones" pesados (cifrado costoso) por "bicicletas" (primitivas de clave simétrica y Transferencia Obliviosa).

Transferencia Obliviosa (OT): Imagina a un camarero que puede darte uno de dos artículos secretos del menú sin que tú sepas cuál elegiste, y sin que el camarero sepa cuál querías. Los autores usan esto para intercambiar información de forma segura sin revelar la lista completa.
El Resultado: Su sistema está construido enteramente a partir de estas herramientas ligeras y rápidas.

Los Dos Escenarios: Habitaciones Pequeñas vs. Grandes Salones

El artículo ofrece dos estrategias diferentes dependiendo de qué tan "concurrido" sea el dato (dimensionalidad):

Escenario A: Bajas Dimensiones (La Suposición del "Apartamento")

El Entorno: Piensa en una habitación pequeña donde las personas están paradas lejos unas de otras (al menos 2 veces la distancia del umbral).
La Estrategia: Utilizan Hashing Espacial. Imagina dividir la habitación en una cuadrícula de baldosas. Si dos personas están cerca, deben estar en la misma baldosa o en las baldosas vecinas. El protocolo solo comprueba esas baldosas específicas.
La Innovación: Combinaron este sistema de cuadrícula con su nuevo atajo de "Prefijo" y una herramienta especial de "Comprobación de Igualdad" (llamada ECSS). Esto les permite encontrar coincidencias instantáneamente sin comprobar cada par.

Escenario B: Altas Dimensiones (La Suposición de "Separación")

El Entorno: Piensa en un almacén masivo y multidimensional. En altas dimensiones, dividir el espacio en una cuadrícula crea demasiadas baldosas vacías (la "maldición de la dimensionalidad").
La Estrategia: Utilizan la Generación de ID Distribuida. En lugar de una cuadrícula, le dan a cada elemento una "tarjeta de identificación" única basada en su ubicación.
La Innovación: Crearon una nueva forma de generar estos IDs de manera segura utilizando su truco de "Prefijo". Incluso en un almacén gigante, pueden generar estos IDs de modo que, si dos elementos están cerca, sus IDs coincidirán, sin revelar las ubicaciones reales de los elementos.

La "Receta Secreta": Suma Condicional de Igualdad

La herramienta matemática central de su invención es la Suma Condicional de Igualdad (ECSS).

Cómo funciona: Imagina que Alice y Bob tienen ambos una lista de números. Quieren sumar los números solo si se cumple una condición específica (por ejemplo, "Solo suma los números si los prefijos coinciden").
La Magia: Pueden realizar esta suma de forma segura sin que ninguna de las partes revele sus números. Si los prefijos no coinciden, el resultado es solo ruido aleatorio. Si coinciden, el resultado es la suma correcta. Esto les permite verificar la cercanía de los elementos sin ver nunca los valores reales.

Los Resultados: Una Mejora Masiva de Velocidad

Los autores construyeron una versión funcional de su sistema y lo probaron contra los mejores métodos existentes.

Velocidad: Su sistema es hasta 43.7 veces más rápido que el mejor método anterior.
Uso de Datos: Utiliza hasta 31.3 veces menos datos para enviar a través de la red.
Escalabilidad: Mientras que otros sistemas colapsaban (se quedaban sin memoria) cuando los conjuntos de datos se volvían muy grandes, su sistema siguió funcionando sin problemas.

Resumen

En resumen, este artículo resuelve el problema del "Emparejamiento Difuso" mediante:

Reemplazar el cifrado lento y pesado por herramientas rápidas y ligeras.
Usar "Prefijos" (como Códigos Postales) para convertir una búsqueda lineal lenta en una búsqueda logarítmica rápida.
Crear nuevas herramientas de "Suma Secreta" que permiten a dos partes comprobar la cercanía sin revelar sus secretos.

El resultado es un sistema que puede encontrar elementos "similares" en conjuntos de datos privados masivos casi instantáneamente, haciendo que el emparejamiento de datos preservando la privacidad sea práctico a gran escala por primera vez.

Resumen Técnico: FPSI Difuso mediante Primitivas Simétricas con Dependencia Logarítmica Exacta de la Distancia de Umbral

Planteamiento del Problema
La Intersección de Conjuntos Privada Difusa (FPSI, por sus siglas en inglés) permite que un emisor con un conjunto de vectores de $d$ dimensiones $Q$ y un receptor con un conjunto $W$ identifiquen elementos $q \in Q$ tales que exista un $w \in W$ con $\text{dist}(q, w) \le \delta$ , sin revelar información adicional. Si bien el PSI estándar ha logrado una alta eficiencia, los protocolos de FPSI existentes enfrentan cuellos de botella teóricos y prácticos significativos. Los trabajos previos suelen exhibir un escalado lineal con la distancia de umbral $\delta$ (es decir, $O(\delta)$ ), o logran una dependencia polilogarítmica solo para distancias $L_\infty$ . Los protocolos que admiten distidades de Minkowski generales ( $L_p$ para $p \in [1, \infty]$ ) con dependencia logarítmica en $\delta$ han dependido, o bien, de un costoso Cifrado Homomórfico Aditivo (AHE), o bien, han sufrido fallos de seguridad y términos de complejidad exponencial en la dimensión $d$ . El objetivo es lograr una dependencia logarítmica exacta en $\delta$ para distancias $L_p$ generales utilizando únicamente primitivas de clave simétrica eficientes.

Metodología y Técnicas Principales
Los autores proponen nuevos protocolos de FPSI construidos enteramente a partir de Transferencia Obliviosa (OT) y primitivas de clave simétrica, evitando operaciones de clave pública como el AHE. La construcción se basa en dos supuestos principales: el supuesto apart (adecuado para entornos de baja dimensión) y el supuesto separate (adecuado para entornos de alta dimensión).

Representación de Prefijos y Prueba de Intervalos:
La innovación central reemplaza la enumeración de todos los enteros en un intervalo $[q_k - \delta, q_k + \delta]$ (que tiene un costo de $O(\delta)$ ) con una representación de prefijos utilizando $O(\log \delta)$ prefijos. Esto reduce el costo de prueba de intervalos a $O(\log \delta)$ por dimensión.
Suma Condicional de Igualdad / Compartición de Producto Interno Condicional de Igualdad (ECSS/ECIPS):
Para manejar la interacción requerida por el emparejamiento de prefijos sin revelar la entrada del emisor ni incurrir en una sobrecarga exponencial, los autores introducen dos nuevas primitivas criptográficas:
- Compartición de Suma Condicional de Igualdad (ECSS): Utilizada para la distancia $L_\infty$ . Permite a las partes calcular una suma de valores condicionados a un emparejamiento de igualdad entre los vectores de entrada, entregando las partes secretas del resultado.
- Compartición de Producto Interno Condicional de Igualdad (ECIPS): Utilizada para distancias $L_p$ generales. Calcula un producto interno condicionado a la igualdad, permitiendo el cálculo de $|w_k - q_k|^p$ mediante la expansión binomial sin revelar los términos específicos.
  Ambas primitivas se implementan eficientemente utilizando OT, Funciones de Prerregistro Programables Obliviosas (OPPRF) y protocolos de Permute+Share (PS).
Manejo de Múltiples Elementos:
- Baja Dimensión ( $L_\infty$ y $L_p$ ): Los protocolos utilizan hashing espacial (celdas de rejilla) combinado con hashing Cuckoo para reducir el número de comparaciones por pares. Los autores introducen optimizaciones utilizando OPRF compartida (sOPPRF) para eliminar la necesidad de valores ficticios en celdas vacías, ocultando así las posiciones de hashing del emisor y eliminando la necesidad de pasos de permutación global en ciertas configuraciones.
- Alta Dimensión ( $L_\infty$ y $L_p$ ): Para evitar el costo exponencial $O(2^d)$ del hashing espacial, los autores emplean un protocolo de Generación de ID Distribuida (dIDG). Este protocolo genera IDs únicos para los elementos de tal manera que los elementos cercanos comparten un ID. Los autores identifican fallos de seguridad en construcciones dIDG previas (específicamente en [DZL25]) relacionados con la filtración por colisión y proponen un dIDG seguro basado en clave simétrica utilizando sOPRF y ECSS.

Contribuciones Clave

Nuevas Primitivas: La introducción de ECSS y ECIPS, que permiten el emparejamiento difuso eficiente con una dependencia logarítmica exacta en $\delta$ utilizando únicamente primitivas simétricas.
Complejidad Óptima: Los primeros protocolos de FPSI para distancias $L_p \in [1, \infty]$ generales que logran una complejidad estrictamente logarítmica $O(d \log \delta)$ en el umbral $\delta$ . Esto es teóricamente óptimo, ya que distinguir valores en un intervalo de longitud $O(\delta)$ requiere $\Omega(\log \delta)$ bits de información.
Seguridad y Eficiencia: Los protocolos eliminan la dependencia de AHE, reemplazándola con operaciones de OT y clave simétrica. Los autores también identifican y corrigen vulnerabilidades de seguridad en protocolos basados en prefijos recientes (por ejemplo, [DZL25]) que sufrían de reutilización de máscaras y filtración por colisión.
Construcciones Escalables: Construcciones separadas para entornos de baja dimensión (usando hashing espacial) y de alta dimensión (usando dIDG), logrando ambas una complejidad asintótica óptima.

Resultados Experimentales
Los autores implementaron sus protocolos y los compararon con trabajos de vanguardia ([GQL+24], [DZL25], [BGMP25]).

Rendimiento: Los nuevos protocolos superan significativamente al estado del arte. En entornos de baja dimensión, logran ser hasta 43.7× más rápidos en tiempo de ejecución y tener una sobrecarga de comunicación 31.3× menor.
Escalabilidad: Mientras que trabajos previos como [GQL+24] y [DZL25] encontraron desbordamiento de memoria con tamaños de conjunto de $2^{16}$ en entornos de alta dimensión, los protocolos propuestos se ejecutaron exitosamente bajo las mismas configuraciones.
Dependencia del Umbral: Los experimentos confirman que los costos de tiempo de ejecución y comunicación escalan logarítmicamente con $\delta$ , contrastando con el escalado lineal observado en los protocolos de dependencia lineal anteriores.

Significado
El artículo afirma un avance teórico en el escalado óptimo del umbral para FPSI, demostrando que la dependencia logarítmica exacta en $\delta$ es alcanzable para distancias $L_p$ generales sin la necesidad de criptografía de clave pública costosa. Prácticamente, esto avanza la viabilidad de aplicaciones de FPSI escalables en dominios que requieren emparejamiento difuso, como el emparejamiento de secuencias genómicas, la recuperación de imágenes similares y la detección de credenciales comprometidas, al eliminar los cuellos de botella de eficiencia asociados con el umbral de distancia y la dimensionalidad.