Property-Preserving Hashing for $\ell_1$-Distance Predicates: Applications to Countering Adversarial Input Attacks

Este artículo presenta la primera construcción de hash que preserva propiedades para predicados de distancia $\ell_1$, diseñada para detectar imágenes similares bajo ataques adversarios y obligar a los atacantes a introducir un ruido significativo que degrade la calidad de la imagen, todo ello con una alta eficiencia computacional.

Lo esencial

¡Claro que sí! Imagina que este artículo es una historia sobre cómo proteger fotos secretas en un mundo lleno de espías digitales. Aquí tienes la explicación, traducida al español y llena de analogías sencillas:

🕵️‍♂️ El Problema: El "Cambio de Disfraz" Digital

Imagina que tienes una galería de fotos de personas (como en un aeropuerto para control de seguridad) y quieres saber si una foto nueva que te envían es de la misma persona, pero sin revelar quién es la persona ni mostrar las fotos originales.

Para hacer esto, usamos un "resumen de la foto" (llamado hash perceptual). Es como tomar una foto, cerrarle los ojos y decir: "Esta foto huele a perro". Si la nueva foto también "huele a perro", es la misma persona.

Pero aquí está el truco: Los hackers (los "malos") han aprendido a poner un poco de maquillaje digital casi invisible en la foto. Cambian un píxel aquí y otro allá (como poner una gota de pintura casi invisible en un cuadro). Para nuestros ojos, la foto sigue siendo la misma persona, pero el "resumen" (el hash) cambia drásticamente y el sistema dice: "¡No es la misma persona!". Esto se llama un ataque de evasión.

🛡️ La Solución: El "Sello de Propiedad" (PPH)

Los autores de este paper proponen una nueva herramienta llamada Hashing que Preserva Propiedades (PPH).

Imagina que en lugar de hacer un resumen de la foto, le pones un sello mágico que contiene una fórmula matemática secreta.

• La magia: Este sello no revela la foto, pero permite a un guardián (el servidor) hacer una pregunta muy específica: "¿Está esta nueva foto tan cerca de la original que podríamos considerarlas gemelas?".
• La diferencia clave: Los sistemas antiguos fallaban porque el "sello" era frágil. Si el hacker cambiaba un píxel, el sello se rompía. Este nuevo sistema es como un sello de goma indestructible: si la foto cambia un poco (dentro de un límite), el sello sigue diciendo "Sí, son similares". Si el hacker intenta cambiarla demasiado para engañar al sistema, el sello dirá "No", pero para lograr eso, el hacker tendrá que deformar la foto tanto que ya no se parecerá a la persona original.

📏 La Regla de la "Distancia" (La Analogía del Metro)

El sistema mide la "distancia" entre dos fotos. No es una distancia en kilómetros, sino en píxeles cambiados.

• Imagina que tienes dos fotos idénticas. Si cambias un píxel, la distancia es 1.
• El sistema tiene una regla de tolerancia (llamada umbral t).
• Si la distancia es menor que t, el sistema dice: "Son la misma foto".
• Si la distancia es mayor, dice: "Son diferentes".

¿Por qué es genial esto contra los hackers?
Los hackers suelen usar matemáticas para cambiar la foto lo menos posible (para que siga pareciendo real) pero lo suficiente para engañar al sistema. Este nuevo sistema les obliga a una elección imposible:

1. Opción A: Cambiar la foto muy poco. El sistema detectará que es la misma persona (¡ataque fallido!).
2. Opción B: Cambiar la foto mucho para engañar al sistema. Pero si cambias la foto mucho, ¡ya no se parece a la persona original! (¡La foto queda destruida!).

Es como intentar disfrazarte para entrar a un club secreto. Si te pones una peluca ligera, el guardia (el sistema) te reconoce. Si te pones una máscara completa y cambias tu voz, el guardia no te reconoce, pero tampoco te parece a ti mismo. ¡No puedes ganar!

⚡ ¿Es rápido? (La analogía de la fábrica)

El sistema es muy rápido, pero si la foto es gigante (como una foto de 4K), calcularlo todo de golpe sería lento.

• La solución: Imagina que la foto es una pizza gigante. En lugar de calcular el sabor de toda la pizza de una vez, la cortamos en 1,000 trozos pequeños (bloques).
• Calculamos el "sello" para cada trozo por separado y muy rápido.
• Como cada trozo se puede calcular al mismo tiempo (en paralelo), el proceso es increíblemente veloz. En pruebas, tardaron menos de un segundo incluso para fotos grandes.

🧩 ¿Cómo funciona la magia matemática? (Sin dolor de cabeza)

Los autores usan algo llamado códigos correctores de errores (como los que usan las naves espaciales para enviar fotos desde Marte).

• Transforman la foto en un polinomio (una ecuación matemática compleja).
• Si la foto cambia un poco, la ecuación cambia un poco, pero la estructura matemática permite saber si están "cerca" sin tener que ver la foto original.
• Es como si la foto fuera un código de barras. Si el código de barras se rayan un poco, el lector sabe que es el mismo producto. Si lo rayan demasiado, el lector sabe que es otro producto, pero el código de barras original ya no se puede leer bien.

🏁 En Resumen

Este paper presenta un nuevo sistema de seguridad para fotos que:

1. Protege la privacidad: No necesitas ver la foto original para compararla.
2. Es a prueba de hackers: Obliga a los atacantes a elegir entre ser detectados o destruir la calidad de la imagen.
3. Es rápido: Funciona cortando las imágenes en trozos pequeños para procesarlas a la velocidad de la luz.

Es como tener un guardaespaldas matemático que sabe exactamente cuándo alguien está intentando disfrazarse, sin necesidad de ver el disfraz en detalle.

Resumen técnico

Resumen Técnico: Hashing Preservador de Propiedades para Predicados de Distancia ℓ1

1. Planteamiento del Problema

El hashing perceptual se utiliza ampliamente para detectar similitudes entre imágenes (por ejemplo, en reconocimiento facial o detección de contenido ilegal en la nube). Sin embargo, estos sistemas son vulnerables a ataques de evasión adversaria. En estos ataques, un oponente introduce perturbaciones imperceptibles en una imagen para que, aunque visualmente sea similar a la original, su hash digest sea completamente diferente, evadiendo así la detección.

La razón fundamental de esta vulnerabilidad es que el hashing perceptual (y el hashing sensible a la localidad en general) no garantiza una corrección negligible. Es decir, la probabilidad de que dos imágenes perceptualmente similares produzcan hashes diferentes no es despreciable, lo que deja espacio para que los atacantes manipulen la imagen sin ser detectados.

La Hashing Preservador de Propiedades (PPH) es una construcción criptográfica más reciente que garantiza que ciertas propiedades (predicados) de las entradas se preserven en el dominio del hash con una probabilidad de error negligible. Aunque existen construcciones de PPH para la distancia de Hamming, no existían soluciones eficientes para distancias métricas continuas como la distancia ℓ1 (o Manhattan), que es fundamental para medir la similitud perceptual y el impacto de los ataques adversarios.

2. Metodología Propuesta

Los autores proponen la primera familia de funciones PPH para el predicado de distancia ℓ1 asimétrica. La metodología se basa en los siguientes pilares:

• Predicado Asimétrico: En lugar de verificar simplemente si $\|x - y\|_1 \leq t$, el esquema verifica dos condiciones asimétricas:
  $$\|y \dot{-} x\|_1 < t_+ \quad \text{y} \quad \|x \dot{-} y\|_1 \leq t_-$$
  Donde $x \dot{-} y$ es un vector donde el $i$-ésimo elemento es $\max\{x_i - y_i, 0\}$. Esto permite distinguir entre imágenes donde los píxeles aumentan o disminuyen de valor, lo cual es crucial para modelar ataques adversarios.

• Codificación Polinómica:

  • Se asocia cada imagen $x$ (vector en $\mathbb{Z}_q^n$) con un polinomio $\sigma_x(z)$ definido sobre un campo finito $\mathbb{Z}_p$ (donde $p > n$ es primo):
    $$\sigma_x(z) = \prod_{i=1}^n (1 - a_i z)^{x_i}$$
    Aquí, $a$ es un vector de coeficientes aleatorios y únicos.
  • El hash de la imagen es la reducción de este polinomio módulo $z^{t+1}$.

• Evaluación mediante el Algoritmo de Euclides Extendido (EEA):

  • Para verificar la similitud entre una imagen de consulta $y$ y una imagen de base de datos $x$, el servidor utiliza el inverso del polinomio de $x$ ($\sigma_x^{-1}$) y el polinomio de $y$ ($\sigma_y$).
  • Se calcula $\tilde{\sigma}_{x,y} = \sigma_x^{-1} \cdot \sigma_y \pmod{z^{t+1}}$.
  • Se ejecuta el EEA sobre $\tilde{\sigma}_{x,y}$ y $z^{t+1}$ hasta encontrar un residuo $r_k$ con grado $\leq t_+$.
  • Si el grado del polinomio asociado al coeficiente $u_k$ cumple ciertas condiciones relacionadas con $t_-$, el predicado se evalúa como 1 (similares).

• Relación con la Distancia ℓ2: Dado que la distancia ℓ2 (Euclidiana) es común en ataques adversarios, y existe una relación de acotación $\|x-y\|_2 \leq \|x-y\|_1 \leq \sqrt{n}\|x-y\|_2$, proteger contra un umbral ℓ1 adecuado implica proteger contra ataques ℓ2.

3. Contribuciones Clave

1. Primera Construcción PPH para ℓ1: Presentan la primera familia de hashes preservadores de propiedades para el predicado de distancia ℓ1 asimétrica, superando las limitaciones de las construcciones anteriores basadas solo en distancia de Hamming.
2. Robustez contra Ataques de Evasión: El esquema garantiza que si un atacante intenta evadir la detección, debe introducir una perturbación tal que la distancia ℓ1 supere el umbral $t$. Esto fuerza al atacante a degradar significativamente la calidad visual de la imagen (aumentando el error perceptual) para lograr eludir el hash.
3. Límites Teóricos de Compresión: Demuestran cotas inferiores para la longitud del digest ($m$). Muestran que para valores pequeños de $t$, su esquema alcanza una compresión cercana al límite teórico ($m \approx t \log n$), siendo mucho más eficiente que el tamaño de la imagen original ($n \log q$).
4. Análisis de Seguridad:
   • Corrección: Garantizan corrección 1 (si son similares, el hash lo detecta) con probabilidad 1. La corrección 0 (si son diferentes, el hash no los confunde) tiene una probabilidad de error muy baja ($\approx p^{-\delta}$), que puede hacerse negligible en la práctica.
   • Inversión y Colisiones: Analizan la dificultad de recuperar la imagen original desde el hash o encontrar colisiones, demostrando que la complejidad computacional es exponencial en el tamaño de la imagen ($O(q^n)$), lo que hace inviables estos ataques.
5. Eficiencia Computacional: El algoritmo de evaluación tiene una complejidad de $O(t^2)$, lo que es altamente eficiente para umbrales $t$ pequeños.

4. Resultados Experimentales

Los autores implementaron el esquema utilizando la librería Python galois y lo probaron contra el conjunto de datos Imagenette (imágenes RGB de 224x224).

• Rendimiento:
  • Para imágenes en escala de grises de 28x28, la evaluación del predicado toma 0.0784 segundos.
  • Para imágenes RGB de 224x224, dividiendo la imagen en 1,000 bloques (paralelización), la evaluación toma 0.0128 segundos por bloque (total ~13 segundos para la imagen completa, pero altamente paralelizable).
• Eficacia contra Ataques:
  • Se probaron ataques FGSM (Fast Gradient Sign Method) y PGD (Projected Gradient Descent).
  • Para evadir la detección, los ataques debieron aumentar la Distancia Asimétrica Normalizada (NAD) por encima del umbral $t$.
  • Esto resultó en una degradación severa de la calidad de la imagen: un NAD de ~1.12 (necesario para evadir) correspondió a un LPIPS (similitud perceptual aprendida) de 0.57, lo que indica una pérdida perceptual muy significativa (la imagen se ve muy diferente a la original).
  • En contraste, los ataques que mantenían alta calidad visual (LPIPS < 0.2) no lograron evadir la detección del hash.
• Transformaciones: El esquema también resistió ataques mediante cambios de brillo y contraste, forzando a los atacantes a aplicar alteraciones extremas para eludir la detección.

5. Significado e Impacto

Este trabajo es fundamental por varias razones:

• Seguridad en Privacidad: Permite verificar la similitud de imágenes en entornos donde ni el cliente ni el servidor deben revelar las imágenes originales (privacidad), pero con una garantía matemática de corrección que el hashing perceptual tradicional no ofrece.
• Defensa Proactiva: Al vincular la detección de similitud a una métrica de distancia rigurosa (ℓ1) con corrección negligible, el esquema convierte los ataques de evasión en un compromiso inaceptable entre "esconderse" y "mantener la calidad de la imagen". Un atacante no puede simplemente añadir ruido imperceptible; debe destruir la imagen para ser invisible.
• Generalización: Abre la puerta a la aplicación de PPH en métricas de distancia continuas más allá de la distancia de Hamming, lo cual es esencial para aplicaciones de visión por computadora y biometría.

En conclusión, los autores han desarrollado un mecanismo criptográfico eficiente y robusto que cierra la brecha de seguridad en el hashing perceptual, haciendo que los ataques adversarios de evasión sean computacionalmente costosos y perceptualmente destructivos.