Quadratic APN Functions in Dimension 8 via Gröbner Basis Search in a Self-Equivalence Subspace

Resumo Técnico: Funções APN Quadráticas em Dimensão 8 via Busca de Base de Gröbner em um Subespaço de Autoequivalência

Enunciado do Problema
A classificação de funções Quase Perfeitas Não Lineares (APN) sobre $\mathbb{F}_{2^n}$ até a equivalência CCZ é um problema central em criptografia, particularmente para $n=8$. Enquanto a classificação é completa para $n \leq 6$, ela permanece parcial para $n=8$. O espaço de busca para funções APN quadráticas é vasto ($2^{224}$ vetores de coeficientes possíveis), tornando a busca aleatória global inviável devido a uma densidade APN estimada de $\approx 2^{-n}$. Esforços sistemáticos anteriores, como a busca em árvore recursiva de Beierle, Brinkmann e Leander (BBL2021), exploraram subespaços algébricos estruturados definidos por restrições de autoequivalência. Especificamente, BBL2021 relatou encontrar zero funções APN dentro do subespaço de autoequivalência de 40 dimensões $V_A$ associado a um automorfismo linear $A$ de ordem 5 (índice de classe 22). Este artigo investiga se este subespaço realmente não contém funções APN ou se o método de busca anterior falhou em localizá-las.

Metodologia
Os autores propõem um pipeline computacional de duas fases que combina amostragem aleatória com enumeração algébrica para explorar $V_A$ de forma mais eficaz do que a busca em árvore anterior.

1. Fase 1: Amostragem Aleatória via Parametrização RREF
   Os autores constroem uma parametrização explícita de Forma Escalonada Reduzida por Linhas (RREF) do subespaço de 40 dimensões $V_A = \{F : F \circ A = A \circ F\}$. Isso reduz o espaço de busca de $2^{224}$ para $2^{40}$. Dentro deste subespaço, a densidade empírica de funções APN é encontrada como aproximadamente $10^{-4}$ (cerca de 1 função APN por cada 11.000 amostras aleatórias), tornando a amostragem direcionada viável. Os autores realizam amostragem aleatória para identificar "centros APN" (funções em $V_A$ que são APN).

2. Fase 2: Computação de Fatias de Base de Gröbner
   Para cada centro APN encontrado na Fase 1, os autores definem um hiperplano afim de 24 dimensões (uma "fatia NL=4") passando por esse centro. Isso é alcançado fixando 200 dos 224 coeficientes da Forma Normal Algébrica (ANF) (especificamente aqueles correspondentes a pares com índices $p \leq 4$) para os valores do centro, deixando 24 coeficientes como incógnitas.
   A condição APN para as 255 diferenças não nulas é codificada como um sistema de equações polinomiais sobre o anel booleano. Os autores utilizam o sistema de álgebra computacional Magma para computar uma base de Gröbner para este sistema.

   • Se o sistema for infactível, a fatia não contém outras funções APN.
   • Se o sistema possuir soluções, a enumeração da base de Gröbner encontra todas as funções APN dentro dessa fatia específica de 24 dimensões.
     Crucialmente, embora o centro seja garantido de estar em $V_A$, as soluções encontradas pelo passo da base de Gröbner não estão restritas a $V_A$; elas podem residir fora do subespaço de autoequivalência.

3. Classificação e Verificação
   As funções encontradas são classificadas usando o invariante de orto-derivada $\sigma(F)$, que é provado ser um invariante CCZ completo para funções APN quadráticas (pelo teorema de Yoshiara e resultados de Canteaut et al.). Os autores realizam comparações de fluxo contínuo de suas assinaturas contra três bases de dados principais: a compilação pré-2020 de BBL2021, o banco de dados de Beierle et al. 2025 (contendo $\approx 3,8$ milhões de funções) e as funções Gold clássicas.

Principais Resultados
Os autores executaram o pipeline em 428 fatias distintas de 24 dimensões (0,65% do total de $2^{16}$ fatias possíveis em $V_A$).

• Descoberta de Novas Classes: A busca rendeu 566 funções APN quadráticas únicas pertencentes a seis classes de equivalência CCZ.
  • Quatro Novas Classes (A, B, C, D): Estas 500 funções (362 na Classe A, 72 em B, 36 em C, 30 em D) não estão presentes no banco de dados Beierle 2025, no banco de dados BBL2021 pré-2020, ou nas famílias Gold clássicas.
  • Duas Classes Conhecidas (E, F): Estas correspondem às funções Gold $x^3$ e $x^9$ (e suas órbitas de Frobenius), servindo como controles para validar o pipeline.
• Achados Estruturais:
  • Pertencimento ao Subespaço: Um teste de pertinência ($F \circ A = A \circ F$) revelou que a Classe A, E e F residem inteiramente dentro de $V_A$. No entanto, as Classes B, C e D residem inteiramente fora de $V_A$.
  • O Fenômeno "Gateway" (Portal): As 138 funções nas novas classes externas (B, C, D) foram encontradas exclusivamente em fatias centradas em funções Gold (Classes E e F) que residem dentro de $V_A$. Fatias centradas em funções da Classe A não produziram vizinhos fora de $V_A$.
  • Falha de Sementes Alternativas: Experimentos comparativos usando 532 funções APN do banco de dados Beierle 2025 (que estão fora de $V_A$) como centros de fatia resultaram em zero vizinhos APN encontrados. Isso sugere que a capacidade de "gateway" para descobrir novas classes via fatiamento de base de Gröbner é específica para funções dentro do subespaço de autoequivalência, não uma propriedade genérica de todas as funções APN.

Significância e Alegações
O artigo alega várias contribuições significativas para o campo da classificação de funções APN quadráticas:

1. Correção de Resultados Anteriores: Os autores demonstram que o subespaço de autoequivalência $V_A$ (índice de classe 22), anteriormente reportado por BBL2021 como não contendo funções APN, contém na verdade pelo menos quatro classes CCZ de funções APN quadráticas. A falha da busca em árvore de BBL2021 é atribuída à sua estratégia de poda de ramos, que pode ter eliminado soluções válidas neste subespaço estruturado, enquanto a abordagem de base de Gröbner realiza uma enumeração completa dentro de cada fatia.
2. Descoberta de Novas Funções: O artigo fornece prova rigorosa (via o invariante de orto-derivada) de que quatro novas classes CCZ de funções APN quadráticas existem para $n=8$, distintas das $\approx 3,8$ milhões de funções no maior banco de dados conhecido.
3. Inovação Metodológica: O trabalho introduz um mecanismo de "navegação por GB" (Gröbner Basis). Eles postulam que, embora a busca global seja impossível, é possível explorar subespaços estruturados com maior densidade APN para encontrar funções "semente". O passo da base de Gröbner então atua como um enumerador local, capaz de sair do subespaço para encontrar novas classes. Os autores enfatizam que este mecanismo não é genérico; ele depende da estrutura algébrica específica do subespaço de autoequivalência, como evidenciado pela falha de funções não pertencentes ao subespaço em atuarem como sementes produtivas.
4. Completude da Orto-Derivada: O trabalho reforça a utilidade da assinatura de orto-derivada como um invariante CCZ exato para funções quadráticas, permitindo uma classificação rigorosa sem testes exaustivos par a par.

Os autores concluem que sua abordagem oferece um programa sistemático para estender a classificação de funções APN quadráticas através da exploração de outros índices de classe de BBL2021 e utilizando a técnica de fatiamento de base de Gröbner para navegar pelo panorama APN.