Resumen Técnico: Criptoanálisis de Códigos de Corrección de Errores Pseudialeatorios Basados en LDPC

Planteamiento del Problema

Los Códigos de Corrección de Errores Pseudialeatorios (PRC, por sus siglas en inglés), introducidos en CRYPTO 2024, representan una nueva primitiva criptográfica diseñada para permitir la marca de agua indetectable para Modelos Generativos de Lenguaje (LLM) y Modelos Generativos de Imágenes (GIM). La principal instanciación de los PRC, conocida como LDPC-PRC, se basa en códigos de comprobación de paridad de baja densidad (LDPC) y afirma su seguridad basándose en la dificultad de los problemas de Aprendizaje de Paridad con Ruido (LPN) y de XOR plantado.

A pesar de las sólidas garantías asintóticas teóricas, la seguridad concreta de LDPC-PRC bajo configuraciones de parámetros prácticas sigue sin explorarse. La literatura existente sugiere que los PRC pueden ser vulnerables a ataques de distinción de tiempo cuasi-polinomial, pero no se ha realizado un análisis riguroso para cuantificar estas vulnerabilidades en escenarios de despliegue del mundo real. Esta brecha deja la indetectabilidad y la robustez de los esquemas de marca de agua basados en PRC sin verificar frente a adversarios prácticos.

Metodología

Este trabajo presenta el primer criptoanálisis concreto de LDPC-PRC, centrándose en dos esquemas de marca de agua específicos: $\Pi_{LLM}$ (para la generación de texto) y $\Pi_{GIM}$ (para la generación de imágenes). Los autores proponen tres ataques novedosos que apuntan a la indetectabilidad y robustez del esquema, analizando su complejidad bajo configuraciones de parámetros realistas derivadas de modelos de vanguardia (DeepSeek y Stable Diffusion).

1. Ataques Criptográficos Novedosos

Los autores diseñan tres ataques con objetivos variables:

• Ataque-I (Recuperación Parcial de la Clave Secreta): Este ataque apunta a la propiedad de indetectabilidad. Al adaptar algoritmos de Decodificación de Conjunto de Información (ISD) utilizando un enfoque de Búsqueda en el Medio (MITM), el adversario recupera un subconjunto de los vectores de fila de la clave secreta a partir de la clave pública. Estos vectores recuperados permiten al adversario distinguir entre palabras de código codificadas por PRC y vectores aleatorios con una probabilidad abrumadora, rompiendo efectivamente la indetectabilidad.
• Ataque-II (Distinguidor de Claves Débiles): Este ataque explota una vulnerabilidad en el procedimiento de generación de claves ($KeyGen$). Los autores observan que, en las implementaciones actuales, la matriz de la clave pública $G$ puede contener filas idénticas con una probabilidad no despreciable (una "clave débil"). Un adversario puede detectar estas no uniformidades estadísticas para distinguir el contenido con marca de agua del ruido aleatorio en tiempo lineal, evitando la necesidad de una recuperación de clave compleja.
• Ataque-III (Ataque de Superposición de Ruido): Este ataque apunta a la propiedad de robustez. Mediante la recuperación del vector de ruido de Bernoulli original $e$ a través de la Decodificación de Síndrome, un adversario construye un vector de superposición malicioso $e'$. Este vector está diseñado de tal manera que, al sumarse a la palabra de código, el peso total del ruido excede el umbral de corrección del decodificador, causando un fallo de decodificación (eliminación de la marca de agua). Crucialmente, este ataque explota la brecha entre los límites teóricos de ruido y las tasas de ruido concretas más bajas observadas en implementaciones prácticas.

2. Análisis de Complejidad Concreta

Los autores analizan la complejidad de tiempo y de datos de estos ataques utilizando conjuntos de parámetros específicos para $\Pi_{LLM}$ y $\Pi_{GIM}$. Derivan límites teóricos (Teoremas 1–3) y los validan contra parámetros concretos, calculando los niveles de seguridad de bits (por ejemplo, $2^{46}$, $2^{60}$) en lugar de depender únicamente de la notación asintótica.

3. Evaluación en el Mundo Real

Para validar las amenazas prácticas, los autores implementaron $\Pi_{LLM}$ y $\Pi_{GIM}$ en DeepSeek (LLM) y Stable Diffusion (GIM). Evaluaron las tasas de éxito de los ataques y el impacto en la calidad del contenido. Notablemente, encontraron que para $\Pi_{LLM}$, lograr marcas de agua detectables requiere una alta entropía de tokens, lo que degrada severamente la legibilidad del texto, haciendo que el esquema sea impráctico para la generación de texto de alta calidad.

Contribuciones Clave y Resultados

1. Rompiendo la Indetectabilidad

• Ataque-I: Demostró que la recuperación parcial de la clave secreta es factible. Para $\Pi_{GIM}$, el nivel de seguridad permanece por debajo de 46 bits en todas las elecciones de parámetros. Para $\Pi_{LLM}$, el ataque tiene éxito con una probabilidad abrumadora.
• Ataque-II: Reveló que las claves débiles ocurren con casi un 100% de probabilidad para parámetros específicos (por ejemplo, $t=3, 4$) en ambos esquemas, LLM y GIM. Esto permite ataques de distinción en tiempo polinomial, socavando completamente la indetectabilidad en estos regímenes.

2. Rompiendo la Robustez

• Ataque-III: Probó que el nivel de seguridad de $\Pi_{LLM}$ no puede exceder los 75 bits para $n \le 2^{17}$ bajo ataques de superposición de ruido. Para $\Pi_{GIM}$, el nivel de seguridad concreta es inferior a 60 bits debido a la baja tasa de ruido concreta ($\eta \ll \rho$).
• Validación Experimental: En Stable Diffusion, los autores lograron tasas de éxito de eliminación de la marca de agua del 67% al 96% dependiendo del límite de perturbación ($\delta$), demostrando que la robustez se ve fácilmente comprometida.

3. Limitaciones Prácticas de $\Pi_{LLM}$

La evaluación en DeepSeek reveló un compromiso fundamental: para satisfacer los límites de corrección de errores de LDPC-PRC, el LLM debe generar tokens de alta entropía (baja confianza). Esto resulta en un texto que es o bien indetectable (baja entropía) o bien ilegible (alta entropía). En consecuencia, los autores concluyen que $\Pi_{LLM}$ es impráctico para la marca de agua de texto de alta calidad en el mundo real.

4. Defensas Propuestas

El artículo propone tres estrategias de mitigación:

• Recomendaciones de Parámetros: Aumentar la longitud del código $n$ y el peso de la fila $t$ puede elevar la complejidad del ataque. Sin embargo, lograr una seguridad de 128 bits requiere $n > 2^{24}$, lo cual excede la longitud máxima de salida de los LLM de vanguardia actuales ($2^{15}$).
• Generación de Claves Revisada: Se propone un algoritmo $KeyGen$ modificado (Algoritmo 2) que utiliza eliminación Gaussiana para eliminar la probabilidad de generar claves débiles, mitigando el Ataque-II.
• Ajustes de Implementación: Para los GIM, se sugiere aumentar el peso del vector de ruido añadido para cerrar la brecha entre las tasas de ruido teóricas y concretas, aumentando así la complejidad del Ataque-III.

Significancia y Reivindicaciones

El artículo afirma proporcionar la primera evaluación de seguridad sistemática de los PRC, cerrando la brecha entre la teoría asintótica y el despliegue práctico. Los autores aseveran que:

1. Las Garantías de Seguridad son Socavadas: La seguridad reclamada de LDPC-PRC es insuficiente en todos los regímenes prácticamente factibles. Los ataques pueden detectar marcas de agua con una probabilidad abrumadora a costos significativamente menores que 128 bits.
2. Imposibilidad Práctica para LLM: Debido a las restricciones inherentes de los modelos generativos grandes (específicamente la longitud de salida y la entropía de los tokens), lograr una seguridad de 128 bits para la marca de agua de LLM mediante LDPC-PRC es actualmente impráctico.
3. Necesidad de una Evaluación Rigurosa: El trabajo destaca que los supuestos de dureza teórica (LPN/XOR plantado) no se traducen automáticamente en seguridad concreta cuando se consideran detalles de implementación específicos (como las heurísticas de generación de claves y las tasas de ruido).

Los autores concluyen que, si bien la marca de agua de imágenes basada en PRC aún puede admitir instancias prácticas con una calidad aceptable, el estado actual de los PRC para LLM requiere una reevaluación significativa de los parámetros y las estrategias de implementación antes de su despliegue generalizado.