Intersección de Conjunto Privado Multipartidista Sobre-Umbral para Detección Colaborativa de Intrusiones en Red

Información Básica

• ID del Artículo: 2510.12045
• Título: Over-Threshold Multiparty Private Set Intersection for Collaborative Network Intrusion Detection
• Autores: Onur Eren Arpaci, Raouf Boutaba, Florian Kerschbaum (Universidad de Waterloo)
• Clasificación: cs.CR (Criptografía y Seguridad), cs.NI (Arquitectura de Redes e Internet)
• Fecha de Publicación: 14 de octubre de 2025 (preimpresión en arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2510.12045

Resumen

Una función importante en la detección colaborativa de intrusiones en red es analizar los registros de red de los colaboradores para identificar direcciones IP comunes. Sin embargo, compartir direcciones IP en texto plano es sensible e incluso puede estar sujeto a leyes de privacidad, ya que constituye información de identificación personal. Este artículo propone un método de recopilación que preserva la privacidad de direcciones IP, presentando un protocolo de intersección de conjunto privado sobre-umbral con un único recopilador. En este protocolo, N participantes identifican direcciones IP que aparecen en los conjuntos de al menos t participantes sin revelar información alguna sobre otras direcciones IP. Mediante un esquema de hash novedoso, se reduce la complejidad computacional de la solución de última generación anterior de $O(M(N \log{M}/t)^{2t})$ a $O(t^2M\binom{N}{t})$, donde M representa el tamaño del conjunto de datos. Esta reducción hace que sea práctico aplicar el protocolo a registros de red reales.

Antecedentes de Investigación y Motivación

Definición del Problema

El problema central en la detección colaborativa de intrusiones en red es cómo identificar ataques multi-institucionales mientras se protege la privacidad. La investigación demuestra que el 75% de los ataques institucionales se propagan a una segunda institución dentro de un día, y más del 40% se propagan dentro de una hora. Los atacantes típicamente utilizan un pequeño número de direcciones IP externas para atacar simultáneamente múltiples instituciones. Si una dirección IP externa se conecta a al menos t instituciones dentro de una ventana de tiempo específica, puede clasificarse como maliciosa con una recuperación del 95%.

Desafíos de Privacidad

Los métodos tradicionales requieren que las instituciones compartan registros de red en texto plano, lo que presenta riesgos graves de privacidad:

1. Cumplimiento Legal: Las direcciones IP se clasifican como información de identificación personal según GDPR, PIPEDA, CCPA y otras leyes
2. Sensibilidad de Datos: Los datos de red sin procesar son más sensibles que las alertas de seguridad, conteniendo abundante información sensible irrelevante
3. Escala de Datos: Los datos sin procesar son varios órdenes de magnitud más grandes que las alertas de seguridad, haciendo que las soluciones existentes sean computacionalmente inviables

Limitaciones de Métodos Existentes

• Kissner and Song 26: Requiere O(N) rondas de comunicación, complejidad computacional O(N³M³)
• Mahdavi et al. 34: Aunque mejora la complejidad de comunicación, el costo computacional sigue siendo excesivo, con complejidad O(M(N logM/t)²ᵗ)

Contribuciones Principales

1. Esquema de Hash Novedoso: Propone un algoritmo de hash innovador que reduce la complejidad computacional de O(M(N logM/t)²ᵗ) a O(t²M(N choose t)), logrando complejidad lineal en M
2. Mejora de Practicidad: Permite que el protocolo maneje registros de red a escala real, completando la detección en 170 segundos con 33 instituciones participantes y hasta 144,045 direcciones IP
3. Opciones de Implementación Dual:
   • Implementación Resistente a Colusión: Proporciona garantías de seguridad más fuertes, pero con mayor sobrecarga de comunicación
   • Implementación No-Interactiva: Asume recopilador no-colusivo, reduciendo significativamente los costos de comunicación
4. Prueba de Seguridad: Demuestra la seguridad del protocolo bajo el modelo de computación multipartidista semi-honesto
5. Validación Práctica: Evaluación utilizando registros de red reales del proyecto CANARIE IDS

Explicación Detallada del Método

Definición de Tarea

Intersección de Conjunto Privado Multipartidista Sobre-Umbral (OT-MP-PSI):

• Entrada: N participantes, cada uno poseyendo un conjunto Sᵢ de como máximo M elementos
• Salida: Identificar elementos que aparecen en al menos t conjuntos, sin revelar información sobre elementos por debajo del umbral
• Restricción: Modelo de seguridad semi-honesto, los participantes siguen el protocolo pero pueden intentar aprender información adicional

Componentes Técnicos Principales

1. Compartición Secreta de Shamir

Utiliza un esquema de umbral (t,n), donde cualquier t partes pueden reconstruir el secreto V, y menos de t partes no pueden obtener información alguna:

P(x) = c_{t-1}x^{t-1} + c_{t-2}x^{t-2} + ... + c_1x + V

2. Función Pseudoaleatoria Olvidadiza (OPRF)

Los participantes aprenden H_K(x) sin conocer la clave K, y el titular de la clave no conoce la entrada x ni los valores de salida.

3. Compartición Secreta Pseudoaleatoria Olvidadiza (OPR-SS)

Combina las propiedades de seguridad de la compartición secreta y OPRF, permitiendo que los participantes obtengan acciones secretas únicas del titular de la clave.

Arquitectura del Protocolo

Implementación No-Interactiva

1. Creación de Acciones: Cada participante crea acciones secretas para cada elemento en su conjunto
2. Mapeo de Hash: Utiliza el nuevo esquema de hash para mapear acciones a cubetas de tamaño 1
3. Reconstrucción: El agregador intenta interpolación de Lagrange para todas las combinaciones de t participantes
4. Notificación de Resultados: El agregador notifica a los participantes los índices reconstruidos exitosamente

Implementación Resistente a Colusión

Utiliza el protocolo OPR-SS en lugar de compartir claves, calculando la función de hash mediante protocolo OPRF multi-clave, proporcionando garantías más fuertes contra colusión.

Puntos de Innovación Técnica

Esquema de Hash Novedoso

Idea Central: Utiliza cubetas de tamaño 1 para evitar colisiones de hash, en lugar de acomodarlas:

1. Manejo de Colisiones: Cuando múltiples elementos se mapean a la misma cubeta, utiliza ordenamiento pseudoaleatorio para seleccionar el más pequeño
2. Estrategia Multi-Tabla: Cada participante crea múltiples tablas, asegurando que los valores perdidos aparezcan en otras tablas
3. Control de Probabilidad de Fallo: Controla la probabilidad de fallo por debajo de 2⁻⁴⁰ mediante 20 tablas

Ventajas Clave:

• El agregador solo necesita intentar combinaciones de participantes, no combinaciones de acciones
• La complejidad se reduce de exponencial a lineal (respecto a M)
• Evita los grandes factores constantes de los métodos tradicionales de cubetización

Técnicas de Optimización

1. Inversión de Ordenamiento: Las dos tablas consecutivas utilizan la misma función de ordenamiento, las tablas pares invierten el ordenamiento
2. Utilización de Cubetas Vacías: La segunda inserción utiliza cubetas vacías después de la primera inserción

Configuración Experimental

Conjunto de Datos

• Datos Reales: Registros de conexión de red de 54 instituciones del proyecto CANARIE IDS
• Rango Temporal: 1-8 de noviembre de 2023, aproximadamente 8 mil millones de entradas de registro diarias
• Escala de Datos: Aproximadamente 700GB diarios (comprimido con gzip)
• Método de Procesamiento: Procesamiento en lotes por hora, extrayendo conexiones de IP externa a IP interna

Métricas de Evaluación

• Tiempo de Reconstrucción: Tiempo para que el agregador complete la reconstrucción
• Tiempo de Generación de Acciones: Tiempo para que un participante individual cree acciones
• Complejidad de Comunicación: Sobrecarga total de comunicación del protocolo
• Corrección: Verificación de probabilidad de fallo

Métodos de Comparación

• Mahdavi et al. 34: Solución OT-MP-PSI de última generación actual
• Límites Teóricos: Comparación con límites de probabilidad de fallo calculados

Detalles de Implementación

• Lenguaje de Programación: Julia, 430 líneas de código
• Biblioteca Criptográfica: SHA.jl, Nettle.jl
• Campo Finito: Número primo de Mersenne de 61 bits
• Entorno de Hardware: 8×procesadores Intel Xeon E7-8870, 80 núcleos físicos, 1TB de memoria

Resultados Experimentales

Resultados Principales

Comparación de Rendimiento

En comparación con Mahdavi et al. 34:

• Mejora de Velocidad: Al menos dos órdenes de magnitud, hasta 23,066 veces más rápido
• Escalabilidad: Con M=10⁵, este método requiere cientos de segundos, mientras que el método de comparación requiere días

Rendimiento en Datos Reales

Rendimiento en datos CANARIE:

• Tiempo Promedio de Reconstrucción: 170 segundos
• Tiempo Máximo de Reconstrucción: 438 segundos (40 instituciones, 220,011 direcciones IP)
• Instituciones Participantes Promedio: 33
• Tamaño Máximo Promedio de Conjunto: 144,045 direcciones IP

Análisis de Complejidad

Complejidad Computacional

• Agregador: O(t²M(N choose t))
• Participantes (No-Interactivo): O(tM)
• Casos Especiales: N=t=2 es O(M), N=t es O(N²M)

Complejidad de Comunicación

• Implementación No-Interactiva: O(tMN)
• Implementación Resistente a Colusión: O(tkMN), 5 rondas de comunicación

Verificación de Corrección

• Probabilidad Teórica de Fallo: 2⁻⁴⁰
• Verificación Experimental: En 10⁷ pruebas, los fallos reales están muy por debajo del límite teórico
• Optimización de Tablas: Optimizado de 28 tablas teóricas a 20 tablas prácticas

Trabajo Relacionado

Soluciones OT-MP-PSI

1. Kissner and Song 26: Primera solución, utilizando representación polinomial, complejidad O(N³M³)
2. Mahdavi et al. 34: Rondas constantes, complejidad O(M(N logM/t)²ᵗ)
3. Ma et al. 33: Aplicable a entradas pequeñas y dominios pequeños, complejidad O(N|S|)

Problemas Relacionados

• Intersección de Conjunto Privado con Umbral (TPSI): Aprender la intersección si y solo si el tamaño de la intersección excede el umbral
• Quorum-PSI: Caso especial de OT-MP-PSI, solo participantes específicos tienen salida

Técnicas de Hash

• Hash de Cuco: Utilizado para evitar colisiones de hash, ampliamente aplicado en protocolos PSI
• Hash de Cuco 2D: Diseñado específicamente para PSI de dos partes, logrando complejidad O(M)

Conclusiones y Discusión

Conclusiones Principales

1. Avance en Practicidad: Primera vez que OT-MP-PSI es prácticamente viable a escala de registros de red reales
2. Mejora de Eficiencia: Logra mejora de rendimiento de órdenes de magnitud mediante el nuevo esquema de hash
3. Implementación Flexible: Proporciona dos opciones de implementación adaptadas a diferentes requisitos de seguridad
4. Validación Práctica: Verifica la practicidad del protocolo en entornos de red multi-institucionales reales

Limitaciones

1. Modelo Semi-Honesto: Aunque extensible al modelo malicioso, sigue siendo vulnerable a ataques de sustitución de entrada
2. Fuga de Tamaño de Conjunto: El protocolo central no trata el tamaño del conjunto de participantes como información privada
3. Confianza en Agregador: La implementación no-interactiva requiere confiar en que el agregador no coluda con los participantes
4. Restricción de Umbral: Cuando t se acerca a N/2 y N es grande, la ventaja de complejidad puede no ser evidente

Direcciones Futuras

1. Seguridad Maliciosa: Extender el protocolo para resistir atacantes activos
2. Umbral Dinámico: Soportar computación multi-umbral sin costo adicional para clientes
3. Optimización a Gran Escala: Optimizar aún más el procesamiento de combinaciones de participantes
4. Privacidad Mejorada: Explorar técnicas de privacidad diferencial para proteger información de tamaño de conjunto

Evaluación Profunda

Fortalezas

1. Contribución Teórica Significativa: El nuevo esquema de hash es un avance importante en la tecnología existente, reduciendo la complejidad exponencial a lineal
2. Alto Valor Práctico: Resuelve el problema clave de privacidad en la detección colaborativa de intrusiones del mundo real
3. Experimentación Suficiente: Incluye tanto análisis teórico como validación con datos reales, con configuración experimental razonable
4. Implementación de Ingeniería Completa: Proporciona implementación de código abierto, mejorando la reproducibilidad
5. Seguridad Rigurosa: Proporciona prueba de seguridad formal y dos opciones de implementación

Deficiencias

1. Limitación del Modelo de Seguridad: El modelo semi-honesto puede no ser suficientemente fuerte en algunos escenarios prácticos
2. Selección de Parámetros: La selección de 20 tablas se basa en optimización empírica, con orientación teórica insuficiente
3. Límites de Escalabilidad: La aplicabilidad a escala extremadamente grande (como nivel de Internet global) no se ha explorado suficientemente
4. Comparación de Referencia Limitada: Principalmente comparado con un método de referencia, faltando comparación de rendimiento más completa

Impacto

1. Valor Académico: Proporciona una nueva ruta técnica para el campo de la computación multipartidista segura
2. Significado Práctico: Resuelve directamente necesidades reales en el campo de la seguridad de redes
3. Promoción Tecnológica: El esquema de hash puede ser aplicable a otros problemas de computación multipartidista
4. Potencial de Estandarización: Tiene potencial para convertirse en protocolo estándar para detección colaborativa de intrusiones

Escenarios Aplicables

1. Seguridad de Red Multi-Institucional: Protección colaborativa de instituciones similares como universidades y hospitales
2. Servicios de Seguridad en la Nube: Análisis de registros que preserva privacidad en centros de operaciones de seguridad
3. Intercambio de Inteligencia de Amenazas: Intercambio de indicadores de amenaza bajo restricciones de privacidad
4. Requisitos de Cumplimiento: Colaboración de datos que cumple con regulaciones de privacidad como GDPR

Referencias

Este artículo cita 53 referencias relacionadas, cubriendo trabajos importantes en múltiples campos incluyendo criptografía, seguridad de redes y computación multipartidista, proporcionando una base teórica sólida y contexto técnico completo.

Evaluación General: Este es un artículo de alta calidad en criptografía aplicada que logra un buen equilibrio entre innovación teórica y aplicación práctica. El nuevo esquema de hash propuesto no solo representa un avance importante en teoría, sino que también demuestra valor significativo en aplicaciones prácticas. La validación experimental es suficiente, el análisis de seguridad es riguroso, y proporciona una contribución técnica importante al campo de la seguridad de redes colaborativa.