Improved Pseudorandom Codes from Permuted Puzzles

Este artículo introduce una nueva construcción de códigos pseudialeatorios basada en la conjetura de los códigos permutados que logra simultáneamente seguridad subexponencial, robustez contra ediciones de peor caso en un alfabeto binario y resistencia ante adversarios que poseen la clave de detección, superando así las limitaciones críticas de los esquemas de marcas de agua previos.

Lo esencial

Imagina que eres un autor famoso escribiendo una novela. Quieres demostrar que un párrafo específico fue escrito por ti y no por un imitador o una IA, pero no quieres cambiar la historia ni hacer que parezca extraña. Necesitas una forma de ocultar una "firma" secreta dentro del texto que solo tú puedas encontrar, incluso si alguien intenta editar, eliminar o desordenar las palabras.

Este documento trata sobre la construcción de una versión mucho mejor de ese sistema de firma secreta, llamado Código Pseudialeatorio (PRC). Piensa en un PRC como una máquina de cifrado mágica que convierte un mensaje secreto en una larga cadena de galimatías. Si tienes la clave, puedes convertir el galimatías de nuevo en el mensaje, incluso si alguien lo ha alterado.

Aquí está el desglose de los logros del documento utilizando analogías simples:

1. El Problema: Las firmas antiguas eran demasiado fáciles de romper

Anteriormente, los investigadores construyeron estos sistemas de firma, pero tenían tres grandes fallos:

• El fallo "Cuasipolinomial": Imagina una cerradura que a una computadora le toma un millón de años romper. Eso es bueno, ¿verdad? Pero estas cerraduras antiguas podían romperse en un tiempo "cuasipolinomial"; piensa en una cerradura que a una computadora le toma unos pocos días en lugar de un millón de años. No era lo suficientemente segura para el largo plazo.
• El fallo del "Alfabeto": Los sistemas antiguos funcionaban bien si podías cambiar el alfabeto entero (como cambiar cada 'A' por una 'Z'). Pero el texto real (como el inglés) tiene un alfabeto pequeño y fijo (26 letras). Los sistemas antiguos no podían manejar el hecho de cambiar solo algunas letras o eliminar una palabra sin que la firma se rompiera.
• El fallo de la "Clave": Si un hacker conocía tu clave secreta, podía encontrar fácilmente cambios diminutos para eliminar tu firma. Los sistemas antiguos asumían que el hacker estaba con los ojos vendados; no funcionaban si el hacker tenía puestos sus lentes.

2. La Solución: El "Rompecabezas Permutado"

Los autores crearon un nuevo sistema basado en un concepto que llaman la "Conjetura de los Códigos Permutados".

Imagina que tienes un mosaico hermoso y complejo (el código).

1. Barajar las piezas: Tomas el mosaico y barajas aleatoriamente las posiciones de las piezas (Permutación de Índices).
2. Pintar las piezas: Tomas un pincel y repintas aleatoriamente el color de cada pieza (Permutación de Alfabeto).
3. Esparcir polvo: Esparces algo de polvo aleatorio sobre todo el conjunto (Ruido).

Los autores afirman que si realizas estos tres pasos, el resultado se ve exactamente como una pila de polvo aleatorio y sin sentido. Para cualquiera que no tenga la clave, es imposible distinguir la diferencia entre el "mosaico barajado" y el "polvo aleatorio". Esto hace que la firma sea indetectable (no arruina la calidad del texto).

3. Los Tres Grandes Triunfos

El documento afirma resolver los tres problemas mencionados anteriormente simultáneamente:

• Seguridad Súper Fuerte: Afirman que su nueva cerradura es tan fuerte que incluso una supercomputadora funcionando durante mucho tiempo (tiempo subexponencial) no podría distinguir la diferencia entre su mosaico barajado y el polvo aleatorio.
• Robusto a las Ediciones (El problema de la "Edición"): Este es el mayor avance. Su sistema puede sobrevivir a las ediciones. Si un hacker elimina una palabra, añade un error tipográfico o cambia el orden de una oración, el sistema aún puede encontrar la firma.
  • Analogía: Imagina un mensaje escrito en una larga tira de papel. Si alguien corta algunas palabras, pega otras nuevas o cambia el orden, el sistema antiguo fallaría. El nuevo sistema es como un rompecabezas que aún puede resolverse incluso si las piezas están ligeramente dañadas o movidas.
• Robusto ante el Hacker que "Conoce la Clave": Su sistema funciona incluso si el hacker conoce la clave secreta.
  • Analogía: Normalmente, si un ladrón conoce la combinación de tu caja fuerte, puede abrirla y extraer su contenido. Los autores construyeron una caja fuerte donde, incluso si el ladrón conoce la combinación, no puede extraer el objeto oculto sin destruir la propia caja fuerte. Esto permite que cualquiera pueda verificar la marca de agua, no solo una parte de confianza, sin romper el sistema.

4. Cómo lo hicieron (El truco del "Plegado")

Para que esto funcione para el texto real (que tiene baja "entropía" o aleatoriedad por palabra), utilizaron un tipo especial de código matemático llamado códigos Reed-Solomon Plegados (Folded Reed-Solomon codes).

• Analogía: Imagina que estás tratando de enviar un mensaje secreto, pero solo puedes enviar ráfagas cortas y entrecortadas de datos. La forma antigua era enviar una letra a la vez. La nueva forma es "plegar" el mensaje. En lugar de enviar "A, B, C", envías un solo bloque que representa "A, B y C" todo a la vez. Esto permite al sistema empaquetar más información en el texto sin necesidad de que el texto sea altamente aleatorio o caótico.

5. El "Truco" (La Suposición)

Los autores admiten que están haciendo una gran suposición. Apuestan a que el "Rompecabezas Permutado" (el mosaico barajado) es verdaderamente imposible de distinguir del polvo aleatorio.

• No han probado que esto sea matemáticamente imposible de romper (nadie ha probado eso para este tipo específico de rompecabezas todavía).
• Sin embargo, demostraron que:
  1. Está implícito en otra suposición famosa y muy estudiada en criptografía (Rompecabezas Permutados).
  2. Intentaron romperlo con muchos tipos diferentes de ataques (como intentar encontrar patrones en el polvo) y fallaron.
  3. Demostraron que si dejas fuera cualquiera de los tres pasos (barajar, repintar o esparcir polvo), el sistema se vuelve fácil de romper. Esto sugiere que los tres pasos son necesarios y que el sistema es robusto.

Resumen

Este documento introduce una forma súper segura de marcar con agua (watermarking) el texto generado por IA. Afirma ser el primer sistema que:

1. Es casi imposible de detectar (parece texto normal).
2. Sobrevive a ediciones pesadas (errores tipográficos, eliminaciones, reescrituras).
3. Funciona incluso si el atacante conoce la clave secreta.

Lo logran convirtiendo el texto en un "rompecabezas barajado" que depende de una nueva suposición matemática, la cual argumentan que es muy probable que sea cierta basándose en pruebas extensas y conexiones con otras teorías matemáticas establecidas.

Resumen técnico

Resumen Técnico: Códigos Pseudialeatorios Mejorados a partir de Puzles Permutados

Planteamiento del Problema

La proliferación de contenido generado por IA requiere esquemas de marcas de agua robustos para identificar la procedencia. Un trabajo reciente estableció que los Códigos Pseudialeatorios (PRC, por sus siglas en inglés) son equivalentes a esquemas de marcas de agua con fuertes garantías de robustez y calidad. Un PRC es un esquema de cifrado de clave secreta donde los textos cifrados son computacionalmente indistinguibles de una distribución uniforme (asegurando la indetectabilidad/calidad) y el algoritmo de decodificación tolera una alta tasa de errores (asegurando la robustez).

Sin embargo, las construcciones de PRC existentes sufren tres limitaciones críticas:

1. Seguridad Débil: Todas las construcciones previas son vulnerables a ataques de distinción de tiempo cuasipolinomial. Dependen de ocultar estructuras $(\log n)$-dispersas, lo que permite ataques de búsqueda por fuerza bruta.
2. Robustez de Alfabeto Limitada: Aunque algunas construcciones manejan errores de edición, requieren un alfabeto de tamaño polinomial. El texto realista (por ejemplo, de Modelos de Lenguaje Extensos) tiene baja entropía (aprox. 1 bit por palabra), lo que requiere un PRC robusto a ediciones sobre un alfabeto de tamaño constante (idealmente binario).
3. Modelos Adversariales Débiles: Trabajos previos asumen que los adversarios están computacionalmente limitados o carecen de la clave de detección. No estaba claro si los PRC podrían seguir siendo robustos contra adversarios computacionalmente ilimitados que poseen la clave de detección (robustez fuertemente adaptativa).

La cuestión abierta central era si una única construcción podría lograr seguridad subexponencial, robustez de edición sobre un alfabeto binario y robustez contra adversarios que poseen la clave simultáneamente.

Metodología

1. La Conjetura de los Códigos Permutados

Los autores introducen un nuevo supuesto de dureza computacional, la Conjetura de los Códigos Permutados. Esta conjetura postula que una distribución de palabras de código "reordenadas" y con ruido es computacionalmente indistinguible de una distribución uniforme.

La distribución $D_{n,\Sigma,C,\eta,T}$ se genera de la siguiente manera:

1. Se muestrea una permutación de índices aleatoria $\sigma \in S_n$ y permutaciones de alfabeto $\pi_1, \dots, \pi_n \in S_\Sigma$.
2. Se muestrean $T$ palabras de código $c_1, \dots, c_T$ uniformemente de un código lineal $C \subseteq \Sigma^n$.
3. Para cada palabra de código, se permutan los índices mediante $\sigma$ y los símbolos en cada posición mediante $\pi_j$, produciendo $\hat{c}$.
4. Se aplica un canal de sustitución con una tasa de ruido $\eta$ a $\hat{c}$.

Idea Clave: Los autores demuestran que esta conjetura es implicada por la Conjetura de los Puzles Permutados (utilizada previamente para la Recuperación de Información Privada doblemente eficiente). Proporcionan evidencia estadística de que, para alfabetos de tamaño constante y códigos con alta distancia dual, un número logarítmico de muestras son estadísticamente uniformes. Además, demuestran que los tres componentes (permutación de índices, permutación de alfabeto y ruido) son necesarios; omitir la permutación del alfabeto (como en una versión "de juguete") hace que los códigos Reed-Solomon sean distinguibles mediante ataques de polinomios de bajo grado.

2. Construcción de PRCs Robustos a la Edición

Para lograr la robustez de edición sobre un alfabeto binario, los autores construyen un PRC basado en códigos Reed-Solomon Plegados (FRS).

• Codificación: La clave secreta consiste en las permutaciones y un one-time pad. Para codificar, se toma una palabra de código aleatoria del código subyacente, se permuta, se le añade ruido y luego se selecciona un subconjunto de símbolos. Crucialmente, cada símbolo seleccionado se entrega como una cadena binaria que contiene tanto el valor del símbolo como su índice.
• Decodificación: El decodificador recibe una cadena potencialmente corrompida por ediciones (inserciones/eliminaciones). Escanea todas las subcadenas de una longitud específica, intentando realizar una "fuerza bruta" de la distancia de edición para recuperar pares potenciales de $(índice, símbolo)$. Estos candidatos forman una lista para cada posición. Luego se aplica un algoritmo de recuperación de lista para el código subyacente a estas listas para recuperar la palabra de código original.
• Mecanismo de Robustez: Al incluir los índices en la salida, el decodificador puede recuperar el símbolo correcto incluso si la posición ha sido desplazada por inserciones o eliminaciones, siempre que el número de ediciones esté acotado. El uso de códigos FRS permite al sistema tolerar una fracción constante de ediciones incluso cuando el alfabeto es efectivamente binario (mediante la transformación).

3. Transformación de Marca de Agua

Utilizando el marco establecido por Christ y Gunn (CRYPTO '24), los autores transforman su PRC en un esquema de marca de agua para modelos de lenguaje autorregresivos. El esquema genera texto con marca de agua sesgando la selección de tokens hacia los bits de la palabra de código del PRC. La robustez del PRC frente a ediciones se traduce directamente en la capacidad de la marca de agua para sobrevivir a modificaciones adversariales del texto, siempre que el modelo tenga suficiente entropía por token.

Contribuciones Clave y Resultados

1. Nueva Construcción de PRC con Tres Propiedades

El artículo presenta la primera construcción de PRC que satisface simultáneamente:

• Seguridad Subexponencial Verosímil: Basada en la Conjetura de los Códigos Permutados, la cual evita las estructuras dispersas vulnerables a ataques de tiempo cuasipolinomial.
• Robustez de Edición de Alfabeto Binario: La construcción tolera una tasa constante de ediciones de peor caso (inserciones, eliminaciones, sustituciones) sobre un alfabeto binario.
• Robustez Fuertemente Adaptativa: El esquema sigue siendo robusto incluso contra adversarios que conocen la clave de detección y son computacionalmente ilimitados.

2. Garantías Teóricas

• Teorema 5.6: Bajo la Conjetura de los Códigos Permutados, existe un PRC de alfabeto binario que es fuertemente adaptativo a una tasa constante de ediciones con seguridad subexponencial.
• Teorema 5.14: Bajo una variante de la conjetura para códigos Reed-Solomon Plegados, existe una marca de agua de LLM indetectable que es robusta a una tasa constante de ediciones ($\tilde{O}(\alpha^7)$) requiriendo solo una tasa de entropía por token constante $\alpha$. Esta es la primera marca de agua de este tipo que es tanto indetectable como robusta a ediciones de peor caso bajo restricciones de entropía realistas.

3. Criptoanálisis y Evidencia

• Necesidad de la Permutación del Alfabeto: Los autores demuestran que sin las permutaciones de alfabeto, los códigos Reed-Solomon son eficientemente distinguibles de una distribución aleatoria, incluso con permutaciones de índice y ruido.
• Ataques Cuasipolinomiales en Trabajos Previos: Muestran que una amplia clase de construcciones de PRC anteriores (aquellas que dependen de estructuras dispersas plantadas o predicados tolerantes al ruido) son inherentemente vulnerables a ataques de tiempo cuasipolinomial.
• Uniformidad Estadística: Demuestran que, para alfabetos de tamaño constante, un número pequeño de palabras de código permutadas son estadísticamente indistinguibles de una distribución uniforme, proporcionando evidencia de la validez de la conjetura frente a distinguidores simples.

Significancia

El artículo afirma resolver la tensión entre las tres propiedades deseables de los PRC que anteriormente se consideraban mutuamente excluyentes o inalcanzables. Al formalizar la Conjetura de los Códigos Permutados y aprovechar los códigos Reed-Solomon Plegados, los autores proporcionan una base teórica para esquemas de marcas de agua que son:

1. Indetectables: Indistinguibles de la salida real del modelo de lenguaje.
2. Robustos: Capaces de resistir ediciones adversariales (inserciones/eliminaciones) en el texto.
3. Seguros: Resilientes contra atacantes que poseen la clave de detección, permitiendo la verificación pública sin comprometer la robustez.

El trabajo establece que lograr estas propiedades requiere ir más allá de las estructuras dispersas y abrazar la dificultad de distinguir palabras de código permutadas y con ruido de cadenas aleatorias. Aunque la seguridad depende de una nueva conjetura, los autores proporcionan una fuerte evidencia de su validez y demuestran que esto implica la existencia de marcas de agua prácticas y robustas para el texto generado por IA.