On the Walsh spectra of quadratic APN functions

Resumo Técnico: Sobre os Espectros de Walsh de Funções Quadráticas APN

Declaração do Problema
Funções Não Lineares Quase Perfeitas (APN) são componentes críticos em sistemas criptográficos simétricos, proporcionando resistência ótima contra ataques diferenciais. Uma propriedade fundamental dessas funções é sua linearidade, que é determinada pelo seu espectro de Walsh. Enquanto a distribuição de amplitudes (e, portanto, o espectro de Walsh) de funções quadráticas APN é totalmente caracterizada para dimensões ímpares $n$, o caso para $n$ par permanece em grande parte aberto. A única restrição geral conhecida para $n$ par é derivada do quarto momento da transformada de Walsh. Este artigo aborda a lacuna na compreensão dos espectros de Walsh possíveis de funções quadráticas APN $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ onde $n$ é par, buscando especificamente derivar condições mais fortes sobre suas distribuições de amplitude.

Metodologia
Os autores estabelecem duas conexões geométricas inovadoras entre funções quadráticas APN e geometria finita:

1. Partições de Espaço Vetorial: O artigo demonstra que a distribuição de amplitude de uma função quadrática APN corresponde unicamente a uma partição de espaço vetorial do espaço ambiente $\mathbb{F}_2^n$. Especificamente, as funções componentes não triviais e não bent de $F$ estão associadas a subespaços em uma partição onde a dimensão de cada subespaço está diretamente ligada à amplitude da função componente correspondente.
2. Conjuntos de Bloqueio: O conjunto de componentes não triviais e não bent, denotado $N_F$, é mostrado para formar um tipo específico de conjunto de bloqueio no espaço projetivo $PG(n-1, 2)$. Crucialmente, os autores provam que a interseção de $N_F$ com qualquer subespaço de dimensão $n/2$ deve conter um número ímpar de pontos.

Ao aproveitar teoremas estabelecidos sobre partições de espaço vetorial e conjuntos de bloqueio (especificamente resultados relativos a "caudas" de partições e conjuntos de bloqueio mínimos), os autores traduzem essas restrições geométricas em limites algébricos sobre as distribuições de amplitude de funções quadráticas APN.

Principais Contribuições e Resultados

• Conexão com Partições de Espaço Vetorial (Seção II):

  • O Teorema II.4 estabelece que, se uma função componente $F_b$ tem amplitude $2^{(n+k)/2}$, ela corresponde a um subespaço de dimensão $k$ em uma partição de espaço vetorial de $\mathbb{F}_2^n$.
  • Essa conexão permite a aplicação de condições de empacotamento e limites de dimensão da teoria de partições.
  • Teorema II.10: Uma função quadrática APN pode ter no máximo uma função componente com amplitude maior que $2^{3n/4}$. Se tal componente existir, todas as outras devem ter amplitude no máximo $2^{(2n-l)/2}$, onde $l$ é o expoente da amplitude máxima.
  • Proposições II.14–II.16: Novos limites inferiores para o número de componentes não bent ($|N_F|$) são derivados com base na linearidade e na presença de amplitudes específicas.

• Conexão com Conjuntos de Bloqueio (Seção III):

  • Corolário III.3: O conjunto $N_F$ é um conjunto de bloqueio em $PG(n-1, 2)$ em relação a subespaços de dimensão $(n/2)$, com a propriedade adicional de que todo tal subespaço intersecciona $N_F$ em um número ímpar de pontos.
  • Teorema III.9: Este é o primeiro limite superior não trivial e geral para o número de funções componentes bent para uma função quadrática APN. Especificamente, para $n \ge 6$, o número de componentes não bent satisfaz $|N_F| \ge 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1$. A igualdade é possível apenas se $n=8$. Consequentemente, o número de componentes bent é no máximo $2^n - 2^{n/2} - 2^{n/2-2} - 2^{n/2-3}$.

• Síntese e Análise Dimensional (Seção IV):

  • Ao combinar as restrições de partição e conjunto de bloqueio, os autores eliminam várias distribuições de amplitude teoricamente possíveis.
  • Teorema IV.1: Partições de espaço vetorial do tipo $[(n/2)^{2^{n/2+1}}]$ (uma $(n/2)$-disseminação) não correspondem a nenhuma função quadrática APN.
  • Teorema IV.5: Para $n=8$, o artigo estreita as distribuições de amplitude possíveis para uma lista específica (excluindo a partição trivial e a 4-disseminação), reduzindo o número de espectros de Walsh estendidos potenciais para no máximo 18 tipos distintos.
  • Proposição IV.4: O artigo compara a força dos limites inferiores derivados para $|N_F|$ em diferentes faixas de parâmetros, identificando qual limite é dominante dependendo da linearidade da função.

• Equivalência e Permutações (Seção V):

  • O artigo analisa como essas estruturas se comportam sob equivalência EA e equivalência CCZ.
  • Corolário V.6: Se uma função quadrática APN é CCZ-equivalente a uma permutação, ela não pode ter poucas componentes não bent; especificamente, $|N_F| \ge 3(2^{n/2}-1)$, e $N_F$ deve ser um conjunto de bloqueio triplo.

Significado e Afirmativas
O artigo afirma fornecer as primeiras condições gerais sobre os espectros de Walsh de funções quadráticas APN além do bem conhecido limite do quarto momento. Ao vincular as propriedades algébricas dessas funções às estruturas combinatórias de partições de espaço vetorial e conjuntos de bloqueio, os autores derivam restrições fortes sobre as distribuições de amplitude possíveis.

Os autores afirmam explicitamente que seus resultados:

1. Provam que uma função quadrática APN pode ter no máximo uma componente com amplitude maior que $2^{3n/4}$.
2. Fornecem o primeiro limite superior não trivial para o número de componentes bent.
3. Oferecem condições para determinar se uma função é CCZ-equivalente a uma permutação com base em seu número de componentes bent.
4. Listam sistematicamente todas as distribuições de amplitude possíveis para pequenas dimensões pares (especificamente $n=6, 8, 10$), destacando quais são realizadas e quais permanecem problemas abertos.

O artigo conclui listando problemas abertos, incluindo a existência de funções APN com distribuições de amplitude específicas na dimensão 8 e a busca por famílias infinitas de funções quadráticas APN com espectros de Walsh não clássicos. Os autores mantêm um tom modesto, observando que, embora tenham excluído muitas possibilidades, a classificação completa dos espectros de Walsh para funções quadráticas APN permanece um desafio aberto.