💻 computer science

Efficient Fuzzy PSI under One-Sided Assumptions

Este artículo introduce los primeros protocolos de intersección de conjuntos privados difusos concretamente eficientes para distancias $L_p$ generales bajo supuestos unidireccionales, aprovechando primitivas de clave simétrica ligeras y técnicas de trie de prefijos para lograr una complejidad de $O(\log \delta)$ y superar significativamente a los trabajos previos del estado del arte tanto en velocidad de computación como en sobrecarga de comunicación.

Autores originales: Xinpeng Yang, Meng Hao, Yanxue Jia, Chenkai Weng, Yonggang Wen, Tianwei Zhang

Publicado 2026-08-19

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Xinpeng Yang, Meng Hao, Yanxue Jia, Chenkai Weng, Yonggang Wen, Tianwei Zhang

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

En la era digital, dos organizaciones a menudo necesitan encontrar un punto común sin revelar todos sus secretos la una a la otra. Imagine un hospital que posee una lista de pacientes con una condición específica y un instituto de investigación que posee una lista de voluntarios. Quieren saber qué voluntarios son también pacientes, pero ninguna de las partes quiere entregar su lista completa, ya que eso expondría los datos privados de todos los demás en el registro. Los protocolos informáticos estándar pueden resolver este problema de coincidencia exacta de manera eficiente, pero fallan cuando los datos son ligeramente desordenados. En el mundo real, los nombres pueden estar mal escritos, las ubicaciones pueden estar ligeramente erradas y los escaneos biométricos pueden variar de un día para otro. Si el registro del hospital dice "John Smith" y el del voluntario dice "Jon Smyth", un sistema estándar no detecta una coincidencia, aunque se trate de la misma persona. Aquí es donde entra en juego la coincidencia "difusa" (fuzzy matching), un método diseñado para encontrar estas conexiones aproximadas. Sin embargo, realizar esto de forma segura es increíblemente difícil. Si el sistema intenta comparar cada posible variación de cada nombre contra cada otra variación, la cantidad de datos intercambiados se vuelve tan masiva que el proceso se detiene, o requiere una maquinaria matemática tan pesada que se vuelve impracticable para el uso cotidiano.

Un equipo de investigadores ha desarrollado ahora una nueva forma de realizar esta coincidencia difusa que es tanto rápida como ligera. Su trabajo se centra en un escenario donde solo una de las dos partes necesita seguir reglas estrictas sobre cómo se organizan sus datos, mientras que la otra parte puede tener datos en cualquier orden caótico. Los intentos anteriores para resolver este problema bajo tales condiciones relajadas dependían de herramientas criptográficas pesadas y lentas, o requerían que ambas partes tuvieran datos perfectamente organizados, lo cual rara vez sucede en la realidad. El nuevo método, creado por Xinpeng Yang y sus colegas de instituciones en Singapur y los Estados Unidos, logra el mismo objetivo utilizando únicamente componentes básicos simples y rápidos. Lograron reducir el tiempo y los datos requeridos para estas comparaciones por márgenes masivos, haciendo que la coincidencia aproximada segura sea viable por primera vez en muchos entornos del mundo real.

El núcleo del logro reside en cómo los investigadores manejan la "distancia" entre los puntos de datos. En este contexto, la distancia es una medida de qué tan diferentes son dos piezas de información, como cuántas letras difieren entre dos nombres o qué tan lejos están dos coordenadas GPS. El objetivo es encontrar pares donde esta distancia sea menor que un umbral específico. Los investigadores se dieron cuenta de que los métodos anteriores intentaban verificar cada posible variación de un punto de datos, lo que creaba un espacio de búsqueda que crecía de forma explosiva a medida que aumentaba la diferencia permitida. Para solucionar esto, introdujeron una técnica que actúa como un filtro inteligente. En lugar de comprobar cada posibilidad individual, el sistema organiza los datos en una estructura de tipo árbol que le permite saltarse instantáneamente grandes bloques de información irrelevante. Este cambio redujo el esfuerzo computacional de un nivel que crecía exponencialmente con el tamaño de la búsqueda a un nivel que crece solo logarítmicamente. En términos prácticos, esto significa que incluso si la diferencia permitida entre los puntos de datos se duplica o triplica, el tiempo que tarda en ejecutarse la verificación apenas aumenta.

El equipo probó sus nuevos protocolos contra los mejores métodos existentes actualmente disponibles. Los resultados fueron dramáticos. Al compararse con un protocolo reciente de 2024, su nuevo sistema fue hasta 239 veces más rápido y utilizó hasta 20 veces menos ancho de banda de comunicación. Contra un método de 2025, la aceleración alcanzó las 518 veces, con una reducción de 63 veces en la transferencia de datos. En una comparación específica contra otra construcción de 2025, el nuevo sistema fue casi 5,000 veces más rápido y requirió 282 veces menos comunicación. Estas cifras no fueron solo teóricas; los investigadores implementaron el sistema completo y realizaron experimentos extensos a través de una amplia gama de tamaños de datos y configuraciones. Confirmaron que su enfoque funciona independientemente de si el emisor o el receptor es quien tiene los datos organizados, y admite varios tipos de mediciones de distancia, no solo las simples.

Una innovación clave en su trabajo fue la capacidad de manejar supuestos de "un solo lado". En muchos sistemas seguros previos, ambas partes tenían que acordar reglas estrictas, como asegurar que sus puntos de datos estuvieran lo suficientemente espaciados para evitar confusiones. Esto es a menudo imposible en la vida real, donde los datos llegan en grupos o patrones aleatorios. El nuevo método solo requiere que un lado tenga un conjunto de datos algo organizado, mientras que el otro lado puede tener datos completamente arbitrarios y desordenados. Esta flexibilidad hace que la tecnología sea aplicable a escenarios como el rastreo de contactos o los servicios basados en la ubicación, donde una entidad puede tener una base de datos estructurada de ubicaciones conocidas mientras que la otra tiene un flujo de entradas de usuario no estructuradas. Al confiar únicamente en técnicas de clave simétrica ligeras —esencialmente herramientas de cifrado estándar que son rápidas y eficientes—, los investigadores evitaron las operaciones matemáticas pesadas y lentas que habían frenado esfuerzos similares anteriormente.

Los investigadores también exploraron cómo hacer el sistema aún más eficiente cuando los datos son dispersos, es decir, cuando los puntos están repartidos en lugar de agrupados. En estos casos, descubrieron que intercambiar los roles de las dos partes en el proceso de coincidencia podía equilibrar aún más la carga de trabajo y mejorar el rendimiento. Esta adaptabilidad sugiere que el sistema puede ajustarse para diferentes tipos de aplicaciones sin necesidad de un rediseño completo. El trabajo demuestra que es posible construir sistemas seguros que preserven la privacidad y que no solo sean teóricamente sólidos, sino también lo suficientemente rápidos para el despliegue en el mundo real.

Las implicaciones de este trabajo se extienden más allá de la velocidad. Al hacer que la coincidencia difusa sea eficiente, los investigadores han abierto la puerta a aplicaciones de preservación de la privacidad más sofisticadas. Las organizaciones que durante mucho tiempo han evitado compartir datos por temor a filtraciones de privacidad o porque el proceso de coincidencia era demasiado lento, ahora pueden considerar la colaboración segura. Ya sea para cotejar registros de pacientes para la investigación médica, verificar identidades de usuarios sin exponer plantillas biométricas, o encontrar artículos similares en grandes catálogos sin revelar el contenido del catálogo, la barrera de entrada se ha reducido significativamente. El estudio demuestra que, con el enfoque algorítmico adecuado, el compromiso entre privacidad y rendimiento puede resolverse, permitiendo que los datos fluyan de forma segura incluso cuando son imperfectos o ruidosos.

Al final, el artículo presenta una solución concreta a un problema que ha persistido durante años: cómo encontrar coincidencias aproximadas en datos privados sin sacrificar la velocidad ni requerir condiciones poco realistas. Los investigadores no solo propusieron una nueva idea; la construyeron, la probaron y demostraron que supera a todo lo anterior por órdenes de magnitud. Su trabajo es un testimonio del poder de refinar la lógica subyacente de un problema en lugar de simplemente intentar aplicar más potencia de cómputo. Para el observador curioso, el resultado es un sistema que se siente menos como una máquina pesada y tosca y más como una herramienta precisa y eficiente, lista para ser usada en el mundo imperfecto y desordenado de los datos reales.

Resumen Técnico: PSI Difuso Eficiente bajo Supuestos Unilaterales

Planteamiento del Problema

La Intersección de Conjuntos Privada (PSI) difusa permite que dos partes, un emisor y un receptor, identifiquen elementos en sus respectivos conjuntos de entrada que coinciden aproximadamente. Específicamente, dada una distancia umbral $\delta$ y una métrica $dist(\cdot, \cdot)$ , el receptor aprende todos los elementos del emisor $\mathbf{q}$ para los cuales existe un elemento del receptor $\mathbf{w}$ tal que $dist(\mathbf{q}, \mathbf{w}) \le \delta$ .

Mientras que la PSI estándar ha experimentado avances significativos, la PSI difusa enfrenta un compromiso entre eficiencia y la fuerza de los supuestos subyacentes. Las construcciones existentes para distancias $L_p$ generales ( $p \in [1, \infty]$ ) suelen caer en dos categorías:

Supuestos bilaterales: Protocolos que requieren que las entradas de ambas partes satisfagan una fuerte separación geométrica (por ejemplo, puntos separados entre sí por $2\delta$ o $4\delta$ ). Estos son eficientes pero a menudo poco realistas para datos ruidosos del mundo real.
Supuestos unilaterales: Protocolos donde solo una de las partes debe satisfacer restricciones de separación, permitiendo que la otra parte posea entradas arbitrarias. Sin embargo, las soluciones unilaterales existentes ya sea dependen de primitivas criptográficas pesadas (por ejemplo, Cifrado Homomórfico Aditivo) o incurren en una sobrecarga asintótica sustancial en el umbral $\delta$ (por ejemplo, $O(\delta)$ o $O((\log \delta)^d)$ ).

El desafío central abordado es la construcción de protocolos de PSI difusa concretamente eficientes para distancias $L_p$ generales bajo supuestos unilaterales débiles, basándose únicamente en primitivas de clave simétrica ligeras.

Metodología

Los autores proponen un marco construido sobre Funciones Pseudorandom Programables Obliviosas con Secret Sharing (so-OPPRF) y Hashing Espacial, mejorado mediante técnicas de Prefix Trie.

1. Primitivas de Coincidencia Difusa de Multi-Punto

Para manejar entradas arbitrarias de una parte sin filtración, el artículo introduce dos protocolos de coincidencia difusa de multi-punto libres de supuestos:

Coincidencia 1-a- $n$ (el receptor posee puntos arbitrarios): El emisor programa una so-OPPRF con intervalos alrededor de su único punto. Para evitar que el receptor infiera la distribución de la entrada del emisor mediante colisiones en las participaciones agregadas (un problema de filtración en trabajos previos), los autores introducen la Aleatorización Condicional de Igualdad (EqRand). Esta primitiva re-aleatoriza las participaciones secretas para entradas no coincidentes mientras preserva la suma correcta para las entradas coincidentes, asegurando la privacidad incluso cuando múltiples puntos del receptor mapean al mismo intervalo programado.
Coincidencia $m$ -a-1 (el emisor posee puntos arbitrarios): Los roles se invierten. El receptor programa la so-OPPRF con intervalos alrededor de su único punto. El emisor evalúa la función en sus múltiples puntos. Dado que el receptor no reconstruye los valores agregados del lado del emisor, el problema de filtración se evita naturalmente y no se requiere EqRand.

2. PSI Difusa bajo Supuestos Unilaterales

Basándose en las primitivas anteriores, los autores construyen protocolos completos de PSI difusa de $m$ -a- $n$ bajo dos supuestos unilaterales específicos:

Supuesto de Celda Única: Cada celda espacial (de longitud de lado $2\delta$ ) contiene como máximo un punto de la parte restringida.
Supuesto de Bloque Único (Más disperso): Cada celda espacial intersecta con como máximo una bola $L_\infty$ de la parte restringida.

El protocolo utiliza hashing espacial para particionar el espacio. La parte restringida programa la so-OPPRF con claves derivadas de sus puntos e identificadores de celda, asegurando la ausencia de colisiones. La parte no restringida evalúa la función en sus puntos y celdas vecinas. El uso de so-OPPRF asegura que las salidas estén compartidas mediante secret-sharing, evitando que cualquiera de las partes aprenda los datos brutos de la otra.

3. Optimización de Prefix Trie

Para abordar la complejidad lineal o superlineal que escala con $\delta$ encontrada en trabajos previos, los autores incorporan técnicas de Prefix Trie.

Mecanismo: En lugar de enumerar todos los puntos en un intervalo $[w - \delta, w + \delta]$ (lo cual toma $O(\delta)$ ), el intervalo se codifica en $O(\log \delta)$ nodos de prefijo utilizando el algoritmo PxTrie.
Filtrado Dimensión por Dimensión: Los trabajos previos requerían evaluar todas las combinaciones de prefijos a través de $d$ dimensiones, lo que llevaba a una complejidad de $O((\log \delta)^d$ . Los autores introducen una primitiva de Selección Condicional (ConSel) que filtra los prefijos dimensión por dimensión. Dado que a lo sumo un prefijo por dimensión puede coincidir con el objetivo, el espacio de búsqueda se reduce de $O((\log \delta)^d)$ a $O(d \cdot \log \delta)$ .
Resultado: Esto logra una complejidad de $O(\log \delta)$ en el umbral $\delta$ para distancias $L_p$ generales, una mejora significativa sobre los límites previos de $O((\log \delta)^d)$ o $O(\delta)$ .

4. Manejo de Distancias $L_p$ Generales

Para distancias $L_p$ ( $p > 1$ ), el protocolo codifica la potencia $p$ -ésima de la contribución de la distancia por dimensión ( $|t|^p$ ) en los valores de la so-OPPRF. Las partes realizan entonces computación multipartita segura (suma y multiplicación) para agregar estas participaciones y verificar si la distancia total está dentro del umbral $\delta^p$ .

Contribuciones Clave

Primera PSI Difusa Unilateral Eficiente para $L_p$ General: El artículo presenta los primeros protocolos concretamente eficientes para distancias $L_p \in [1, \infty]$ generales bajo supuestos unilaterales, basándose exclusivamente en primitivas de clave simétrica (so-OPPRF, OKVS, silent OT).
Complejidad Logarítmica en $\delta$ : Al integrar de manera no trivial las técnicas de prefix trie con un mecanismo de filtrado dimensión por dimensión, los protocolos logran una complejidad de $O(\log \delta)$ en el umbral de distancia, mejorando los límites de $O((\log \delta)^d)$ u $O(\delta)$ de trabajos de vanguardia.
Soporte de Supuestos Flexibles: El marco soporta tanto configuraciones de Lado del Emisor como de Lado del Receptor, así como supuestos de Celda Única y Bloque Único. El supuesto de Bloque Único permite mayores optimizaciones al invertir los roles de programación y evaluación para explotar el menor costo de programación frente a la evaluación de la so-OPPRF.
Evaluación Extensa: Los autores implementaron los protocolos y los compararon con trabajos de vanguardia (van Baarsen & Pu [31], Dang et al. [10], Bui et al. [6], etc.).

Resultados Experimentales

La evaluación se realizó en un servidor con un procesador AMD EPYC 9554. Los resultados demuestran mejoras significativas tanto en comunicación como en computación:

Contra van Baarsen y Pu (EUROCRYPT'24): Hasta 239 $\times$ más rápido en computación y hasta 20 $\times$ menos comunicación.
Contra Dang et al. (CCS'25): Hasta 518 $\times$ de aceleración y reducción de comunicación de 63 $\times$ .
Contra Bui et al. (ASIACRYPT'25): Hasta 4818 $\times$ más rápido en computación y hasta 282 $\times$ menos comunicación.

Las variantes optimizadas por prefijo (Ours-Px) muestran un rendimiento superior en comunicación para $\delta$ grandes y dimensiones altas, mientras que las variantes no optimizadas (Ours) son altamente competitivas para umbrales más pequeños debido a su menor sobrecarga computacional.

Significado y Reivindicaciones

El artículo afirma resolver el compromiso de larga data entre la fuerza de los supuestos geométricos y la eficiencia de los protocolos de PSI difusa. Al demostrar que la PSI difusa para $L_p$ general puede lograrse bajo supuestos unilaterales débiles utilizando únicamente primitivas de clave simétrica ligeras, este trabajo hace que la PSI difusa sea más aplicable a escenarios del mundo real donde los datos son ruidosos y no se pueden garantizar supuestos de separación estrictos.

Los autores enfatizan que sus protocolos superan significativamente a los trabajos previos bajo supuestos comparables, logrando mejoras de órdenes de magnitud en eficiencia. La introducción del mecanismo de filtrado dimensión por dimensión mediante prefix tries se destaca como una innovación técnica clave que rompe la dependencia exponencial de la dimensionalidad en el parámetro del umbral, haciendo que los protocolos sean escalables para datos de alta dimensión y grandes umbrales de coincidencia.