Permutation Polynomials Under Multiplicative-Additive Perturbations: Characterization via Difference Distribution Tables

Título: Polinômios de Permutação sob Perturbações Multiplicativo-Aditivas: Caracterização via Tabelas de Distribuição de Diferenças

1. Problema e Contexto

O artigo investiga uma classe específica de polinômios de permutação $F$ sobre corpos finitos $\mathbb{F}_{p^n}$. O foco central é a propriedade de Perfeita Não-Linearidade $c$ (Perfect c-Nonlinearity - PcN).

• Definição do Problema: Uma função $F$ é dita PcN se, para todo deslocamento não nulo $a \in \mathbb{F}_{p^n}^*$ e para um parâmetro fixo $c \in \mathbb{F}_{p^n} \setminus \{0, 1\}$, a derivada generalizada (ou derivada $c$-externa) definida por:
  $$D_{c,a}F(x) = F(x + a) - cF(x)$$
  seja ela própria uma permutação de $\mathbb{F}_{p^n}$.
• Motivação Criptográfica: Esta propriedade representa a resistência ótima contra ataques de criptanálise diferencial $c$. A relevância prática foi destacada recentemente por ataques bem-sucedidos ao cifra de bloco Kuznyechik (padrão GOST R 34.12-2015), onde exploraram-se vulnerabilidades relacionadas a essas derivadas generalizadas.
• Desafio Atual: Verificar se uma função é PcN tradicionalmente exige a construção de uma Tabela de Distribuição de Diferenças $c$ (cDDT), o que tem complexidade computacional de $O(p^{3n})$, tornando a análise inviável para dimensões maiores.

2. Metodologia

Os autores desenvolveram uma nova abordagem teórica e computacional baseada na Tabela de Distribuição de Diferenças Clássica (DDT), que é mais eficiente de calcular e armazenar.

• Abordagem Principal: Em vez de calcular a cDDT completa para cada $c$, os autores estabelecem uma equivalência direta entre a propriedade PcN e condições específicas sobre a DDT clássica ($\Delta_F$).
• Ferramentas Matemáticas:
  • Análise de propriedades de homogeneidade em monômios.
  • Teoria de subespaços vetoriais sobre $\mathbb{F}_p$.
  • Espectro de Walsh-Hadamard e limites de não-linearidade.
  • Equivalência afim e automorfismos de Frobenius.

3. Principais Contribuições e Resultados

A. Caracterização Eficiente via DDT (Seção 3)

O resultado mais significativo é um teorema que permite verificar a propriedade PcN usando apenas a DDT clássica.

• Teorema 3.2: Um polinômio de permutação $F$ é PcN se e somente se, para todos $a, b \in \mathbb{F}_{p^n}^*$:
  $$\Delta_F(a, b) \cdot \Delta_F(a, c^{-1}b) = 0$$
  Isso significa que, para qualquer diferença de entrada $a$, não pode haver uma diferença de saída $b$ tal que tanto $b$ quanto $c^{-1}b$ apareçam simultaneamente na DDT.
• Impacto Computacional:
  • Antes: Verificação direta via definição exigia $O(p^{3n})$ operações.
  • Agora: Com a DDT pré-calculada (que pode ser feita em $O(p^{2n})$ ou $O(np^n)$ para $p=2$), a verificação de PcN para um $c$ fixo reduz-se a $O(p^{2n})$.
  • Permite enumerar todos os valores de $c$ para os quais uma função é PcN em tempo $O(p^{3n})$.

B. Dicotomia para Monômios (Seção 3)

• Teorema 3.8: Para funções monomiais $F(x) = ax^d$ sobre $\mathbb{F}_{2^n}$, existe uma dicotomia estrita ("tudo ou nada"):
  • Ou $F(x + \alpha) + cF(x)$ é uma permutação para todos os deslocamentos não nulos $\alpha$.
  • Ou não é uma permutação para nenhum deslocamento não nulo.
• Contraste: Os autores provam que essa propriedade não se mantém para polinômios gerais (fornecendo um contraexemplo com um binômio), indicando que a homogeneidade é a chave para esse comportamento.

C. Caracterização de Polinômios Quadráticos e DO

• Para permutações quadráticas e polinômios de Dembowski-Ostrom (DO), os autores fornecem caracterizações algébricas explícitas baseadas em complementos ortogonais de subespaços definidos por derivadas parciais.
• Teorema 3.26: Estabelece condições geométricas sobre a interseção de espaços afins para garantir a propriedade PcN.

D. Incompatibilidade com APN (Seção 3)

• Teorema 3.29: Existe uma incompatibilidade fundamental entre ser uma função APN (Almost Perfect Nonlinear, $\delta=2$ para $c=1$) e ser PcN para $c \neq 1$.
  • Uma permutação APN pode ser PcN para, no máximo, dois valores de $c$ (especificamente $c$ e $c^{-1}$), e tipicamente para nenhum.
  • Isso revela um compromisso (trade-off) fundamental no design criptográfico: otimizar para resistência diferencial clássica (APN) pode prejudicar a resistência contra ataques diferenciais generalizados ($c$-diferenciais).

E. Invariância sob Transformações Afins (Seção 4)

• Os autores identificam a primeira classe explícita de transformações afins que preservam a uniformidade diferencial $c$.
• Mostram que composições com automorfismos de Frobenius ($L(x) = x^{p^i}$) e translações podem preservar ou alterar a propriedade PcN, dependendo da relação entre $c$ e o parâmetro da transformação.
• Demonstram que a propriedade PcN não é preservada sob inversão funcional (diferente de muitas outras propriedades criptográficas), ou seja, se $F$ é PcN, $F^{-1}$ não necessariamente o é.

F. Limites de Não-Linearidade (Seção 5)

• Os autores derivam limites superiores rigorosos para a não-linearidade de funções PcN.
• Teorema 5.4: Se $c$ é um elemento primitivo e $n$ é ímpar, uma função PcN não pode atingir o limite de Sidelnikov–Chabaud–Vaudenay (que define funções "Almost Bent").
• Isso implica que funções PcN possuem um espectro de Walsh-Hadamard com esparsidade específica, limitando sua não-linearidade máxima.

4. Significado e Impacto

1. Ferramenta Prática de Análise: A caracterização via DDT clássica transforma a verificação de PcN de um problema computacionalmente proibitivo em uma tarefa viável para dimensões moderadas, permitindo a análise sistemática de S-boxes contra ataques $c$-diferenciais.
2. Fundamentação Teórica: A descoberta da dicotomia estrita para monômios e a incompatibilidade com funções APN fornecem uma compreensão mais profunda da estrutura algébrica necessária para resistir a ataques diferenciais generalizados.
3. Segurança de Padrões Reais: O trabalho valida as preocupações levantadas pelo ataque ao Kuznyechik, mostrando que a segurança de padrões criptográficos modernos depende não apenas da resistência diferencial clássica ($c=1$), mas também da análise de derivadas generalizadas.
4. Direções Futuras: O artigo deixa questões em aberto, como encontrar condições algébricas suficientes para que a dicotomia "tudo ou nada" se aplique a polinômios gerais (não apenas monômios) e estender a caracterização para funções $(n, m)$ onde $m < n$.

Em resumo, o artigo estabelece a Perfeita Não-Linearidade $c$ como um regime estrutural distinto e altamente restritivo na teoria dos polinômios de permutação, fornecendo as ferramentas matemáticas e computacionais necessárias para sua verificação e compreensão em criptografia.