The combinatorial structure and value distributions of plateaued functions

Resumo Técnico: Estrutura Combinatória e Distribuições de Valor de Funções Planares (Plateaued)

1. Problema e Contexto

As funções plateaued (planares) são uma generalização de funções quadráticas e bent (curvas), desempenhando um papel fundamental na criptografia simétrica. Elas servem como blocos de construção para primitivas criptográficas devido a propriedades desejáveis como alta não-linearidade, resiliência e baixa autocorrelação aditiva. Muitas funções APN (Almost Perfect Nonlinear), essenciais para a resistência contra ataques diferenciais, são plateaued.

O problema central abordado neste trabalho é a investigação das distribuições de valor (tamanhos dos conjuntos de pré-imagens) de funções vetoriais $F: \mathbb{F}_p^n \to \mathbb{F}_p^m$. Especificamente, os autores buscam entender como a estrutura combinatória dessas funções, particularmente aquelas que são "quase balanceadas" (onde todas as pré-imagens têm o mesmo tamanho, exceto uma), se relaciona com:

• A Transformada de Walsh (espectral).
• A linearidade da função.
• A uniformidade diferencial.
• A existência de funções $d$-para-1 (onde uma imagem tem 1 pré-imagem e as outras têm $d$).

O objetivo é preencher lacunas teóricas sobre quando tais funções existem, quais são suas restrições estruturais e como suas propriedades espectrais determinam seu comportamento diferencial.

2. Metodologia

A abordagem do artigo baseia-se fortemente na análise espectral, utilizando a Transformada de Walsh como ferramenta principal, em vez de depender exclusivamente de propriedades diferenciais diretas.

• Conexão Espectral-Estrutural: Os autores estabelecem ligações diretas entre os coeficientes da Transformada de Walsh em $a=0$ e os tamanhos dos conjuntos de pré-imagens. Eles utilizam momentos da Transformada de Walsh (especificamente o segundo momento) para derivar limites rigorosos para os tamanhos das pré-imagens.
• Definição de Imbalance (Desequilíbrio): Introduzem e utilizam a métrica $N_bF$ (imbalance), definida como a soma dos quadrados dos coeficientes de Walsh não nulos em $a=0$, normalizada. Esta métrica quantifica o desvio da função em relação ao estado balanceado.
• Análise de Funções Quase Balanceadas: Definem funções "quase balanceadas" como aquelas que atingem os limites teóricos derivados para os tamanhos das pré-imagens, caracterizadas por terem apenas dois tamanhos distintos de pré-imagens não vazias.
• Uso de Teoria de Corpos e Polinômios: Para o caso de funções monomiais ($x^d$), utilizam propriedades de campos finitos, traços e campos ciclotômicos para restringir os valores possíveis de $d$ que permitem que a função seja plateaued.

3. Principais Contribuições e Resultados

A. Limites Gerais e Funções Quase Balanceadas

• Teorema 3.3: Derivam limites superiores e inferiores para o tamanho de qualquer conjunto de pré-imagem $|F^{-1}(\beta)|$ em termos do tamanho da imagem e do imbalance ($N_bF$).
• Definição 3.7: Formalizam o conceito de funções "quase balanceadas" como aquelas que atingem a igualdade nesses limites. Mostram que essas funções são as "mais próximas" de serem balanceadas, exceto por um único elemento na imagem.
• Teorema 4.1: Estabelecem uma conexão forte para funções sobrejetoras quase balanceadas: a Transformada de Walsh em $a=0$ assume valores constantes (em módulo) para todos os vetores de saída não nulos. Isso implica que tais funções devem ser plateaued com uma amplitude única.

B. Funções $d$-para-1 e Funções Planares

• Teorema 5.2: Demonstram uma restrição severa para funções vetoriais $d$-para-1 que são plateaued. Elas só podem existir se $d = p^t + 1$ (para algum $t \ge 1$) e $n$ for par.
  • A função possui componentes bent e componentes com amplitude $p^{n/2+t}$.
  • A linearidade da função é determinada por $L(F) = p^{n/2+t}$.
• Corolário 5.4: Aplicando o teorema acima a funções monomiais ($x^d$), concluem que mapeamentos induzidos por monomiais que são plateaued são ou permutações ($d=1$) ou mapeamentos $(p^t+1)$-para-1.
• Teoremas 5.5 e 5.6: Relacionam a uniformidade diferencial de funções plateaued com sua amplitude. Mostram que uma função $t$-plateaued tem uniformidade diferencial $\delta \ge p^t$, e a igualdade $\delta = p^t$ ocorre se e somente se a função for diferencialmente 2-valuada (as equações diferenciais têm 0 ou $p^t$ soluções).

C. Construções Específicas

• Teorema 5.8: Apresentam uma família de funções quase balanceadas baseadas em traços de monomiais ($Tr(x^{2r+1})$), provando que são plateaued com amplitude única e fornecendo as distribuições exatas das pré-imagens.
• Proposições 5.9 e 5.10: Analisam construções do tipo Maiorana-McFarland, mostrando como a seleção adequada de blocos de construção ($\pi$ e $\phi$) pode gerar funções balanceadas ou quase balanceadas.

D. Estrutura de Funções APN Planares

• Proposição 6.3: Estabelecem limites inferior e superior para o imbalance de funções APN plateaued. O limite inferior é atingido se e somente se a função tiver uma proporção específica de componentes bent e balanceados.
• Teorema 6.7: Usando a análise de imbalance, provam que não existem funções APN plateaued com a segunda distribuição de valor listada na literatura anterior (onde duas imagens têm 2 pré-imagens e as outras 3). Isso elimina uma classe de possibilidades para funções APN com imagem mínima.
• Teorema 6.8: Mostram que funções APN plateaued com tamanho de imagem mínimo não podem ter componentes balanceados.

4. Significado e Impacto

Este trabalho fornece uma unificação teórica robusta para o estudo de funções plateaued, conectando propriedades espectrais (Walsh), combinatórias (distribuição de valores) e criptográficas (uniformidade diferencial).

• Restrições de Existência: O resultado mais impactante é a demonstração de que funções plateaued com certas propriedades de distribuição de valor (como ser $d$-para-1) só existem para parâmetros muito específicos ($d = p^t + 1$). Isso limita drasticamente o espaço de busca para novos primitivos criptográficos baseados em monomiais.
• Filtragem de Candidatos APN: Ao provar a inexistência de certas distribuições de valor para funções APN plateaued, o artigo ajuda a refinar a busca pela famosa "Big APN problem" (existência de permutações APN em dimensões pares), descartando classes de funções que não podem satisfazer os critérios espectrais necessários.
• Ferramentas Analíticas: A introdução e aplicação sistemática do imbalance ($N_bF$) como uma ferramenta para analisar a estrutura de pré-imagens oferece um novo método poderoso para pesquisadores que estudam a segurança de cifras de bloco e funções de hash, especialmente em contextos de prova de conhecimento zero (onde monomiais são comuns).

Em suma, o artigo avança significativamente a compreensão teórica das funções plateaued, transformando problemas de existência e classificação em questões de análise espectral e combinatória rigorosa.