🔢 matemática

Constructing Complete Permutations via the D-Class of Locally Crooked Permutations

Este artigo introduz a classe D de permutações sobre $\mathbb{F}_{2^{n+1}}$ para caracterizar e construir permutações completas via conjugações locais, estabelecendo suas propriedades algébricas, limites criptográficos e inequivalência CCZ, ao mesmo tempo em que apresenta algoritmos que enumeram com sucesso novas permutações completas $\delta=4$ .

Autores originais: Li Shuai

Publicado 2026-10-16

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Li Shuai

Artigo original sob licença CC BY 4.0 (https://creativecommons.org/licenses/by/4.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

Na arquitetura oculta da segurança digital moderna, existe uma classe de objetos matemáticos conhecidos como permutações completas. Estas não são meros embaralhamentos aleatórios de números; são rearranjos altamente estruturados onde o ato de mover um item para uma nova posição e o ato de movê-lo para uma posição que é a soma de sua localização antiga e nova resultam em ambos em uma ordem perfeita e não sobreposta. Este requisito duplo é crucial para o design de caixas de substituição, ou S-boxes, que são os componentes primários em sistemas de criptografia que embaralham dados para esconder seu significado. Se esses componentes forem muito previsíveis, a criptografia pode ser quebrada; se forem muito caóticos, tornam-se ineficientes. O desafio para os criptógrafos tem sido, há muito tempo, encontrar o ponto ideal: permutações que sejam complexas o suficiente para resistir a ataques sofisticados, mas estruturadas o suficiente para serem implementadas rapidamente.

Um estudo recente de Li Shuai, da Universidade de Ningxia, aborda este desafio explorando uma família específica dessas permutações através de uma lente de simetria geométrica. A pesquisa foca em uma propriedade chamada "crookedness local" (tortuosidade local), que descreve como uma permutação se comporta quando sua entrada é deslocada por uma quantidade específica. O autor introduz uma nova categoria dessas funções, definida por um padrão específico em como seus resultados mudam. Ao tratar essas funções como elementos de um grupo maior que pode ser transformado por deslocamento, rotação ou troca de partes específicas dos dados, o estudo mapeia um panorama de possibilidades. O objetivo era ver se o movimento dentro deste panorama poderia gerar novas permutações superiores que ofereçam melhor proteção contra a criptoanálise diferencial, um método onde atacantes estudam como pequenas mudanças na entrada afetam a saída para deduzir a chave secreta.

O núcleo do trabalho envolve uma cadeia de construção que começa com uma permutação conhecida e bem comportada e aplica uma série de operações algébricas precisas para criar novas. O autor define um conjunto específico de regras, ou uma "classe-D", que estas permutações devem seguir para permanecerem válidas. Dentro deste conjunto, o pesquisador prova que a coleção de permutações "erguidas" (lifted) — aquelas que foram estendidas de um espaço menor para um espaço maior — possui uma rigidez única. Se alguém tentar alterar uma única permutação usando apenas um tipo de operação, como um simples deslocamento ou uma rotação linear, o resultado geralmente falha em permanecer uma permutação completa válida. No entanto, o estudo demonstra que combinar duas operações diferentes em uma sequência específica quebra essa rigidez. Esta combinação permite ao pesquisador navegar pelo espaço de possibilidades, movendo-se de uma permutação válida para outra sem perder as propriedades essenciais exigidas pela segurança.

Para tornar este quadro teórico prático, o artigo desenvolve dois algoritmos distintos. O primeiro é uma busca de retrocesso (backtracking) que constrói uma permutação completa do zero, garantindo em cada etapa que os requisitos duplos de ordenação sejam atendidos. O segundo é uma busca local gananciosa (greedy local search) que parte de uma permutação existente e tenta melhorá-la aplicando as operações combinadas descritas anteriormente. Este segundo algoritmo atua como um escalador buscando um pico mais alto: ele testa várias pequenas modificações, mas só aceita uma mudança se ela melhorar estritamente a qualidade criptográfica da permutação. A qualidade é medida por dois indicadores principais: uniformidade diferencial, que conta a frequência do pior caso de padrões de saída, e não linearidade, que mede o quão distante a função está de ser uma equação linear simples. Menor uniformidade diferencial e maior não linearidade são, geralmente, melhores para a segurança.

Os pesquisadores testaram estes métodos em um espaço matemático específico de tamanho 32, o que corresponde a um sistema de 5 bits. Partindo de uma permutação linear simples que era conhecida por ser fraca, o algoritmo de busca gananciosa foi executado cem vezes. Os experimentos renderam diversas permutações com uma uniformidade diferencial de 4, uma melhoria significativa em relação ao valor inicial de 32. O estudo também partiu de cem permutações geradas aleatoriamente e aplicou o mesmo processo de busca. Novamente, o algoritmo encontrou consistentemente permutações com uma uniformidade diferencial de 4. Os resultados não foram apenas sobre encontrar números melhores; as novas permutações possuíam "espectros" distintos, ou padrões de frequências de saída, que eram diferentes entre si e em relação ao ponto de partida. Isso prova que o método não produz apenas variações do mesmo objeto, mas descobre genuinamente novas e distintas classes de permutações seguras.

Uma das descobertas mais impressionantes diz respeito à relação entre estas novas permutações e uma classe famosa de funções conhecidas como funções APN (quase perfeitamente não lineares). Historicamente, muitas construções de permutações seguras dependeram de começar com estas funções APN. No entanto, o estudo descobriu que as permutações geradas por este novo método de conjugação local, embora possuam a mesma excelente uniformidade diferencial de 4, são CCZ-inequivalentes àquelas derivadas das abordagens APN clássicas. De fato, uma permutação de referência baseada em uma função APN bem conhecida teve um desempenho inferior neste teste específico, com uma uniformidade diferencial de 8. Isso sugere que o novo método explora uma região diferente do panorama matemático, descobrindo permutações de alta qualidade que eram anteriormente inacessíveis às técnicas de construção padrão.

O artigo conclui propondo uma conjectura baseada na evidência experimental: que todo o espaço destas permutações erguidas está conectado. Em outras palavras, parece ser possível alcançar qualquer permutação válida nesta família a partir de qualquer outra, seguindo um caminho destas modificações locais específicas. Embora esta conectividade não tenha sido matematicamente provada, o fato de o algoritmo de busca encontrar consistentemente soluções de alta qualidade a partir de pontos de partida diversos fornece um forte apoio preliminar para a ideia. O estudo também deixa aberta a questão de se esta família específica de permutações contém funções que sejam ainda mais fortes do que as encontradas, potencialmente atingindo o limite teórico de segurança conhecido como APN. Por enquanto, o trabalho fornece um novo e robusto conjunto de ferramentas para gerar permutações seguras, demonstrando que, ao compreender as simetrias locais destes objetos matemáticos, pode-se construir defesas melhores para o mundo digital.

Resumo Técnico: Construção de Permutações Completas via a Classe-D de Permutações Localmente Tortuosas

Declaração do Problema

O artigo aborda a construção de Permutações Completas (CPs) sobre corpos finitos $\mathbb{F}_{2^n}$ . Uma permutação $f$ é uma CP se tanto $f$ quanto o mapa $x \mapsto f(x) + x$ forem permutações. As CPs são críticas na criptografia, especificamente como blocos de construção para S-boxes no framework de Lai–Massey e para a geração de quadrados latinos ortogonais.

Embora as CPs estejam ligadas a Permutações Localmente Tortuosas (LCPs) sobre $\mathbb{F}_{2^{n+1}}$ via a correspondência de Shuai–Li, os métodos anteriores dependiam de um caminho "função tortuosa $\to$ LCP $\to$ CP". Essa abordagem era restritiva, pois não permitia o movimento livre ou a geração de novas LCPs dentro da própria classe. O artigo busca superar isso trabalhando diretamente dentro da classe LCP para gerar novas CPs através de ações de grupo internas, expandindo assim o espaço de busca por permutações criptograficamente fortes.

Metodologia

1. A Classe-D e a Invariância

O autor introduz a classe-D, definida como o conjunto de permutações $f$ sobre $\mathbb{F}_{2^{n+1}}$ tais que a derivada em uma direção fixa $q_1 = 2^n$ tem uma imagem igual ao complemento de um hiperplano fixo $H = \{x : x_n = 0\}$ .
$D = \{f \in S_q : \text{Im } \Delta_{q_1}f = K\}$
onde $K = \mathbb{F}_{2^{n+1}} \setminus H$ .

O artigo prova que $D$ é fechado sob três ações de grupo específicas:

Translação à Esquerda: $t_a \circ f$ para qualquer $a \in \mathbb{F}_q$ .
Multiplicação à Esquerda: $g \circ f$ para qualquer $g$ no grupo linear geral que preserva $H$ ( $GL_H$ ).
Multiplicação à Direita: $f \circ h$ para qualquer $h$ no centralizador $C$ da involução que troca $H$ e $K$ .

Adicionalmente, a classe é fechada sob translações locais $t_{a,X}$ (translações restritas a um subconjunto $X$ ), desde que $X$ seja uma união de órbitas de um grupo diedral específico gerado pela translação e pela involução conjugada.

2. Rigidez e a Cadeia de Construção

O autor define a subclasse de CP elevada $D^\uparrow \subset D$ , consistindo de permutações em $D$ que atuam como a identidade no complemento $K$ .

Rigidez: O artigo prova que $D^\uparrow$ é "rígida" sob qualquer operação única das propriedades de fechamento acima (translação, multiplicação linear ou multiplicação pelo centralizador). Uma única operação não pode mapear uma CP elevada para outra CP elevada, a menos que seja a identidade.
Cadeia de Construção: Para gerar novas CPs, o autor constrói uma cadeia envolvendo um produto de operações:
$CP \xrightarrow{\text{elevação}} LCP \xrightarrow{\text{translação local}} LCP' \xrightarrow{\text{correção pelo centralizador}} LCP'' \xrightarrow{\text{restrição}} \text{Nova } CP$
Esta cadeia utiliza elementos do centralizador localizados ( $g_{a,X_1}$ e $g_{a,X_2}$ ) para "reparar" o defeito introduzido pelas translações locais, garantindo que o resultado permaneça em $D^\uparrow$ .

3. Conjugações Locais

A construção produz duas conjugações locais específicas, $f_1$ e $f_2$ , definidas no corpo base $\mathbb{F}_{2^n}$ :

$f_1$ : Uma modificação de $f$ em um subconjunto $X_1 \subset H$ , onde $X_1$ é invariante sob um grupo diedral.
$f_2$ : Uma modificação envolvendo o inverso de $f$ em um subconjunto $X_2$ , onde $X_2$ é invariante sob um grupo cíclico.
O artigo fornece condições necessárias e suficientes para que esses mapas modificados permaneçam CPs.

4. Algoritmos

Dois algoritmos são apresentados para implementar a teoria:

Busca de Backtracking Aleatório: Gera CPs aleatórias do zero, mantendo restrições sobre $f(x)$ e $f(x)+x$ .
Busca Local Gananciosa (Greedy): Aplica iterativamente as conjugações locais ( $f_1, f_2$ ) a uma semente CP. Ela aceita movimentos apenas se estes melhorarem estritamente uma função de qualidade baseada no espectro diferencial completo (DDT) e no espectro de Walsh.

Principais Resultados

Contribuições Teóricas

Prova de Invariância: Estabeleceu que a classe-D é invariante sob as especificadas ações de grupo e translações locais.
Teorema de Rigidez: Provou que a subclasse de CP elevada $D^\uparrow$ não pode ser gerada por operações únicas, necessitando da cadeia de construção composta.
Critérios de Inequivalência CCZ: Derivou critérios para determinar quando as novas CPs construídas são CCZ-inequivalentes à semente. Isso depende da verificação se a Tabela de Distribuição Diferencial (DDT) ou o multiconjunto de coeficientes absolutos de Walsh mudam.
Limites Criptográficos: Derivou limites para uniformidade diferencial ( $\delta$ ), não-linearidade ($nl$) e grau algébrico ( $\deg$ ) sob modificações locais. Especificamente, $\delta$ muda em no máximo $2m$ , onde $m$ é o tamanho do subconjunto modificado.

Descobertas Experimentais

Experimentos foram conduzidos em $H \cong \mathbb{F}_{2^5}$ (32 elementos):

Geração de CPs com $\delta=4$ : Partindo de uma semente linear ( $\delta=32$ ) e sementes aleatórias, a busca gananciosa encontrou com sucesso múltiplas permutações completas com uniformidade diferencial $\delta=4$ .
Espectros Distintos: As CPs geradas exibiram espectros diferenciais distintos em relação umas às outras e a uma CP de referência baseada em Dillon (que possuía $\delta=8$ ).
Inequivalência CCZ: Os espectros diferenciais distintos confirmam que a construção produz novas classes de inequivalência CCZ, e não apenas variantes afins da semente.
Evidência de Conectividade: A convergência repetida para distribuições de indicadores semelhantes a partir de diferentes sementes aleatórias fornece evidência preliminar de que o conjunto de CPs elevadas $D^\uparrow$ pode ser conectado sob movimentos de conjugação local.

Significância e Alegações

O artigo afirma fornecer um framework algébrico sistemático para gerar novas permutações completas, explorando a estrutura interna da classe LCP.

Além de Funções Tortuosas: Ao contrário de métodos anteriores dependentes de começar com uma função tortuosa, esta abordagem permite a exploração do próprio espaço LCP para encontrar CPs.
Utilidade Criptográfica: O método produz com sucesso CPs com baixa uniformidade diferencial ( $\delta=4$ ), uma propriedade desejável para S-boxes, que eram anteriormente mais difíceis de construir via a correspondência padrão de funções tortuosas.
Visão Estrutural: A identificação da "rigidez" de $D^\uparrow$ e o papel específico do centralizador em "reparar" translações locais oferece uma compreensão teórica mais profunda da relação entre LCPs e CPs.
Problemas Abertos: O autor enquadra modestamente a conectividade de $D^\uparrow$ e a existência de funções APN dentro desta classe como problemas abertos, sugerindo que, embora os experimentos apoiem a conectividade, uma prova formal é necessária. Eles também observam que, embora os resultados sugiram uma ligação potencial com permutações APN, nenhuma permutação APN foi explicitamente estabelecida neste trabalho.