🔢 mathematics

Quadratic APN Functions in Dimension 8 via Gröbner Basis Search in a Self-Equivalence Subspace

Este artículo presenta una búsqueda computacional híbrida que combina el muestreo aleatorio y la enumeración de bases de Gröbner dentro de un subespacio de autoequivalencia específico de 40 dimensiones para descubrir 566 funciones APN cuadráticas en dimensión 8, incluyendo tres clases de equivalencia CCZ previamente desconocidas que fueron omitidas por bases de datos exhaustivas anteriores.

Autores originales: Oleksandr Kuznetsov

Publicado 2026-06-11

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Oleksandr Kuznetsov

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 que estás intentando encontrar un tipo de ganzúa increíblemente rara (llamada función APN) dentro de un almacén masivo y oscuro. Este almacón representa todas las funciones matemáticas de un cierto tamaño. El problema es que el almacén es tan enorme (contiene más posibilidades que átomos en el universo) que si simplemente empezaras a caminar al azar, es probable que nunca encontraras una sola ganzúa en toda tu vida.

Este artículo describe una nueva y astuta estrategia para encontrar estas ganzuas raras utilizando una "linterna" y un "imán" para navegar por una sección específica y más pequeña del almacén que antes se consideraba vacía.

Aquí está el desglose de su descubrimiento utilizando analogías simples:

1. El Problema: La aguja en el pajar cósmico

En el mundo de la criptografía (la ciencia de los códigos secretos), estas "ganzuas" son herramientas matemáticas especiales utilizadas para cifrar datos de modo que no puedan ser descifrados por hackers. Durante mucho tiempo, los matemáticos han intentado encontrar nuevas y mejores ganzuas para un tamaño específico de datos (8 bits).

La forma antigua: Investigadores anteriores intentaron encontrarlas construyendo un gigantesco árbol de posibilidades, revisando rama por rama. Miraron una sección específica y organizada del almacén (un "subespacio de auto-equivalencia") y concluyeron: "No hay nada aquí". Dejaron de buscar.
La realidad: Los autores de este artículo dicen: "Un momento. Esa sección no está vacía. Simplemente pasasteis los objetos por alto porque vuestro método de escalar árboles era demasiado rígido".

2. La Nueva Estrategia: La Linterna y el Imán

Los autores desarrollaron un proceso de dos pasos para encontrar estas ganzuas ocultas:

Paso 1: La Linterna (Muestreo aleatorio en una zona estructurada)
En lugar de buscar en todo el universo, se centraron en una "habitación" de 40 dimensiones, específica y organizada, dentro del almacén. Se dieron cuenta de que, aunque esta habitación es diminuta en comparación con todo el almacén, las "ganzuas" son en realidad mucho más comunes dentro de esta habitación específica que en cualquier otro lugar.
Utilizaron un mapa especial (llamado parametrización RREF) para recorrer esta habitación de forma aleatoria. Encontraron cientos de ganzuas "centrales" que estaban allí mismo, esperando ser descubiertas.
Paso 2: El Imán (La búsqueda de la Base de Gröbner)
Este es el truque de magia. Una vez que encontraron una ganzúa "central", no se detuvieron. Utilizaron una poderosa herramienta matemática llamada Base de Gröbner (piensa en ella como un superimán) para escanear el vecindario inmediato alrededor de ese centro.

Aquí está la parte sorprendente: el imán no solo encontró más ganzuas en la misma habitación. También extrajo nuevas ganzuas que estaban escondidas en las habitaciones adyacentes, fuera de la sección organizada en la que comenzaron.

Analogía: Imagina que encuentras una moneda rara en un cajón específico. Usas un imán para escanear el cajón y, de repente, el imán extrae otras tres monedas raras que estaban pegadas al fondo del cajón, a pesar de que esas monedas pertenecen técnicamente a un cajón diferente.

3. El Descubrimiento: Nuevas Clases de Tesoros

Utilizando este método, el equipo encontró 566 nuevas ganzuas. Las clasificaron en seis grupos (clases):

Dos grupos eran tipos "conocidos" (como las famosas funciones Gold). Estos actuaron como puertas de enlace (gateways). Cuando los autores usaron estos tipos conocidos como punto de partida, el "imán" extrajo los nuevos tipos desconocidos.
Cuatro grupos eran completamente nuevos. Nunca se habían visto antes.
- Un grupo (Clase A) fue encontrado directamente dentro de la habitación organizada.
- Tres grupos (Clases B, C y D) fueron encontrados fuera de la habitación, pero solo eran descubribles porque el "imán" estaba conectado a las conocidas ganzuas "puerta de enlace" dentro de la habitación.

4. La Prueba: Por qué es importante

Los autores no solo supusieron que eran nuevos. Utilizaron un sistema de "huella dactilar" (llamado invariante de la orto-derivada) para cotejar sus hallazgos con las bases de datos más grandes del mundo, que contienen millones de ganzuas conocidas.

Resultado: Sus cuatro nuevos grupos no coincidían con ninguna de las entradas existentes de millones de registros. Son genuinamente nuevos.
El mito de la "Habitación Vacía": Demostraron que los investigadores anteriores estaban equivocados sobre la habitación estando vacía. La habitación no estaba vacía; el método de búsqueda anterior simplemente no podía ver los objetos porque los miraba uno por uno, mientras que este nuevo método mira todo el vecindario a la vez.

5. La Gran Lección: El Fenómeno de la "Puerta de Enlace"

La lección más importante no es solo el hallazgo de las nuevas ganzuas, sino cómo se encontraron.
Los autores descubrieron que no puedes simplemente elegir cualquier ganzua al azar y esperar encontrar otras nuevas cerca. Tienes que empezar con un tipo muy específico y estructurado (las funciones "Gold" dentro de la habitación organizada).

La Analogía: Si intentas usar un imán en un trozo de chatarra aleatorio en el almacén, no sucede nada. Pero si usas el imán en un objeto "puerta de enlace" específico, revelas todo un mundo oculto de nuevos objetos que antes eran invisibles.

Resumen

Este artículo trata sobre encontrar tesoros matemáticos ocultos en un lugar que todos pensaban que estaba vacío. Al utilizar un mapa más inteligente para encontrar un punto de partida y un poderoso "imán" matemático para escanear los alrededores, los autores encontraron 566 nuevas herramientas criptográficas, incluyendo cuatro familias completamente nuevas que nadie había visto jamás. Demostraron que, a veces, para encontrar lo nuevo, tienes que apoyarte en los hombros de lo conocido, pero necesitas las herramientas adecuadas para ver qué se esconde justo más allá del borde.

Resumen Técnico: Funciones APN Cuadráticas en Dimensión 8 mediante la Búsqueda de Bases de Gröbner en un Subespacio de Autoequivalencia

Planteamiento del Problema
La clasificación de las funciones Casi Perfectamente No Lineales (APN) sobre $\mathbb{F}_{2^n}$ hasta la equivalencia CCZ es un problema central en criptografía, particularmente para $n=8$ . Mientras que la clasificación es completa para $n \leq 6$ , para $n=8$ sigue siendo parcial. El espacio de búsqueda para las funciones APN cuadráticas es vasto ( $2^{224}$ vectores de coeficientes posibles), lo que hace que la búsqueda aleatoria global sea infactible debido a una densidad APN estimada de $\approx 2^{-n}$ . Esfuerzos sistemáticos previos, como la búsqueda en árbol recursivo de Beierle, Brinkmann y Leander (BBL2021), exploraron subespacios algebraicos estructurados definidos por restricciones de autoequivalencia. Específicamente, BBL2021 reportó haber encontrado cero funciones APN dentro del subespacio de autoequivalencia de 40 dimensiones $V_A$ asociado con un automorfismo lineal $A$ de orden 5 (índice de clase 22). Este artículo investiga si este subespacio realmente contiene ninguna función APN o si el método de búsqueda anterior no logró localizarlas.

Metodología
Los autores proponen un flujo de trabajo computacional de dos fases que combina el muestreo aleatorio con la enumeración algebraica para explorar $V_A$ de manera más efectiva que la búsqueda previa en árbol.

Fase 1: Muestreo Aleatorio mediante Parametrización RREF
Los autores construyen una parametrización explícita de la Forma Escalonada Reducida por Filas (RREF) del subespacio de 40 dimensiones $V_A = \{F : F \circ A = A \circ F\}$ . Esto reduce el espacio de búsqueda de $2^{224}$ a $2^{40}$ . Dentro de este subespacio, la densidad empírica de funciones APN se encuentra en aproximadamente $10^{-4}$ (aproximadamente 1 función APN por cada 11,000 muestras aleatorias), lo que hace que el muestreo dirigido sea factible. Los autores realizan un muestreo aleatorio para identificar "centros APN" (funciones en $V_A$ que son APN).
Fase 2: Computación de Rebanadas mediante Base de Gröbner
Para cada centro APN encontrado en la Fase 1, los autores definen un hiperplano afín de 24 dimensiones (una "rebanada NL=4") que pasa por ese centro. Esto se logra fijando 200 coeficientes de la Forma Normal Algebraica (ANF) (específicamente aquellos correspondientes a pares con índices $p \leq 4$ ) a los valores del centro, dejando 24 coeficientes como incógnitas.
La condición APN para las 255 diferencias no nulas se codifica como un sistema de ecuaciones polinómicas sobre el anillo booleano. Los autores utilizan el sistema de álgebra computacional Magma para calcular una base de Gröbner para este sistema.
- Si el sistema es infactible, la rebanada no contiene otras funciones APN.
- Si el sistema tiene soluciones, la enumeración de la base de Gröbner encuentra todas las funciones APN dentro de esa rebanada específica de 24 dimensiones.
  Crucialmente, aunque el centro está garantizado en $V_A$ , las soluciones encontradas por el paso de la base de Gröbner no están restringidas a $V_A$ ; pueden encontrarse fuera del subespacio de autoequivalencia.
Clasificación y Verificación
Las funciones halladas se clasifican utilizando el invariante de ortoderivada $\sigma(F)$ , el cual se demuestra que es un invariante CCZ completo para funciones APN cuadráticas (por el teorema de Yoshiara y resultados de Canteaut et al.). Los autores realizan comparaciones de flujo (streaming) de estas firmas contra tres bases de datos principales: la compilación BBL2021 pre-2020, la base de datos de Beierle et al. 2025 (que contiene $\approx 3.8$ millones de funciones) y las funciones Gold clásicas.

Resultos Clave
Los autores ejecutaron el flujo de trabajo en 428 rebanadas distintas de 24 dimensiones (0.65% del total de $2^{16}$ rebanadas posibles en $V_A$ ).

Descubrimiento de Nuevas Clases: La búsqueda produjo 566 funciones APN cuadráticas únicas que pertenecen a seis clases de equivalencia CCZ.
- Cuatro Nuevas Clases (A, B, C, D): Estas 500 funciones (362 en la Clase A, 72 en B, 36 en C, 30 en D) no están presentes en la base de datos Beierle 2025, la base de datos BBL2021 pre-2020, ni en las familias Gold clásicas.
- Dos Clases Conocidas (E, F): Estas corresponden a las funciones Gold $x^3$ y $x^9$ (y sus órbitas de Frobenius), sirviendo como controles para validar el flujo de trabajo.
Hallazgos Estructurales:
- Pertenencia al Subespacio: Una prueba de pertenencia ( $F \circ A = A \circ F$ ) reveló que la Clase A, E y F residen enteramente en $V_A$ . Sin embargo, las Clases B, C y D residen enteramente fuera de $V_A$ .
- El Fenómeno de la "Puerta de Enlace" (Gateway): Las 138 funciones en las nuevas clases externas (B, C, D) se encontraron exclusivamente en rebanadas centradas en funciones Gold (Clases E y F) que residen dentro de $V_A$ . Las rebanadas centradas en funciones de la Clase A no produjeron vecinos fuera de $V_A$ .
- Fallo de Semillas Alternativas: Experimentos comparativos utilizando 532 funciones APN de la base de datos Beierle 2025 (que están fuera de $V_A$ ) como centros de rebanada resultaron en cero vecinos APN encontrados. Esto sugiere que la capacidad de "puerta de enlace" para descubrir nuevas clases mediante el rebanado de base de Gröbner es específica de las funciones dentro del subespacio de autoequivalencia, y no una propiedad genérica de todas las funciones APN.

Significancia y Reivindicaciones
El artículo reclama varias contribuciones significativas al campo de la clasificación de funciones APN cuadráticas:

Corrección de Resultados Previos: Los autores demuestran que el subespacio de autoequivalencia $V_A$ (índice de clase 22), reportado previamente por BBL2021 como carente de funciones APN, contiene en realidad al menos cuatro clases CCZ de funciones APN cuadráticas. El fallo de la búsqueda en árbol de BBL2021 se atribuye a su estrategia de poda de ramas, que pudo haber eliminado soluciones válidas en este subespacio estructurado, mientras que el enfoque de base de Gröbner realiza una enumeración completa dentro de cada rebanada.
Descubrimiento de Nuevas Funciones: El artículo proporciona una prueba rigurosa (vía el invariante de ortoderivada) de que existen cuatro nuevas clases CCZ de funciones APN cuadráticas para $n=8$ , distintas de las $\approx 3.8$ millones de funciones en la base de datos más grande conocida.
Innovación Metodológica: El trabajo introduce un mecanismo de "navegación por GB". Postula que, si bien la búsqueda global es imposible, se puede explotar subespacios estructurados con mayor densidad APN para encontrar funciones "semilla". El paso de la base de Gröbner actúa entonces como un enumerador local, capaz de salir del subespacio para encontrar nuevas clases. Los autores enfatizan que este mecanismo no es genérico; depende de la estructura algebraica específica del subespacio de autoequivalencia, como lo demuestra el fallo de las funciones no pertenecientes al subespacio para actuar como semillas productivas.
Completitud de la Ortoderivada: El trabajo refuerza la utilidad de la firma de la ortoderivada como un invariante CCZ exacto para funciones cuadráticas, permitiendo una clasificación rigurosa sin necesidad de pruebas exhaustivas por pares.

Los autores concluyen que su enfoque ofrece un programa sistemático para extender la clasificación de las funciones APN cuadráticas mediante la exploración de otros índices de clase de BBL2021 y la utilización de la técnica de rebanado por base de Gröbner para navegar el panorama de las APN.