🔢 mathematics

Triprojective almost perfect nonlinear permutations and functions

Este artigo apresenta uma grande família de permutações quase perfeitas não lineares (APN) para espaços vetoriais finitos de dimensões ímpares divisíveis por três, bem como funções APN não bijectivas para dimensões pares, todas caracterizadas por uma estrutura triprojectiva induzida pelo grupo linear geral $\mathrm{GL}(3,2^m)$ .

Autores originais: Faruk Göloğlu, Lukas Kölsch

Publicado 2026-05-19

📖 5 min de leitura🧠 Leitura aprofundada

CC0 1.0

Autores originais: Faruk Göloğlu, Lukas Kölsch

Artigo original dedicado ao domínio público sob CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você é um mestre-alfaiate tentando projetar o cofre definitivo. No mundo da segurança digital, as "trancas" são funções matemáticas usadas para embaralhar dados, de modo que hackers não consigam descobrir a mensagem original. O artigo sobre o qual você está perguntando é um projeto para construir um novo tipo de trava, incrivelmente forte.

Aqui está a história do que os autores, Faruk Gölöglu e Lukas Kölsch, descobriram, explicada sem o pesado jargão matemático.

O Objetivo: O Embaralhador Perfeito

Na criptografia, existe um tipo específico de trava chamado Caixa-S (Substitution Box). Pense em uma Caixa-S como uma máquina que recebe um conjunto de entradas (como uma combinação de números) e libera um conjunto completamente diferente de saídas.

O perigo vem de um método chamado "criptanálise diferencial". Imagine um ladrão tentando arrombar seu cofre percebendo padrões: "Se eu girar o mostrador um clique para a direita, a trava muda seu som em uma quantidade específica. Se eu girá-lo dois cliques, o som muda de forma diferente." Se a trava reagir de forma muito previsível a pequenas mudanças, o ladrão pode trabalhar de trás para frente para encontrar a chave.

Para impedir isso, os matemáticos buscam funções APN (Quase Perfeitamente Não Lineares). Estas são as "travas perfeitas", onde uma pequena mudança na entrada causa uma mudança caótica e imprevisível na saída. O objetivo é fazer com que, não importa como o ladrão ajuste a entrada, a saída pareça ruído aleatório.

O Grande Desafio: O Problema da "Dimensão Par"

Por muito tempo, os matemáticos souberam como construir essas travas perfeitas para certos tamanhos de dados (especificamente, quando o tamanho dos dados é um número ímpar). Mas, para blocos de dados de tamanho par (que são muito comuns em computadores do mundo real), encontrar uma trava perfeita que também seja uma permutação (significando que cada entrada individual mapeia para uma saída única, de modo que nada se perde) tem sido uma enorme dor de cabeça. É como tentar encontrar uma chave que se encaixe em todas as fechaduras de uma fileira específica de casas, mas você continua descobrindo que algumas chaves abrem duas fechaduras ao mesmo tempo, ou que algumas fechaduras não têm chave alguma.

Os autores deste artigo dizem: "Encontramos uma maneira de construir essas travas perfeitas e não repetitivas para uma enorme nova família de blocos de dados de tamanho par."

O Ingrediente Secreto: Arquitetura "Triprojetiva"

Os autores não apenas tropeçaram em uma fórmula aleatória. Eles construíram suas travas usando um estilo arquitetônico específico que chamam de "Triprojetiva".

Para entender isso, imagine que você está olhando para uma escultura 3D.

Travas Padrão: Geralmente, estas são construídas olhando para a escultura apenas de um ângulo (uma visão plana, 2D).
As Novas Travas "Triprojetivas": Os autores construíram sua função olhando para a escultura de três ângulos diferentes simultaneamente, usando um grupo especial de regras (relacionado a uma estrutura matemática chamada $GL(3, 2^m)$ ).

Eles chamam isso de estrutura "Triprojetiva" porque trata os dados como se existissem em um espaço 3D onde as regras da geometria estão ligeiramente distorcidas. Ao organizar os dados dessa maneira, eles garantem que o "embaralhamento" ocorra de uma forma incrivelmente difícil de prever, independentemente de como você tenta sondá-lo.

A Fórmula Mágica

O artigo apresenta uma receita específica (uma fórmula) para essas travas. Envolve três variáveis ( $x, y, z$ ) e alguns números especiais ( $a, b, c$ ).

A receita tem uma "verificação de segurança". Antes de poder usar a trava, você precisa executar um teste rápido para garantir que uma equação específica não tenha soluções.

Se o teste passar: Você obtém uma trava perfeita e inquebrável (uma permutação APN).
Se o teste falhar: A trava ainda é muito forte (altamente não linear), mas pode não ser uma permutação perfeita (algumas entradas podem mapear para a mesma saída).

Os autores provam que, se você escolher seus números corretamente, essa receita funciona para todas as dimensões ímpares divisíveis por três. Esta é uma enorme expansão do que era conhecido anteriormente.

Por Que Isso Importa (De Acordo com o Artigo)

Unifica Descobertas Antigas: Os autores mostram que várias outras fórmulas complicadas descobertas por diferentes matemáticos nos últimos anos são, na verdade, apenas versões simplificadas e especiais de sua nova receita "Triprojetiva". É como perceber que três tipos diferentes de carros são, na verdade, apenas diferentes pinturas no mesmo chassi.
É Novo e Único: Eles provam que sua nova família de travas é fundamentalmente diferente das travas "Gold" (uma famosa família de funções APN descoberta décadas atrás). Eles não estão apenas renomeando chaves antigas; estão forjando chaves inteiramente novas.
A Prova é "Limpa": Tentativas anteriores de provar que essas travas funcionavam exigiam simulações massivas de computadores e páginas de álgebra complexa. Os autores usaram uma abordagem inteligente e puramente lógica (usando "polinômios torcidos" e propriedades de corpos finitos) para provar seus resultados sem precisar de um supercomputador.

A Conclusão

Este artigo é um avanço matemático no projeto de travas de segurança digital. Os autores descobriram um novo e versátil método "Triprojetivo" para construir Permutações Quase Perfeitamente Não Lineares.

Em termos simples: Eles encontraram uma nova e confiável maneira de construir os embaralhadores de dados mais fortes possíveis para uma ampla gama de tamanhos de dados de computador, resolvendo um problema que havia deixado especialistas perplexos por anos. Eles não encontraram apenas uma nova trava; encontraram uma fábrica inteira para produzi-las e provaram que essas novas travas são distintas de qualquer outra que já tenhamos visto antes.

Resumo Técnico: Permutações e Funções Não Lineares Quase Perfeitas Triprojetivas

Declaração do Problema
O artigo aborda a existência e a construção de permutações Não Lineares Quase Perfeitas (APN) sobre espaços vetoriais finitos de dimensão par. No contexto da criptanálise diferencial, funções APN (aquelas com uniformidade diferencial $\Delta_F = 2$ ) são críticas para o projeto de Caixas-S seguras em redes de substituição-permutação. Embora se saiba que funções APN existem para dimensões ímpares, a existência de permutações APN (bijeções) para dimensões pares $n > 6$ permanece um grande problema em aberto. Especificamente, os autores focam na construção de grandes famílias de tais funções nas dimensões $n = 3m$ (onde $m$ é ímpar) e na caracterização de suas propriedades, incluindo suas classes de equivalência e tamanhos de conjuntos imagem.

Metodologia
Os autores empregam uma abordagem estrutural baseada em mapas "triprojetivos" e "semi-quadráticos". A metodologia prossegue através das seguintes etapas:

Estrutura Projetiva: Os autores definem uma classe de funções $F \in SQH(3, q)$ (semi-quadráticas homogêneas) sobre $\mathbb{F}_q^3$ (onde $q=2^m$ ). Essas funções são induzidas por formas semi-quadráticas que satisfazem propriedades específicas de homogeneidade, permitindo-lhes induzir mapas bem definidos no espaço projetivo $\mathbb{P}^2(\mathbb{F}_q)$ .
Critérios de Bijecção: Baseando-se em trabalhos anteriores (Teorema 1.2), o artigo utiliza uma condição sobre um polinômio univariado específico $P(X) = aX^{\sigma^2+\sigma+1} + bX^{\sigma+1} + cX + 1$ para garantir que o mapa induzido no espaço projetivo seja uma bijecção.
Análise de Uniformidade Diferencial:
- Caso $m/d$ é par: Os autores utilizam o conceito de "núcleo" da função (um subcorpo sobre o qual o mapa derivado é linear) para mostrar que a uniformidade diferencial é $2d$ , onde $d = \gcd(k, m)$ .
- Caso $m/d$ é ímpar: Os autores introduzem ferramentas da teoria de anéis de polinômios torcidos (anéis de Ore) $\mathbb{F}_q[t; \sigma]$ . Eles estabelecem uma conexão entre as raízes do polinômio $P(X)$ e a existência de divisores lineares à direita no anel torcido. Ao estender o corpo e analisar o mínimo múltiplo comum à esquerda (mmlc) de polinômios, eles provam que a uniformidade diferencial permanece $2d$ mesmo neste caso mais complexo.
Equivalência e Classificação: O artigo compara a nova família com funções APN trivariadas existentes (especificamente as de Li-Kaleyski e Bartoli-Stanica) usando equivalência linear. Além disso, prova a inequivalência em relação às funções APN de Gold ( $x^{2^i+1}$ ) analisando os grupos de automorfismo linear ( $Aut_L(F)$ ) e mostrando que eles não podem ser conjugados no grupo linear geral.

Contribuições e Resultados Principais

Construção de Permutações APN: O artigo apresenta uma grande família de permutações APN para espaços vetoriais finitos de dimensão $n=3m$ onde $m$ é ímpar. As funções são definidas como:
$F(x, y, z) = (x^{\sigma+1} + ay^\sigma z + bx^\sigma y + cx^\sigma y, \quad ay^{\sigma+1} + z^\sigma x + bz^\sigma y + cx^\sigma y, \quad z^{\sigma+1} + x^\sigma y)$
onde $\sigma = 2^k$ , $a, b, c \in \mathbb{F}_q$ , e $a \neq 0$ .
Uniformidade Diferencial: Os autores provam que, se a equação polinomial $ax^{\sigma^2+\sigma+1} + bx^{\sigma+1} + cx + 1 = 0$ não tiver solução em $\mathbb{F}_q$ , a uniformidade diferencial de $F$ é $2d$ (onde $d = \gcd(k, m)$ ). Consequentemente, quando $d=1$ e $m$ é ímpar, $F$ é uma permutação APN.
Tamanho do Conjunto Imagem: O artigo caracteriza o tamanho do conjunto imagem dessas funções. Se $m/d$ é par, a função é $(2d+1)$ -para-um em $\mathbb{F}_q^3 \setminus \{0\}$ . Se $m/d$ é ímpar, a função é bijetora em $\mathbb{F}_q^3$ .
Unificação de Famílias Existentes: Os autores demonstram que várias famílias recentemente descobertas de funções APN trivariadas (Li-Kaleyski e Bartoli-Stanica) são linearmente equivalentes a instâncias específicas de sua família proposta (obtidas definindo parâmetros específicos $a, b, c$ ). Isso fornece uma explicação unificada e elementar para essas construções, evitando as complexas distinções de casos e cálculos de resultantes assistidos por computador usados em provas anteriores.
Inequivalência às Funções de Gold: O artigo prova que, para $m > 2$ e $m \neq 6$ , as funções APN construídas são CCZ-inequivalentes às funções APN de Gold. Isso é estabelecido mostrando que seus grupos de automorfismo linear não são conjugados em $GL(3m, 2)$.

Significado e Alegações
O artigo alega fornecer uma "grande família" de permutações APN em toda dimensão ímpar divisível por três, abordando a questão em aberto das bijeções APN para dimensões pares. O significado reside em:

Generalidade: A construção produz comprovadamente um número exponencial de funções APN mutuamente inequivalentes dentro da classe de mapas multiprojetivos.
Simplificação: As provas são descritas como "livres de computador, muito mais curtas e puramente elementares" em comparação com trabalhos anteriores, oferecendo um quadro unificado para entender várias funções APN trivariadas.
Novos Exemplos: A família é mostrada como contendo exemplos que são inequivalentes a funções APN conhecidas (incluindo funções de Gold), expandindo o cenário conhecido de primitivas criptográficas.

Os autores notam que, embora os espectros de Walsh sejam conhecidos para o caso onde $m/d$ é par, determinar o espectro de Walsh para as permutações APN (onde $m$ é ímpar) permanece um problema em aberto. Eles também identificam a classificação de funções semi-quadráticas homogêneas que levam a bijeções projetivas como uma direção natural para pesquisas futuras.