On APN Exponents and the Differential and Boomerang Properties of Binomials in Characteristic 3

Resumo Técnico: Sobre Expoentes APN e as Propriedades Diferencial e Boomerang de Binômios em Característica 3

Declaração do Problema
O artigo investiga as propriedades criptográficas de funções binômicas da forma $F_r(x) = x^r(1 + \chi(x))$ sobre corpos finitos $\mathbb{F}_{3^n}$, onde $\chi(x)$ é o caractere quadrático. Embora a uniformidade diferencial seja uma métrica padrão para resistência contra ataques diferenciais, ela não captura totalmente a resistência a ataques boomerang. A noção de uniformidade boomerang ($\beta_F$) foi introduzida para abordar essa questão. Estudos anteriores [9] estabeleceram que, para certos expoentes $r$, a função $F_r$ exibe baixa uniformidade diferencial e uniformidade boomerang limitada por 2. No entanto, observações empíricas sugerem que, em característica 3, instâncias de uniformidade boomerang extremamente baixa (especificamente 0 ou 1) ocorrem com mais frequência do que em outras características. O artigo visa analisar sistematicamente esses fenômenos, identificar os expoentes $r$ específicos que resultam em uniformidade boomerang 0 ou 1 e fornecer provas rigorosas para essas classes.

Metodologia
Os autores empregam uma combinação de análise teórica e verificação computacional:

1. Estrutura Teórica: O estudo baseia-se no conceito de funções "localmente-PN" e "localmente-APN". Ao analisar a equação diferencial $(x+1)^r - x^r = b$ e o sistema boomerang associado, os autores derivam condições sob as quais o espectro diferencial e o espectro boomerang podem ser determinados explicitamente.
2. Classificação APN: O artigo fornece uma parametrização sistemática de funções potência Não Lineares Quase Perfeitas (APN) decorrentes da construção de Zha e Wang [23]. Isso envolve resolver a condição diofantina $(3m+1)r - 2 = k(3^n-1)$ para gerar famílias explícitas de expoentes.
3. Somas de Caracteres e Análise Espectral: Para determinar o espectro boomerang para classes específicas (notadamente $r = 3^n - 3$), os autores avaliam somas de caracteres envolvendo caracteres quadráticos e raízes polinomiais.
4. Busca Computacional: Buscas exaustivas foram conduzidas para pequenos valores de $n$ (até $n=13$) usando SageMath para identificar expoentes que resultam em uniformidade boomerang 0 ou 1. Esses resultados são cruzados com as famílias teóricas derivadas.

Principais Contribuições e Resultados

• Parametrização de Expoentes APN: Os autores apresentam uma parametrização explícita (Proposição 3.3) para expoentes APN derivados da estrutura em [23]. Eles demonstram que, para $n \le 13$, essa construção generalizada accounts para todas as funções potência APN conhecidas em característica 3 que não estavam previamente listadas em tabelas padrão [2]. Isso inclui a recuperação de classes conhecidas (por exemplo, $r = 3^{(n+1)/2} - 1$) e a identificação de novos casos esporádicos.
• Duas Classes com Uniformidade Boomerang 0: O artigo prova rigorosamente que duas classes específicas de binômios $F_r$ possuem a uniformidade boomerang mínima possível de 0:
  1. Expoentes $r$ decorrentes da construção APN em [23] (satisfazendo a condição $(3m+1)r - 2 = k(3^n-1)$).
  2. O expoente $r = 2 \cdot 3^{(n-1)/2} + 1$.
     Para ambas as classes, os autores provam que $F_r$ é localmente-PN e derivam seus espectros diferenciais.
• Análise de $r = 3^n - 3$: O artigo analisa o binômio com expoente $r = 3^n - 3$. É provado que, para $n$ ímpar $\ge 5$, essa função é localmente-APN com uniformidade boomerang 1. Os autores determinam completamente seu espectro boomerang avaliando somas de caracteres específicas, fornecendo fórmulas explícitas para o número de valores de $b$ que resultam em $\beta_{F_r}(1, b) = 0$ e $1$.
• Classificação Numérica: Através de buscas exaustivas para $n \le 13$, os autores compilam tabelas de expoentes que resultam em uniformidade boomerang 0 e 1. Eles observam que, para $n \le 9$, a condição de ser localmente-PN parece ser tanto necessária quanto suficiente para uniformidade boomerang 0, mesmo sem a suposição estrita $\gcd(r, 3^n-1) \in \{1, 2\}$ usada em limites teóricos anteriores.

Significância
O artigo esclarece e estende estudos existentes sobre as propriedades criptográficas de binômios em característica 3. Sua principal significância reside em:

1. Caracterização Sistemática: Fornecer uma estrutura unificada que explica por que certos binômios em característica 3 alcançam uniformidade boomerang 0 ou 1, vinculando essas propriedades diretamente a construções específicas de expoentes APN.
2. Extensão de Limites: Demonstrar que o limite geral de uniformidade boomerang 2 (estabelecido em [9]) pode ser estritamente melhorado para 0 ou 1 para famílias infinitas específicas em característica 3.
3. Completude da Classificação APN: Mostrar que a parametrização de expoentes APN de [23] cobre todas as funções potência APN conhecidas em característica 3 para pequenos $n$, sugerindo uma estrutura abrangente para essas funções.
4. Validação Empírica: Os resultados numéricos apoiam as descobertas teóricas e destacam uma forte correlação entre a propriedade localmente-PN e a uniformidade boomerang 0, apresentando essa relação como uma área potencial para futura prova rigorosa.

Os autores concluem que, embora tenham identificado famílias infinitas e casos esporádicos com propriedades boomerang ótimas, a equivalência precisa entre a propriedade localmente-PN e a uniformidade boomerang 0 permanece um problema aberto, e a extensão dos casos esporádicos de uniformidade boomerang 1 para famílias infinitas é uma direção para pesquisa futura.