🔢 mathematics

Bent Functions and the Completed Maiorana-McFarland Class

Este artigo faz um levantamento de resultados fundamentais e avanços recentes no design e análise de funções booleanas bent, focando especificamente em sua relação com a classe Maiorana-McFarland completada.

Autores originais: Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin

Publicado 2026-08-25

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin

Artigo original sob licença CC BY 4.0 (http://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 um tipo especial de objeto matemático conhecido como função bent. Estas não são dispositivos físicos ou entidades biológicas, mas sim regras complexas para o processamento de dados binários — sequências de uns e zeros que formam a base de toda a comunicação computacional. Imagine uma vasta paisagem de regras possíveis, onde a maioria é previsível e fácil de analisar. As funções bent situam-se no pico dessa imprevisibilidade, afastando-se o máximo possível de qualquer padrão simples e linear. Devido a essa extrema irregularidade, elas são ferramentas valiosas para proteger dados em criptografia e códigos de correção de erros, atuando como o ruído caótico que impede que espiões encontrem um sinal. Por décadas, matemáticos souberam como construir uma família específica e bem compreendida dessas funções, um grupo nomeado em homenagem aos pesquisadores que as descreveram pela primeira vez. Esta família, frequentemente chamada de classe Maiorana-McFarland, tem servido como o principal modelo para a criação de funções bent, tal como um plano arquitetônico padrão para construir uma casa. No entanto, uma questão persistente tem assombrado o campo: seriam esses projetos padrão a única maneira de construir tais funções, ou existem outros designs mais estranhos que ainda não descobrimos?

Uma equipe de pesquisadores realizou agora um olhar abrangente sobre esta questão, examinando todo o panorama das funções bent para ver como elas se relacionam com essa família padrão. O trabalho deles confirma que os modelos conhecidos, embora úteis, representam apenas uma fração minúscula das possibilidades totais. No caso específico de funções com oito variáveis, buscas computacionais revelaram que o número total de funções bent é astronomicamente grande, aproximadamente dois elevado à centésima e sexta potência. Em forte contraste, o número de funções que podem ser construídas usando o padrão da classe Maiorana-McFarland é estimado em, no máximo, dois elevado à oitenta e primeira potência. Essa enorme lacuna sugere que a vasta maioria das funções bent é fundamentalmente diferente daquelas que fomos capazes de construir explicitamente. O objetivo dos pesquisadores era mapear o território entre esses dois extremos, identificando novos métodos para construir funções bent que definitivamente não se encaixam no molde antigo e compreendendo as razões estruturais pelas quais elas são tão diferentes.

O artigo começa examinando duas famílias específicas de funções bent, conhecidas como classes C e D, que foram projetadas para modificar o modelo padrão. Estas famílias introduzem pequenas mudanças deliberadas na fórmula padrão, adicionando padrões específicos à saída. Os pesquisadores investigaram se essas modificações eram suficientes para empurrar as funções resultantes para fora da família padrão. Eles descobriram que, sob certas condições, essas funções modificadas são, de fato, distintas. Por exemplo, se a permutação subjacente usada na construção possui propriedades algébicas específicas — essencialmente, se carece de certas simetrias ocultas — a função bent resultante não pode ser transformada de volta para a forma padrão. Os autores forneceram regras claras e testáveis para determinar quando uma função pertence a estas novas famílias exóticas e quando permanece presa na antiga. Eles também exploraram "superclasses", que combinam diferentes tipos de modificações, descobrindo que, embora algumas combinações funcionem, outras falham em produzir funções bent, revelando o equilíbrio delicado necessário para manter o nível de imprevisibilidade necessário.

Além dessas famílias específicas, os pesquisadores observaram funções construídas usando a estrutura multiplicativa de corpos finitos, frequentemente descritas usando termos de traço. Estas são funções onde a saída depende da soma de um número elevado a uma potência específica. O estudo destaca que muitas dessas funções, particularmente aquelas baseadas em certos expoentes, são comprovadamente externas à família padrão. Os pesquisadores utilizaram um teste matemático específico envolvendo derivadas de segunda ordem — uma forma de medir como a própria taxa de variação da função muda — para provar que essas funções carecem da regularidade estrutural encontrada na classe padrão. Eles também examinaram funções que atuam como indicadores para outros objetos matemáticos importantes, como funções quase perfeitamente não lineares, mostrando que esses indicadores frequentemente possuem as propriedades únicas e não padronizadas das funções bent que residem fora das famílias conhecidas.

Um tema central da pesquisa é o conceito de um "índice de linearidade", que pode ser pensado como uma medida de quanto uma função se assemelha a um padrão linear simples. As funções Maiorana-McFarland padrão possuem um alto índice de linearidade, o que significa que podem ser decompostas em grandes partes afins simples. Os pesquisadores identificaram uma nova categoria de funções com o índice de linearidade mínimo possível, que eles chamam de "otimizadas". Estas funções são o oposto das padrão; são tão irregulares que não podem ser simplificadas em blocos afins de grande escala de forma alguma. O artigo detalha como construir essas funções otimizadas e prova que elas são fundamentalmente diferentes da classe padrão. Ao estudar os "subespaços-M" — subestruturas geométricas especiais dentro do domínio da função que revelam sua simetria subjacente — os autores mostraram que essas funções otimizadas possuem uma estrutura única e mínima que as funções padrão simplesmente não possuem.

O levantamento também explora um quadro mais amplo e flexível chamado classe Maiorana-McFarland generalizada. Este framework permite funções que são construídas a partir de partes afins de tamanhos variados, em vez de apenas o tamanho fixo usado na classe padrão. Os pesquisadores caracterizaram exatamente quando uma função nesta classe mais ampla permanece dentro da família padrão e quando ela sai dela. Eles descobriram que, ao escolher cuidadosamente os blocos de construção, é possível criar funções que são "quase" padrão, mas ainda assim distintas, bem como funções que são completamente alienígenas à família padrão. O artigo conclui listando vários problemas em aberto, reconhecendo que, embora tenham mapeado partes significativas deste território matemático, a enumeração total de todas as funções bent permanece um mistério. Eles desafiam futuros pesquisadores a encontrar mais famílias infinitas dessas funções exóticas e a compreender as estruturas algébricas precisas que as tornam únicas, garantindo que o campo continue a evoluir além das limitações dos planos originais.

Resumo Técnico: Funções Bent e a Classe de Maiorana-McFarland Completada

Enunciado do Problema
As funções booleanas bent, introduzidas por Rothaus, representam uma classe fundamental de funções em um número par de variáveis que alcançam não linearidade máxima (distância máxima de funções afins). Embora a classe de Maiorana-McFarland (M) e sua versão completada ( $M^\#$ ) constituam a família explícita de funções bent mais minuciosamente compreendida, evidências computacionais recentes indicam uma discrepância significativa entre o número total de funções bent e aquelas pertencentes a $M^\#$ . Especificamente, na dimensão 8, o número total de funções bent é aproximadamente $2^{106}$ , enquanto o número de funções equivalentes a Maiorana-McFarland é estimado em, no máximo, $2^{81}$ . Esta observação motiva o problema central deste levantamento: caracterizar funções bent que residem fora da classe de Maiorana-McFarland completada ( $M^\#$ ), compreender suas estruturas algébricas e desenvolver métodos de construção explícitos para tais funções. O artigo foca no "problema da exclusão" — determinar a interseção de várias classes de funções bent com $M^\#$ e identificar condições sob as quais funções são comprovadamente fora desta classe.

Metodologia
O artigo emprega uma metodologia de levantamento abrangente, sintetizando resultados fundamentais e avanços recentes no design e análise de funções booleanas bent. A abordagem técnica baseia-se fortemente em:

Caracterização Algébrica: Utilizando o critério de derivada de segunda ordem (Lema 1.2) para caracterizar a pertinência em $M^\#$ . Uma função pertence a $M^\#$ se, e somente se, existe um subespaço de dimensão $m$ , $U$ , tal que todas as derivadas de segunda ordem $D_a D_b f$ se anulem para $a, b \in U$ .
Índice de Linearidade e Subespaços M: Analisando o "índice de linearidade" ($ind(f)$), definido como a dimensão máxima de um subespaço M (um subespaço onde as derivadas de segunda ordem se anulam). Funções com $ind(f) = n/2$ pertencem a $M^\#$ , enquanto aquelas com índices mínimos ($ind(f)=1$) são denominadas $\ell$ -ótimas.
Construções Secundárias: Investigando como operações como somas direta/indireta, concatenações (2 e 4-concatenação) e a adição de termos de traço ou indicadores de subespaços afetam a pertinência em $M^\#$ .
Estruturas Generalizadas: Estendendo a análise da classe clássica $M$ ( $r=s=n/2$ ) para a classe Maiorana-McFarland Generalizada (GMM) ( $Mr,s$ ), onde $f(x,y) = x \cdot \phi(y) + h(y)$ com $x \in \mathbb{F}_2^r, y \in \mathbb{F}_2^s$ e $r \neq s$ .

Principais Contribuições e Resultados

Classes C e D de Carlet: O artigo detalha as classes C e D, que modificam a forma de Maiorana-McFarland adicionando indicadores de subespaços vetoriais.
- Classe C: Funções da forma $x \cdot \pi(y) + 1_{L^\perp}(x)$ . Os autores resumem as condições suficientes sobre a permutação $\pi$ e o subespaço $L$ (especificamente a propriedade (C)) que garantem que a função seja bent e esteja fora de $M^\#$ . Um resultado chave envolve permutações cujos componentes carecem de estruturas lineares não nulas.
- Classe D e $D_0$ : Funções da forma $x \cdot \pi(y) + 1_{E_1}(x)1_{E_2}(y)$ e a subclasse $D_0$ ( $x \cdot \pi(y) + \delta_0(x)$ ). O artigo fornece uma caracterização completa de $D_0 \cap M^\#$ , mostrando que, para permutações quadráticas, a pertinência depende de se a permutação é afim em um hiperplano afim. Para graus superiores, as funções são frequentemente externas a $M^\#$ .
- Superclasses: O levantamento examina superclasses (SC, CD, SD) formadas pela combinação de indicadores. Identifica-se que, embora algumas combinações (como SC) gerem funções bent fora de $M^\#$ , outras (como SD) falham em produzir funções bent inteiramente.
Termos de Traço e a Propriedade $P_\tau$ :
- O artigo revisa funções bent monomiais, binomiais e relacionadas definidas via termos de traço (ex: expoentes de Dillon e Kasami). Confirma-se que muitas destas, particularmente aquelas com expoentes Niho específicos, residem fora de $M^\#$ .
- Uma parte significativa é dedicada à propriedade $P_\tau$ , que envolve adicionar combinações polinomiais de termos de traço a uma função bent. O artigo detalha como a propriedade $P_\tau$ , caracterizada pelo desaparecimento das derivadas de segunda ordem da função dual, permite a construção de famílias infinitas de funções bent fora de $M^\#$ que não são cobertas pelas classes C ou D.
Classe Maiorana-McFarland Generalizada (GMM):
- O artigo introduz a classe GMM ( $Mr,s$ ) e sua versão completada. Caracteriza a bentness nesta classe usando "conjuntos bent" e "funções bent parcialmente definidas".
- Quase Maiorana-McFarland ( $k=1$ ): Funções com índice de linearidade $n/2 - 1$ são analisadas. O artigo distingue entre partições "triviais", "não-próprias" e "próprias" do domínio, mostrando que partições próprias específicas resultam em funções bent fora de $M^\#$ .
- Funções $\ell$ -ótimas: O levantamento discute funções com índice de linearidade mínimo ($ind(f)=1$), observando que estas são o "oposto" das funções Maiorana-McFarland. Construções envolvendo permutações com a propriedade (P1) (derivadas de segunda ordem não nulas) são destacadas como um método para gerar tais funções.
Subespaços M e Construções Secundárias:
- O artigo fornece uma análise algébrica e combinatória profunda de subespaços M. Estabelece limites para o número de subespaços M maximais e vincula-os à classificação de funções bent.
- Apresenta condições necessárias e suficientes para que construções secundárias (soma direta, soma indireta, 2- e 4-concatenação) resultem em funções fora de $M^\#$ . Notavelmente, prova que a 4-concatenação de uma função bent fora de $M^\#$ com uma função bent arbitrária resulta em uma nova função bent fora de $M^\#$ .

Significância
O artigo posiciona-se como um levantamento abrangente que preenche a lacuna entre a bem compreendida classe Maiorana-McFarland e o vasto espaço, em grande parte não classificado, das funções bent. Sua principal significância reside em:

Sistematizar a Exclusão: Fornecer um framework unificado para determinar quando funções bent caem fora de $M^\#$ , indo além de exemplos ad-hoc para caracterizações estruturais baseadas em índices de linearidade e subespaços M.
Expandir Métodos de Construção: Detalhar métodos explícitos (C, D, $P_\tau$ , GMM) para gerar famílias infinitas de funções bent fora de $M^\#$ , abordando a escassez de exemplos conhecidos em dimensões fixas.
Esclarecer a Estrutura Algébrica: Introduzir e refinar conceitos como o índice de linearidade e subespaços M como ferramentas fundamentais para entender as propriedades algébricas das funções bent e sua relação com a hierarquia generalizada de Maiorana-McFarland.
Identificar Problemas Abertos: O artigo conclui listando inúmeros problemas abertos, incluindo a enumeração exata de classes de equivalência EA em $M^\#$ , a extensão destas teorias para funções bent $p$ -árias e a construção de conjuntos de diferença fora da classe de McFarland.

Os autores mantêm um tom modesto, reconhecendo que, embora progressos significativos tenham sido feitos na identificação de funções fora de $M^\#$ , a enumeração total de funções bent e a classificação completa de suas estruturas algébricas permanecem desafios abertos. O trabalho serve como uma referência fundamental para pesquisadores que visam projetar funções booleanas criptograficamente significativas com propriedades de não linearidade específicas que não podem ser capturadas pela construção padrão de Maiorana-McFarland.

Mais como este