🔢 mathematics

The combinatorial structure and value distributions of plateaued functions

Este artículo estudia las propiedades combinatorias de las funciones aplanadas, centrándose en la relación entre su transformada de Walsh, linealidad, propiedades diferenciales y distribuciones de valores, con especial énfasis en funciones "casi equilibradas" y su aplicación a funciones monomiales y APN.

Autores originales: Lukas Kölsch, Alexandr Polujan

Publicado 2026-03-26

📖 4 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Lukas Kölsch, Alexandr Polujan

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 las funciones matemáticas que usan los criptógrafos son como recetas secretas para mezclar ingredientes (datos) y crear un plato final (código cifrado). El objetivo es que, si alguien intenta adivinar la receta o separar los ingredientes, sea extremadamente difícil.

En este artículo, los autores (Lukas Kolsch y Alexandr Polujan) se centran en un tipo especial de receta llamada "función mesada" (o plateaued function en inglés).

Aquí tienes la explicación sencilla, usando analogías:

1. ¿Qué es una "función mesada"?

Imagina que tienes una montaña.

Algunas montañas son muy empinadas y caen de golpe (funciones lineales o simples).
Otras son picos muy agudos (funciones "bent" o curvas, que son ideales pero muy raras).
Las funciones mesada son como una montaña con una meseta plana en la cima. No son tan perfectas como los picos agudos, pero son muy estables y fáciles de construir.

La mayoría de las funciones que ya usamos en criptografía (como las que protegen tus contraseñas o los algoritmos de blockchain) son de este tipo de "meseta". Los autores quieren entender mejor cómo se comportan estas mesetas.

2. El problema de la "Distribución de Valores" (¿Quién se queda con qué?)

Imagina que tienes una fiesta con 100 invitados (los datos de entrada) y quieres repartirlos en 10 mesas (los resultados de salida).

Ideal (Equilibrado): Lo perfecto sería que en cada mesa se sienten exactamente 10 personas. Esto es una función "balanceada". Es lo mejor para la seguridad porque nadie puede adivinar en qué mesa está alguien.
El problema: A veces, la distribución no es perfecta. Quizás en una mesa hay 12 personas, en otra 8, y en las demás 10.
Casi Equilibrado: Los autores estudian un caso especial llamado "casi equilibrado". Imagina que en 9 mesas hay exactamente 10 personas, pero en una sola mesa hay un número diferente (digamos, 12). Es la distribución más cercana a la perfección posible sin ser perfecta.

El artículo investiga: ¿Qué tan desordenada puede estar la fiesta antes de que la receta sea insegura?

3. La "Brújula Mágica" (Transformada de Walsh)

Para medir el desorden de la fiesta sin contar a cada persona uno por uno, los matemáticos usan una herramienta llamada Transformada de Walsh.

Piensa en ella como una brújula mágica o un escáner de rayos X.
En lugar de mirar a las personas directamente, la brújula te dice si la fiesta está "equilibrada" o si hay "turbulencias" (desequilibrios) basándose en patrones ocultos.
Los autores descubrieron que, si miras la lectura de esta brújula en un punto específico, puedes predecir exactamente cuántas personas hay en cada mesa, incluso si no las cuentas.

4. Las "Reglas de Oro" que descubrieron

Los autores encontraron varias reglas sorprendentes sobre estas funciones:

La regla del "1 a 1" (Monomios): Si la función es un tipo especial llamada "monomio" (como una receta muy simple donde solo elevas un número a una potencia), la fiesta casi nunca está desordenada. O bien es perfecta (todos tienen una mesa), o bien sigue una regla muy estricta donde las mesas tienen tamaños específicos (como $p^t + 1$ ). No pueden ser "cualquier cosa".
El límite de la seguridad: Descubrieron que si una función es "mesada" y también es muy segura contra ciertos ataques (llamados APN), entonces no puede tener mesas vacías ni desequilibrios extraños. Tiene que seguir un patrón muy estricto.
Imposibilidad: Demostraron que ciertos tipos de fiestas "casi equilibradas" simplemente no pueden existir en el mundo de las funciones mesadas. Es como intentar construir un puente de gelatina que soporte un camión; la física (en este caso, las matemáticas) no lo permite.

5. ¿Por qué nos importa esto?

En el mundo real, esto es crucial para:

Criptomonedas y Blockchain: Funciones como las de Poseidon o Rescue (usadas en pruebas de conocimiento cero) dependen de estas recetas. Si la distribución de valores es mala, un hacker podría encontrar un atajo para romper la seguridad.
Diseño de Cifrado: Ayuda a los ingenieros a elegir las mejores "mesetas" para sus algoritmos, asegurando que la fiesta esté lo más equilibrada posible sin tener que usar recetas imposibles de construir.

En resumen

Este artículo es como un manual de ingeniería para arquitectos de criptografía. Los autores dicen: "Si quieres construir una función segura que sea una 'meseta', aquí tienes las reglas exactas de cómo debe distribuirse la gente en las mesas. Si intentas hacer algo fuera de estas reglas, la función no funcionará o será insegura".

Han creado nuevas herramientas (la brújula de Walsh aplicada a desequilibrios) para que los futuros criptógrafos puedan diseñar sistemas más robustos y entender por qué ciertas recetas funcionan y otras no.

1. Problema y Contexto

Las funciones de meseta (plateaued functions) son una generalización de las funciones cuadráticas y las funciones bent (curvadas). Estas funciones son fundamentales en criptografía debido a sus propiedades deseables, como alta no linealidad, resiliencia y baja autocorrelación aditiva. Muchas primitivas criptográficas, incluidas la mayoría de las funciones APN (Almost Perfect Nonlinear) conocidas y las funciones cuadráticas, pertenecen a esta clase.

El problema central abordado en el artículo es la comprensión profunda de la distribución de valores (tamaños de los conjuntos de imagen y preimagen) de estas funciones vectoriales $F: \mathbb{F}_p^n \to \mathbb{F}_p^m$ . Específicamente, los autores buscan:

Determinar cómo la estructura de la transformada de Walsh y la linealidad de una función de meseta influyen en su distribución de valores.
Investigar el caso especial de funciones "casi balanceadas" (almost balanced), donde todos los conjuntos de preimagen tienen el mismo tamaño, excepto uno.
Establecer condiciones de existencia y no existencia para funciones de meseta con distribuciones de valores específicas (como funciones $d$ -a-1 y monomios).
Analizar la relación entre la distribución de valores y las propiedades diferenciales (uniformidad diferencial) en funciones APN de meseta.

2. Metodología

Los autores desarrollan un marco teórico que conecta tres conceptos clave:

Transformada de Walsh: Utilizan la transformada de Walsh en el punto $a=0$ ( $W_F(b, 0)$ ) como la herramienta principal. Dado que las funciones de meseta tienen un número limitado de coeficientes de Walsh distintos (valores en $\{0, \pm p^{(n+t)/2}\}$ ), esto permite derivar restricciones fuertes sobre las distribuciones de valores.
Imbalance ( $N_b F$ ): Introducen y utilizan el concepto de imbalance (desequilibrio), definido como la suma de los cuadrados de los coeficientes de Walsh no nulos en $a=0$ . Este valor mide la distancia de la función respecto a ser balanceada.
Desigualdades Combinatorias: Aplican la desigualdad de Cauchy-Schwarz y propiedades de los momentos de la transformada de Walsh para acotar los tamaños de los conjuntos de preimagen ( $|F^{-1}(\beta)|$ ).

El enfoque es puramente espectral y combinatorio, evitando depender exclusivamente de propiedades diferenciales directas, lo que permite obtener resultados incluso cuando la información diferencial es limitada.

3. Contribuciones Clave y Resultados Principales

A. Límites Generales y Funciones Casi Balanceadas

Teorema 3.3: Establecen límites superiores e inferiores para el tamaño de los conjuntos de preimagen en función del tamaño de la imagen y el imbalance ( $N_b F$ ).
Definición 3.7: Formalizan el concepto de funciones casi balanceadas como aquellas que alcanzan la igualdad en estos límites. Estas funciones tienen un único tamaño de preimagen diferente al resto (que son todos iguales).
Teorema 4.1: Demuestran que para una función casi balanceada y sobreyectiva, la transformada de Walsh en $a=0$ toma valores constantes (en magnitud) para todos los $b \neq 0$ . Esto implica que las funciones casi balanceadas de meseta deben tener una amplitud única.

B. Funciones $d$ -a-1 y Monomios

Teorema 5.2: Analizan funciones vectoriales $d$ $d$ -a-1 (donde hay un único preimagen de tamaño 1 y el resto de tamaño $d$ $d$ ). Demuestran que una función de este tipo solo puede ser de meseta si $d$ $d$ toma valores muy específicos: $d = p^t + 1$ $d = p^{t} + 1$ (donde $t \ge 1$ $t \geq 1$ y $t | n/2$ $t ∣ n /2$ ).
- Esto implica que las funciones de meseta $d$ -a-1 tienen componentes bent y componentes con amplitud $p^{n/2+t}$ .
Corolario 5.4: Aplican este resultado a monomios $F(x) = x^d$ . Concluyen que los monomios de meseta inducen o bien permutaciones ( $d=1$ ) o bien funciones $(p^t+1)$ -a-1.
Teoremas 5.5 y 5.6: Establecen que la uniformidad diferencial $\delta$ de una función de meseta $t$ -meseta es al menos $p^t$ . La uniformidad es exactamente $p^t$ si y solo si la función es diferencialmente de dos valores (las ecuaciones diferenciales tienen 0 o $p^t$ soluciones).

C. Construcciones de Funciones Casi Balanceadas

Teorema 5.8: Proporcionan una construcción explícita de funciones de meseta sobreyectivas y casi balanceadas utilizando trazas de monomios sobre campos de característica 2.
Proposiciones 5.9 y 5.10: Muestran que ciertas construcciones de tipo Maiorana-McFarland inducen naturalmente funciones casi balanceadas, dependiendo de las propiedades de las funciones internas ( $\pi$ y $\phi$ ).

D. Estructura de Funciones APN de Meseta

Proposición 6.3: Derivan cotas para el imbalance de funciones APN de meseta. El límite inferior se alcanza si la función tiene una proporción específica de componentes bent y balanceadas.
Teorema 6.7: Utilizando las propiedades del imbalance y la paridad, demuestran que no existen funciones APN de meseta que posean la segunda distribución de valores posible para funciones APN con tamaño de imagen mínimo (la distribución con dos preimágenes de tamaño 2 y el resto de tamaño 3).
Teorema 6.8: Demuestran que las funciones APN de meseta con el tamaño de imagen mínimo no pueden tener componentes balanceadas.

4. Significado e Impacto

Este trabajo es significativo por varias razones:

Unificación Teórica: Proporciona un marco unificado que conecta la transformada de Walsh, el imbalance y la distribución de valores, extendiendo resultados previos que se centraban solo en funciones bent o APN específicas.
Restricciones de Existencia: Establece restricciones fuertes sobre qué tipos de funciones de meseta pueden existir. Por ejemplo, limita drásticamente los valores de $d$ para los cuales existen funciones de meseta $d$ -a-1, lo cual es crucial para el diseño de primitivas criptográficas basadas en monomios (como en sistemas de prueba de conocimiento cero como Poseidon).
Resolución de Problemas Abiertos: Resuelve parcialmente el problema de la existencia de ciertas distribuciones de valores para funciones APN de meseta, eliminando la posibilidad de la segunda distribución de valores mencionada en la literatura anterior.
Herramientas para Criptoanálisis: Las cotas derivadas sobre la uniformidad diferencial y la linealidad basadas en la distribución de valores ofrecen nuevas herramientas para evaluar la seguridad de primitivas criptográficas y para guiar la búsqueda de nuevas funciones APN.

En resumen, el artículo avanza significativamente la comprensión de la estructura combinatoria de las funciones de meseta, demostrando que sus propiedades espectrales imponen restricciones rigurosas sobre cómo pueden distribuirse sus valores de salida, lo cual tiene implicaciones directas para el diseño y análisis de algoritmos criptográficos seguros.