🔢 mathematics

Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes

Este artículo presenta un ataque de recuperación de clave en tiempo polinomial que rompe todos los conjuntos de parámetros propuestos del esquema de cifrado de Códigos de Matriz Gabidulin Mejorados (EGMC) al combinar técnicas combinatorias y algebraicas para recuperar una clave secreta equivalente, reduciendo así el nivel de seguridad de 128 bits pretendido a solo 35 bits.

Autores originales: Thai Hung Le

Publicado 2026-08-05

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Thai Hung Le

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

Imagina el internet como una ciudad gigante y bulliciosa donde todos intentan enviar mensajes secretos. Para mantener estos mensajes seguros de ojos indiscretos, usamos cerraduras digitales llamadas cifrado. Durante mucho tiempo, los científicos han estado construyendo estas cerraduras utilizando acertijos matemáticos complejos que son fáciles de crear pero increíblemente difíciles de resolver sin la llave. Recientemente, se propuso un nuevo tipo de cerradura utilizando un tipo especial de matemáticas que involucra cuadrículas de números y "rango" (que es solo una forma elegante de medir cuánta información hay realmente empaquetada dentro de la cuadrícula). Los creadores de esta nueva cerradura pensaron que habían añadido una capa de "ruido" —como la estática en una radio— para ocultar la verdadera forma de la cerradura, haciendo que parezca un caos aleatorio para cualquiera que intente romperla. Afirmaron que este nuevo diseño era tan seguro que incluso una computadora cuántica súper rápida no podría descifrarlo, y prometieron que sería diminuto y eficiente, perfecto para el futuro de la comunicación segura.

Sin embargo, al igual que un truco de magia que depende de un movimiento de manos específico, esta nueva cerradura tenía un fallo oculto. Un investigador llamado Thai Hung Le descubrió que el "ruido" no estaba ocultando la forma secreta tan bien como todos pensaban. Utilizando una mezcla ingeniosa de conjeturas y trabajo detectivesco algebraico, el investigador encontró una manera de despojarse de las capas de estática y revelar la estructura original y oculta debajo. Es como si alguien hubiera construido una casa de naipes con un plano secreto, la hubiera cubierto con niebla y luego se diera cuenta de que, si simplemente mirabas la niebla desde el ángulo correcto, el plano aún era débilmente visible. Este descubrimiento es un gran acontecimiento porque significa que las nuevas cerraduras no son tan seguras como se anunciaba, y las personas que las diseñaron deben replantearse sus planos antes de empezar a usarlas para proteger nuestros datos.

El Gran Descubrimiento del Artículo

En este artículo, Thai Hung Le presenta una nueva forma de romper los esquemas de cifrado "Enhanced Gabidulin Matrix Code" (EGMC). Estos esquemas fueron introducidos recientemente como una forma de crear claves de cifrado muy pequeñas y eficientes que pudieran sobrevivir a los ataques de futuras computadoras cuánticas. La seguridad de estos esquemas dependía de la idea de que, si tomabas una cuadrícula especial y estructurada de números y le añadías filas y columnas aleatorias (el "ruido"), se volvería imposible distinguir la diferencia entre el código real y un caos completamente aleatorio.

El autor demuestra que este supuesto es erróneo. En lugar de intentar la fuerza bruta para cada posible forma de eliminar el ruido (lo que tomaría una eternidad), el artículo introduce un ataque "híbrido". Imagina que estás tratando de encontrar un patrón específico en un mosaico gigante y desordenado. La forma antigua era adivinar la posición de cada baldosa. Este nuevo método es más inteligente: adivina la posición de solo una fila de baldosas y luego utiliza las matemáticas para deducir instantáneamente dónde deben estar el resto de las baldosas.

El artículo detalla dos formas principales de hacer esto:

Adivinar las Columnas: El atacante adivina cómo se mezclaron las columnas de la cuadrícula y luego utiliza el álgebra para resolver cómo se mezclaron las filas.
Adivinar las Filas: El atacante adivina cómo se mezclaron las filas y luego resuelve las columnas.

Una vez que el atacante descubre el mezclado, puede despojar la estructura original y oculta del ruido aleatorio. El artículo demuestra que esta estructura es un "código Gabidulin", que es un tipo de acertijo matemático que es bastante fácil de resolver una vez que conoces el patrón secreto.

Lo que el Artículo Realmente Rompe

El autor no solo encuentra una pequeña grieta; rompe toda la ventana. El artículo demuestra que este ataque funciona contra los 16 conjuntos de parámetros propuestos para los esquemas de cifrado EGMC. Esto significa que cada versión de la cerradura que se sugirió para su uso ahora se considera rota.

Para darte una idea de su eficacia, el artículo analiza un conjunto específico de números que supuestamente ofrecía una seguridad de 128 bits (un nivel estándar de seguridad). El autor muestra que su ataque reduce este nivel de seguridad a solo 35 bits. En el mundo del cifrado, eso es como pasar de una caja fuerte con una combinación de un millón de dígitos a una cerradura que un niño podría abrir en segundos.

El artículo proporciona un ejemplo concreto de este poder: utilizando su método, los investigadores pudieron recuperar la clave secreta para ese nivel de seguridad de 128 bits en menos de 10 minutos. Esto no fue solo una idea teórica; realmente construyeron un programa informático para hacerlo.

Lo que el Artículo Descarta

Es importante notar lo que este artículo no hace funcionar. El autor explica que los intentos previos de romper estos códigos dependían de métodos "combinatorios", que implican adivinar tanto el mezclado de filas como el de columnas al mismo tiempo. El artículo argumenta que esa forma antigua es demasiado lenta e ineficiente en comparación con su nuevo enfoque "híbrido".

Además, el artículo argumenta contra la idea de que simplemente hacer más grandes los parámetros (añadiendo más ruido) solucionará el problema para todos los casos. El autor muestra que para ciertos tipos de estos códigos —específicamente cuando uno de los factores de ruido (ya sea el número de filas o el número de columnas adicionales) es cero— el ataque se vuelve tan rápido que se ejecuta en "tiempo polinómico". Esto significa que, sin importar cuánto aumentes el tamaño de la cerradura en esos casos específicos, el ataque seguirá siendo lo suficientemente rápido como para romperla. La única forma de potencialmente arreglar esto, sugiere el artículo, sería cambiar el diseño fundamental para que ambos factores de ruido sean distintos de cero y lo suficientemente grandes como para detener el ataque, pero el autor advierte que esto podría hacer que las claves y los mensajes sean demasiado grandes para ser útiles.

¿Qué tan Seguros Están?

El artículo es muy seguro de sus resultados. El autor no solo conjeturó; proporcionó una prueba matemática completa de cómo funciona su ataque y lo respaldó con una implementación informática funcional. Afirma explícitamente que su ataque rompe todas las versiones propuestas del esquema. También compara sus resultados con ataques anteriores, mostrando que su método es significativamente más rápido y poderoso. El artículo concluye que los esquemas de cifrado EGMC ya no son seguros para su uso y que la comunidad de seguridad debe avanzar hacia diseños diferentes.

Resumen Técnico: Ruptura de los Esquemas de Cifrado Gabidulin de MinRank ACDGV sobre Códigos de Matriz

Planteamiento del Problema
El artículo aborda la seguridad de los Códigos de Matriz Gabidulin Mejorados (EGMC), un esquema de enmascaramiento introducido por Aragon et al. en Asiacrypt 2024. El EGMC fue diseñado para ocultar la estructura algebraica de los códigos de matriz Gabidulin, permitiendo esquemas de cifrado compactos de tipo McEliece y Niederreiter con textos cifrados pequeños (por ejemplo, 65 bytes para una seguridad de 128 bits). La seguridad del EGMC se basa en el problema de la Indistinguibilidad Decisional de EGMC: el supuesto de que un código EGMC enmascarado es computacionalmente indistinguible de un código de matriz aleatorio. El criptoanálisis previo, específicamente un ataque de kernel basado en MinRank por Porwal et al. (Eurocrypt 2026), demostró ataques de tiempo exponencial que rompieron un subconjunto de los conjuntos de parámetros propuestos, pero dejaron otros seguros. El autor investiga si la construcción EGMC retiene suficiente estructura oculta como para ser rota de manera más eficiente.

Metodología
El autor propone un nuevo distinguidor "híbrido" y un subsiguiente ataque de recuperación de clave que combina la adivinación combinatoria con la resolución algebraica. A diferencia de los distinguidores previos que realizan una búsqueda exhaustiva de ambas matrices de compresión de filas y columnas, este ataque adivina solo una matriz de compresión y resuelve la otra mediante técnicas algebraicas.

El ataque opera en dos direcciones principales:

Adivinar- $V$ -resolver- $U$ : El atacante adivina una matriz de compresión de columnas $V$ y resuelve algebraicamente una matriz de compresión de filas $U$ .
Adivinar- $U$ -resolver- $V$ : El atacante adivina una matriz de compresión de filas $U$ y resuelve una matriz de compresión de columnas $V$ .

Modelado Algebraico y Resolución
Una vez que se adivina una matriz de compresión válida, el código público se comprime en un subespacio equivalente a un código Gabidulin corto (específicamente un código $[k+1, k]$ ). El autor modela la condición de que este código comprimido debe ser un hiperplano $F_{q^m}$ anulado por un vector específico. Esto conduce a un sistema de ecuaciones bilineales que, tras su linealización, produce un sistema lineal homogéneo sobre el cuerpo de extensión $F_{q^m}$ .

El núcleo del ataque consiste en encontrar una solución de rango 1 dentro del kernel de este sistema lineal. El autor observa que el kernel admite una base con entradas en el cuerpo base $F_q$ . Consecuentemente, el problema se reduce a encontrar una combinación lineal de estas matrices base que resulte en una matriz de rango 1. Esto se formula como un sistema de ecuaciones cuadráticas (menores de $2 \times 2$ que se anulan).

Para resolver este sistema cuadrático de manera eficiente, el autor emplea el método del autovalor (método del autovalor de Stickelberger) para sistemas polinómicos de dimensión cero. Aprovechan la estabilidad de Frobenius del kernel para realizar los cálculos sobre el cuerpo más pequeño $F_q$ en lugar de $F_{q^m}$ , reduciendo significativamente la complejidad. Una conjetura clave (Conjetura 1) postula que el álgebra cociente del ideal generado por los menores tiene una dimensión igual a $m$ , lo que asegura que el sistema es de dimensión cero y resoluble mediante autovalores.

Contribuciones Clave

Distinguidor Híbrido: El artículo introduce un distinguidor que evita el costo de búsqueda exhaustiva de los métodos anteriores al resolver una de las matrices de compresión algebraicamente.
Recuperación de Clave en Tiempo Polinomial: El autor demuestra que si cualquiera de los factores de anexión $\ell_1$ o $\ell_2$ es cero, el ataque se convierte en un proceso de tiempo polinomial. Esto se debe a que el factor de adivinación exponencial desaparece, dejando solo el paso de resolución algebraica, que recupera la matriz de compresión oculta eficientemente.
Extensión de Código: Tras recuperar un código Gabidulin amputado (corto), el autor proporciona un algoritmo de tiempo polinomial para extender este código de vuelta a un código Gabidulin secreto de longitud completa, explotando la estructura $q$ -Frobenius de los códigos Gabidulin.
Descifrado Universal: La clave secreta equivalente recuperada (trampa) permite el descifrado de los textos cifrados tanto de EGMC-McEliece como de EGMC-Niederreiter.

Resultos
El ataque rompe los 16 conjuntos de parámetros propuestos para los esquemas de cifrado EGMC-Niederreiter.

Reducción de Seguridad: Para el conjunto de parámetros que apunta a 128 bits de seguridad con parámetros $(2, 17, 37, 4, 0)$ , el ataque reduce el nivel de seguridad de un alegado 186 bits a aproximadamente 35 bits.
Eficiencia: En la implementación del autor, la clave secreta equivalente para el conjunto de parámetros de 128 bits se recupera en menos de 10 minutos.
Comparación: El ataque supera a los mejores ataques previos (combinatorios y basados en MinRank) por márgenes amplios, como se muestra en la Tabla 1 del artículo.

Significancia y Reclamaciones
El artículo afirma que la construcción EGMC, tal como se propone, no logra proporcionar seguridad post-cuántica para las familias específicas de parámetros donde $\ell_1 = 0$ o $\ell_2 = 0$ . El autor argumenta que simplemente aumentar los parámetros sin cambiar la construcción de enmascaramiento no restaura la seguridad para estas familias, ya que el paso de resolución algebraica sigue siendo de tiempo polinomial.

El autor señala que una posible reparación requeriría mantener tanto $\ell_1$ como $\ell_2$ no nulos y suficientemente grandes para asegurar que el mínimo de las dos direcciones de ataque exceda el nivel de seguridad objetivo. Sin embargo, advierte que aumentar estos parámetros incrementa directamente los tamaños de la clave pública y del texto cifrado, y queda por investigar si tal reparación seguiría siendo competitiva con otros esquemas basados en códigos. El artículo concluye que los parámetros actuales de EGMC son inseguros y que el ataque propuesto proporciona tanto un distinguidor como un mecanismo completo de recuperación de clave.

El Gran Descubrimiento del Artículo

Lo que el Artículo Realmente Rompe

Lo que el Artículo Descarta

¿Qué tan Seguros Están?

Más como este