A class of locally differentially $4$-uniform power functions with Niho exponents

Resumo Técnico: Funções de Potência 4-Uniformes Localmente Diferencialmente com Exponentes de Niho

1. Problema e Contexto

O artigo aborda um problema fundamental na criptografia simétrica: a análise da uniformidade diferencial e do espectro diferencial de funções de potência sobre corpos finitos.

• Contexto: Funções criptográficas, especialmente aquelas usadas em caixas de substituição (S-boxes) em cifras de bloco, devem resistir à criptanálise diferencial. A resistência é medida pela uniformidade diferencial ($\Delta_F$).
• Desafio: Determinar o espectro diferencial (a distribuição exata de quantas vezes cada valor de diferença ocorre na tabela de distribuição de diferenças) de funções de potência é uma tarefa computacionalmente difícil. Poucas classes de funções têm seu espectro totalmente determinado.
• Foco Específico: O artigo investiga a função de potência $F(x) = x^{3q-2}$ sobre o corpo finito $\mathbb{F}_{q^2}$, onde $q = 2^m$ e $m \ge 4$ é um inteiro par. O expoente $d = 3q-2$ é um expoente de Niho, conhecido por suas aplicações em teoria de códigos e design de sequências.
• Motivação: Funções com baixa uniformidade diferencial são desejáveis. No caso de característica par (corpos binários), a uniformidade mínima possível é 2 (APN - Almost Perfect Nonlinear). O objetivo é verificar se esta nova função possui propriedades de segurança robustas e determinar seu espectro completo.

2. Metodologia

Os autores empregaram uma abordagem combinatória e algébrica rigorosa para determinar o espectro diferencial:

• Análise de Equações Diferenciais: O problema foi reduzido à contagem de soluções da equação diferencial $F(x+1) + F(x) = b$ para $b \in \mathbb{F}_{q^2}$.
• Decomposição do Corpo: Utilizaram a estrutura do grupo multiplicativo $\mathbb{F}_{q^2}^*$. Especificamente, usaram o fato de que qualquer elemento não nulo pode ser escrito como $x = yz$, onde $y \in \mathbb{F}_q^*$ e $z$ pertence ao subgrupo cíclico $U_{q+1} = \{x \in \mathbb{F}_{q^2} : x^{q+1} = 1\}$.
• Estudo de Trinômios: Analisaram a cardinalidade dos conjuntos de pré-imagens de uma classe específica de trinômios sobre $\mathbb{F}_{q^2}$ da forma $f(x) = x^2 + x^{1-q} + x^{2-q}$. Este passo foi crucial para limitar o número de soluções da equação diferencial.
• Sistemas de Equações e Sequências Recursivas:
  • Derivaram o número de soluções para um sistema de equações simétricas envolvendo quatro variáveis.
  • Introduziram uma sequência recursiva $\{\tau_m\}$ definida por $\tau_1 = 1/2$, $\tau_2 = -7/4$ e $\tau_m = \frac{1}{2}\tau_{m-1} - \tau_{m-2}$, cuja forma fechada envolve raízes quadradas de $-15$.
  • Utilizaram identidades fundamentais do espectro diferencial (somas ponderadas de $\omega_i$) e um lema que relaciona a soma dos quadrados das multiplicidades ($\sum i^2 \omega_i$) ao número de soluções de um sistema de equações de grau 4.

3. Contribuições Chave

1. Determinação do Espectro Diferencial Completo: O artigo fornece a primeira determinação completa do espectro diferencial para a classe de funções $F(x) = x^{3q-2}$ sobre $\mathbb{F}_{q^2}$ com $m$ par e $m \ge 4$.
2. Prova de Não-Equivalência CCZ: Os autores demonstram que esta função é CCZ-inequivalente às funções de potência com espectros diferenciais já conhecidos, expandindo o conjunto de funções criptográficas conhecidas.
3. Caracterização de Uniformidade Local: Estabelecem que a função é localmente 4-uniforme diferencialmente. Isso significa que, embora a uniformidade diferencial global seja alta ($\Delta_F = q$), para a maioria dos valores de diferença ($b \notin \mathbb{F}_2$), o número de soluções é limitado a 4.
4. Fórmulas Analíticas: Derivaram fórmulas fechadas para as multiplicidades $\omega_i$ (o número de vezes que a diferença $i$ ocorre no espectro) em função de $q$ e da sequência $\tau_m$.

4. Resultados Principais

O Teorema 4 do artigo resume os resultados principais:

• Uniformidade Diferencial Global: $\Delta_F = q$. Isso ocorre porque, para $b=1$, a equação diferencial possui exatamente $q$ soluções.
• Comportamento Local: Para todo $b \in \mathbb{F}_{q^2} \setminus \{1\}$, a equação diferencial tem no máximo 4 soluções ($\delta_F(1,b) \le 4$).
• Espectro Diferencial ($DS_F$): O espectro é composto apenas pelos valores $0, 2, 4$e$q$. As multiplicidades são dadas por:
  • $\omega_q = 1$ (correspondente a $b=1$).
  • $\omega_4 = \frac{1}{8}(q^2 - \tau_m q + 1)$.
  • $\omega_2 = \frac{1}{4}(q^2 + (\tau_m - 2)q - 1)$.
  • $\omega_0 = \frac{1}{8}(5q^2 + (-\tau_m + 4)q - 7)$.
  • Onde $\tau_m$ é o termo geral da sequência definida anteriormente.
• Validação: Os resultados teóricos foram validados computacionalmente usando o software MAGMA para casos específicos ($m=4, 6, 8$), confirmando a precisão das fórmulas derivadas.

5. Significado e Impacto

• Avanço na Teoria Criptográfica: Este trabalho preenche uma lacuna na literatura sobre espectros diferenciais de funções com expoentes de Niho. A descoberta de uma função que é "localmente 4-uniforme" é valiosa, pois oferece um equilíbrio entre propriedades algébricas e resistência a ataques diferenciais na maioria dos casos práticos.
• Aplicações em S-boxes: Embora a uniformidade global seja $q$ (o que pode ser alto para S-boxes diretas), o comportamento local limitado a 4 sugere que variantes ou construções baseadas nesta função podem ser úteis em designs de cifras onde a estrutura algébrica específica é necessária.
• Ferramentas Matemáticas: A metodologia desenvolvida, especialmente o uso da sequência $\tau_m$ para contar soluções de sistemas de equações sobre corpos finitos, pode ser aplicada a outros problemas em teoria de códigos e criptografia.
• Direções Futuras: O artigo abre caminho para investigar o espectro diferencial para outros valores de $q$ (como potências ímpares) e explorar outras classes de expoentes de Niho.

Em suma, o artigo apresenta um avanço significativo na compreensão das propriedades diferenciais de funções de potência com expoentes de Niho, fornecendo resultados teóricos rigorosos e validados computacionalmente que enriquecem o arsenal de funções para o design de sistemas criptográficos seguros.