🔢 matemáticas

Constructing Complete Permutations via the D-Class of Locally Crooked Permutations

Este artículo introduce la clase D de permutaciones sobre $\mathbb{F}_{2^{n+1}}$ para caracterizar y construir permutaciones completas mediante conjugaciones locales, estableciendo sus propiedades algebraicas, límites criptográficos e inequivalencia CCZ, al tiempo que presenta algoritmos que enumeran con éxito nuevas permutaciones completas de $\delta=4$ .

Autores originales: Li Shuai

Publicado 2026-10-16

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Li Shuai

Artículo original bajo licencia CC BY 4.0 (https://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

En la arquitectura oculta de la seguridad digital moderna, existe una clase de objetos matemáticos conocidos como permutaciones completas. Estas no son meros desordenes aleatorios de números; son reordenamientos altamente estructurados donde el acto de mover un elemento a una nueva posición y el acto de moverlo a una posición que es la suma de su ubicación antigua y la nueva, resultan en ambos en un orden perfecto y no superpuesto. Este requisito dual es crucial para el diseño de cajas de sustitución, o S-boxes, que son los componentes primarios en los sistemas de cifrado que desordenan los datos para ocultar su significado. Si estos componentes son demasiado predecibles, el cifrado puede romperse; si son demasiado caóticos, se vuelven ineficientes. El desafío para los criptógrafos ha sido durante mucho tiempo encontrar el punto ideal: permutaciones que sean lo suficientemente complejas como para resistir ataques sofisticados, pero lo suficientemente estructuradas como para implementarse rápidamente.

Un estudio reciente de Li Shuai, de la Universidad de Ningxia, aborda este desafío explorando una familia específica de estas permutaciones a través de la lente de la simetría geométrica. La investigación se centra en una propiedad llamada "torcimiento local" (local crookedness), que describe cómo se comporta una permutación cuando su entrada es desplazada por una cantidad específica. El autor introduce una nueva categoría de estas funciones, definidas por un patrón específico en cómo cambian sus salidas. Al tratar estas funciones como elementos de un grupo más grande que puede ser transformado mediante el desplazamiento, la rotación o el intercambio de partes específicas de los datos, el estudio mapea un paisaje de posibilidades. El objetivo era ver si moverse dentro de este paisaje podía generar nuevas permutaciones superiores que ofrecieran una mejor protección contra el criptoanálisis diferencial, un método donde los atacantes estudian cómo pequeños cambios en la entrada afectan a la salida para deducir la clave secreta.

El núcleo del trabajo involucra una cadena de construcción que comienza con una permutación conocida y bien comportada, y aplica una serie de operaciones algebraicas precisas para crear otras nuevas. El autor define un conjunto específico de reglas, o una "clase-D", que estas permutaciones deben seguir para seguir siendo válidas. Dentro de este conjunto, el investigador demuestra que la colección de permutaciones "elevadas" (lifted)—aquellas que han sido extendidas desde un espacio más pequeño a uno más grande—posee una rigidez única. Si uno intenta cambiar una sola permutación usando solo un tipo de operación, como un simple desplazamiento o una rotación lineal, el resultado usualmente falla en seguir siendo una permutación completa válida. Sin embargo, el estudio demuestra que combinar dos operaciones diferentes en una secuencia específica rompe esta rigidez. Esta combinación permite al investigador navegar por el espacio de posibilidades, moviéndose de una permutación válida a otra sin perder las propiedades esenciales requeridas para la seguridad.

Para hacer práctico este marco teórico, el artículo desarrolla dos algoritmos distintos. El primero es una búsqueda de retroceso (backtracking) que construye una permutación completa desde cero, asegurando en cada paso que los requisitos de orden dual se cumplan. El segundo es una búsqueda local codiciosa (greedy local search) que comienza con una permutación existente e intenta mejorarla aplicando las operaciones combinadas descritas anteriormente. Este segundo algoritmo actúa como un escalador que busca una cima más alta: prueba diversas modificaciones pequeñas, pero solo acepta un cambio si este mejora estrictamente la calidad criptográfica de la permutación. La calidad se mide por dos indicadores principales: la uniformidad diferencial, que cuenta la frecuencia del peor de los casos de los patrones de salida, y la no linealidad, que mide qué tan lejos está la función de ser una ecuación lineal simple. Una uniformidad diferencial más baja y una no linealidad más alta son generalmente mejores para la seguridad.

Los investigadores probaron estos métodos en un espacio matemático específico de tamaño 32, que corresponde a un sistema de 5 bits. Partiendo de una permutación lineal simple que se sabía débil, se ejecutó el algoritmo de búsqueda codiciosa cien veces. Los experimentos produjeron varias permutaciones con una uniformidad diferencial de 4, una mejora significativa sobre el valor inicial de 32. El estudio también partió de cien permutaciones generadas aleatoriamente y aplicó el mismo proceso de búsqueda. Nuevamente, el algoritmo encontró consistentemente permutaciones con una uniformidad diferencial de 4. Los resultados no fueron solo encontrar mejores números; las nuevas permutaciones poseían "espectros" distintos, o patrones de frecuencias de salida, que eran diferentes entre sí y respecto al punto de partida. Esto demuestra que el método no solo produce variaciones del mismo objeto, sino que descubre genuinamente clases nuevas y distintas de permutaciones seguras.

Uno de los hallazgos más llamativos concierne a la relación entre estas nuevas permutaciones y una famosa clase de funciones conocidas como funciones APN (casi perfectamente no lineales). Históricamente, muchas construcciones de permutaciones seguras han dependido de partir con estas funciones APN. Sin embargo, el estudio encontró que las permutaciones generadas por este nuevo método de conjugación local, aunque tienen la misma excelente uniformidad diferencial de que de 4, son CCZ-inequivalentes a aquellas derivadas de los enfoques APN clásicos. De hecho, una permutación de referencia basada en una función APN bien conocida funcionó peor en esta prueba específica, con una uniformidad diferencial de 8. Esto sugiere que el nuevo método explora una región diferente del paisaje matemático, descubriendo permutaciones de alta calidad que antes eran inaccesibles para las técnicas de construcción estándar.

El artículo concluye proponiendo una conjetura basada en la evidencia experimental: que todo el espacio de estas permutaciones elevadas está conectado. En otras palabras, parece posible llegar a cualquier permutación válida en esta familia desde cualquier otra siguiendo un camino de estas modificaciones locales específicas. Aunque esta conectividad no ha sido demostrada matemáticamente, el hecho de que el algoritmo de búsqueda encontrara consistentemente soluciones de alta calidad desde diversos puntos de partida proporciona un sólido apoyo preliminar a la idea. El estudio también deja abierta la pregunta de si esta familia específica de permutaciones contiene funciones que sean incluso más fuertes que las encontradas, pudiendo alcanzar el límite teórico de seguridad conocido como APN. Por ahora, el trabajo proporciona un nuevo y robusto conjunto de herramientas para generar permutaciones seguras, demostrando que, al comprender las simetrías locales de estos objetos matemáticos, se pueden construir mejores defensas para el mundo digital.

Resumen Técnico: Construcción de Permutaciones Completas mediante la Clase-D de Permutaciones Localmente Torcidas

Planteamiento del Problema

El artículo aborda la construcción de Permutaciones Completas (CPs) sobre campos finitos $\mathbb{F}_{2^n}$ . Una permutación $f$ es una CP si tanto $f$ como el mapa $x \mapsto f(x) + x$ son permutaciones. Las CPs son críticas en criptografía, específicamente como bloques de construcción para cajas S en el marco de Lai–Massey y para la generación de cuadrados latinos ortogonales.

Mientras que las CPs están vinculadas a las Permutaciones Localmente Torcidas (LCPs) sobre $\mathbb{F}_{2^{n+1}}$ a través de la correspondencia de Shuai–Li, los métodos anteriores dependían de una ruta de "función torcida $\to$ LCP $\to$ CP". Este enfoque era restrictivo, ya que no permitía el movimiento libre o la generación de nuevas LCPs dentro de la propia clase. El artículo busca superar esto trabajando directamente dentro de la clase LCP para generar nuevas CPs mediante acciones de grupo internas, ampliando así el espacio de búsqueda de permutaciones criptográficamente fuertes.

Metodología

1. La Clase-D y la Invarianza

El autor introduce la clase-D, definida como el conjunto de permutaciones $f$ sobre $\mathbb{F}_{2^{n+1}}$ tales que la derivada en una dirección fija $q_1 = 2^n$ tiene una imagen igual al complemento de un hiperplano fijo $H = \{x : x_n = 0\}$ .
$D = \{f \in S_q : \text{Im } \Delta_{q_1}f = K\}$
donde $K = \mathbb{F}_{2^{n+1}} \setminus H$ .

El artículo demuestra que $D$ es cerrada bajo tres acciones de grupo específicas:

Traslación a la izquierda: $t_a \circ f$ para cualquier $a \in \mathbb{F}_q$ .
Multiplicación a la izquierda: $g \circ f$ para cualquier $g$ en el grupo lineal general que preserva $H$ ( $GL_H$ ).
Multiplicación a la derecha: $f \circ h$ para cualquier $h$ en el centralizador $C$ de la involución que intercambia $H$ y $K$ .

Además, la clase es cerrada bajo traslaciones locales $t_{a,X}$ (traslaciones restringidas a un subconjunto $X$ ) siempre que $X$ sea una unión de órbitas de un grupo diedral específico generado por la traslación y la involución conjugada.

2. Rigidez y la Cadena de Construcción

El autor define la subclase de CP elevada $D^\uparrow \subset D$ , que consiste en permutaciones en $D$ que actúan como la identidad en el complemento de $K$ .

Rigidez: El artículo demuestra que $D^\uparrow$ es "rígida" bajo cualquier operación única de las propiedades de clausura anteriores (traslación, multiplicación lineal o multiplicación por el centralizador). Una sola operación no puede mapear una CP elevada a otra CP elevada a menos que sea la identidad.
Cadena de Construcción: Para generar nuevas CPs, el autor construye una cadena que involucra un producto de operaciones:
$CP \xrightarrow{\text{elevar}} LCP \xrightarrow{\text{traslación local}} LCP' \xrightarrow{\text{corrección del centralizador}} LCP'' \xrightarrow{\text{restricción}} \text{Nueva } CP$
Esta cadena utiliza elementos del centralizador localizados ( $g_{a,X_1}$ y $g_{a,X_2}$ ) para "reparar" el defecto introducido por las traslaciones locales, asegurando que el resultado permanezca en $D^\uparrow$ .

3. Conjugaciones Locales

La construcción produce dos conjugaciones locales específicas, $f_1$ y $f_2$ , definidas sobre el campo base $\mathbb{F}_{2^n}$ :

$f_1$ : Una modificación de $f$ sobre un subconjunto $X_1 \subset H$ donde $X_1$ es invariante bajo un grupo diedral.
$f_2$ : Una modificación que involucra la inversa de $f$ sobre un subconjunto $X_2$ donde $X_2$ es invariante bajo un grupo cíclico.
El artículo proporciona condiciones necesarias y suficientes para que estos mapas modificados sigan siendo CPs.

4. Algoritmos

Se presentan dos algoritmos para implementar la teoría:

Búsqueda de Retroceso Aleatorio (Random Backtracking Search): Genera CPs aleatorias desde cero manteniendo las restricciones sobre $f(x)$ y $f(x)+x$ .
Búsqueda Local Ávida (Greedy Local Search): Aplica iterativamente las conjugaciones locales ( $f_1, f_2$ ) a una semilla CP. Solo acepta movimientos si estos mejoran estrictamente una función de calidad basada en el espectro diferencial completo (DDT) y el espectro de Walsh.

Resultados Clave

Contribuciones Teóricas

Prueba de Invarianza: Estableció que la clase-D es invariante bajo las acciones de grupo y traslaciones locales especificadas.
Teorema de Rigidez: Demostró que la subclase de CP elevada $D^\uparrow$ no puede ser generada por operaciones simples, lo que requiere la cadena de construcción compuesta.
Criterios de Inequivalencia CCZ: Derivó criterios para determinar cuándo las nuevas CPs construidas son CCZ-inequivalentes a la semilla. Esto se basa en verificar si la Tabla de Distribución Diferencial (DDT) o el multiconjunto de coeficientes absolutos de Walsh cambian.
Límites Criptográficos: Derivó límites para la uniformidad diferencial ( $\delta$ ), la no linealidad ($nl$) y el grado algebraico ( $\deg$ ) bajo modificaciones locales. Específicamente, $\delta$ cambia en un máximo de $2m$ donde $m$ es el tamaño del subconjunto modificado.

Hallazgos Experimentales

Los experimentos se realizaron en $H \cong \mathbb{F}_{2^5}$ (32 elementos):

Generación de CPs con $\delta=4$ : Partiendo de una semilla lineal ( $\delta=32$ ) y semillas aleatorias, la búsqueda ávida encontró con éxito múltiples permutaciones completas con uniformidad diferencial $\delta=4$ .
Espectros Distintos: Las CPs generadas exhibieron espectros diferenciales distintos en comparación entre sí y respecto a una CP de referencia basada en Dillon (que tenía $\delta=8$ ).
CCZ-Inequivalencia: Los distintos espectros diferenciales confirman que la construcción produce nuevas clases de CCZ-inequivalencia, no solo variantes afines de la semilla.
Evidencia de Conectividad: La convergencia repetida hacia distribuciones indicadoras similares desde diferentes semillas aleatorias proporciona evidencia preliminar de que el conjunto de CPs elevadas $D^\uparrow$ puede estar conectado bajo movimientos de conjugación local.

Significado y Reivindicaciones

El artículo afirma proporcionar un marco algebraico sistemático para generar nuevas permutaciones completas explotando la estructura interna de la clase LCP.

Más allá de las Funciones Torcidas: A diferencia de los métodos anteriores que dependen de partir de una función torcida, este enfoque permite explorar el espacio LCP para encontrar CPs.
Utilidad Criptográfica: El método produce con éxito CPs con baja uniformidad diferencial ( $\delta=4$ ), una propiedad deseable para las cajas S, que anteriormente eran más difíciles de construir mediante la correspondencia estándar de funciones torcidas.
Perspectiva Estructural: La identificación de la "rigidez" de $D^\uparrow$ y el papel específico del centralizador para "reparar" las traslaciones locales ofrece una comprensión teórica más profunda de la relación entre LCPs y CPs.
Problemas Abiertos: El autor plantea modestamente la conectividad de $D^\uparrow$ y la existencia de funciones APN dentro de esta clase como problemas abiertos, sugiriendo que, si bien los experimentos apoyan la conectividad, se requiere una prueba formal. También señala que, aunque los resultados sugieren un vínculo potencial con las permutaciones APN, no se establecieron explícitamente permutaciones APN en este trabajo.