🔢 mathematics

Bent Functions and the Completed Maiorana-McFarland Class

Questo articolo esamina i risultati fondamentali e i recenti progressi nella progettazione e nell'analisi delle funzioni bent booleane, concentrandosi specificamente sulla loro relazione con la classe completata di Maiorana-McFarland.

Autori originali: Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin

Pubblicato 2026-08-25

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Nell'architettura nascosta della moderna sicurezza digitale, esiste un tipo speciale di oggetto matematico noto come funzione bent. Queste non sono dispositivi fisici o entità biologiche, ma piuttosto regole complesse per l'elaborazione di dati binari — stringhe di uno e zero che formano la base di tutta la comunicazione informatica. Immaginate un vasto paesaggio di possibili regole, dove la maggior parte è prevedibile e facile da analizzare. Le funzioni bent si collocano al vertice della imprevedibilità, stando il più lontano possibile da qualsiasi schema semplice e lineare. A causa di questa estrema irregolarità, esse sono strumenti preziosi per proteggere i dati e per i codici di correzione degli errori, agendo come il rumore caotico che impedisce agli intercettatori di trovare un segnale. Per decenni, i matematici hanno saputo come costruire una specifica e ben compresa famiglia di queste funzioni, un gruppo chiamato in onore dei ricercatori che le hanno descritte per la prima volta. Questa famiglia, spesso chiamata classe Maiorana-McFarland, ha servito come principale progetto per la creazione di funzioni bent, proprio come un piano architettonico standard per costruire una casa. Tuttavia, una domanda persistente ha tormentato il campo: sono questi progetti standard l'unico modo per costruire tali funzioni, o esistono altri design più strani che non abbiamo ancora scoperto?

Un team di ricercatori ha ora affrontato in modo esaustivo questa questione, esaminando l'intero panorama delle funzioni bent per vedere come esse si relazionino con quella famiglia standard. Il loro lavoro conferma che i progetti noti, pur essendo utili, rappresentano solo una minuscola frazione delle possibilità totali. Nel caso specifico di funzioni con otto variabili, le ricerche informatiche hanno rivelato che il numero totale di funzioni bent è astronomicamente grande, circa due alla potenza di cento e sei. In netto contrasto, il numero di funzioni che possono essere costruite utilizzando lo standard progetto Maiorana-McFarland è stimato essere al massimo due alla potenza di ottantauno. Questo enorme divario suggerisce che la stragrande maggioranza delle funzioni bent sia fondamentalmente diversa da quelle che siamo stati in grado di costruire esplicitamente. L'obiettivo dei ricercatori era mappare il territorio tra questi due estremi, identificando nuovi metodi per costruire funzioni bent che non rientrino certamente nel vecchio stampo e comprendendo le ragioni strutturali per cui esse sono così diverse.

Il saggio inizia esaminando due famiglie specifiche di funzioni bent, note come classi C e D, che sono state progettate per modificare il progetto standard. Queste famiglie introducono piccole, deliberate modifiche alla formula standard, aggiungendo schemi specifici all'output. I ricercatori hanno indagato se queste modifiche fossero sufficienti a spingere le funzioni risultanti fuori dalla famiglia standard. Hanno scoperto che, sotto certe condizioni, queste funzioni modificate sono effettivamente distinte. Ad esempio, se la permutazione sottostante utilizzata nella costruzione possiede specifiche proprietà algebriche — essenzialmente, se manca di certe simmetrie nascoste — la funzione bent risultante non può essere trasformata nuovamente nella forma standard. Gli autori hanno fornito regole chiare e testabili per determinare quando una funzione appartiene a queste nuove famiglie esotiche e quando rimane intrappolata in quella vecchia. Hanno anche esplorato le "superclassi", che combinano diversi tipi di modifiche, scoprendo che mentre alcune combinazioni funzionano, altre non riescono a produrre funzioni bent, rivelando l'equilibrio delicato richiesto per mantenere il necessario livello di imprevedibilità.

Oltre a queste famiglie specifiche, i ricercatori hanno esaminato funzioni costruite utilizzando la struttura moltiplicativa dei campi finiti, spesso descritte usando termini di traccia. Queste sono funzioni in cui l'output dipende dalla somma di un numero elevato a una specifica potenza. Lo studio evidenzia che molte di queste funzioni, in particolare quelle basate su determinati esponenti, sono provabilmente esterne alla famiglia standard. I ricercatori hanno utilizzato un test matematico specifico basato sulle derivate del secondo ordine — un modo per misurare come la variazione del tasso di cambiamento della funzione stessa cambi — per provare che queste funzioni mancano della regolarità strutturale presente nella classe standard. Hanno anche esaminato funzioni che agiscono come indicatori per altri importanti oggetti matematici, come le funzioni quasi perfette non lineari, mostrando che questi indicatori possiedono spesso le proprietà uniche e non standard delle funzioni bent che risiedono al di fuori delle famiglie note.

Un tema centrale della ricerca è il concetto di "indice di linearità", che può essere pensato come una misura di quanto una funzione assomigli a un semplice schema lineare. Le funzioni Maiorana-McFarland standard hanno un alto indice di linearità, il che significa che possono essere scomposte in grandi pezzi affini semplici. I ricercatori hanno identificato una nuova categoria di funzioni con l'indice di linearità minimo possibile, che chiamano "ottimali". Queste funzioni sono l'opposto di quelle standard; sono così irregolari che non possono essere semplificate in grandi blocchi affini affatto. Il saggio dettaglia come costruire queste funzioni ottimali e prova che esse sono fondamentalmente diverse dalla classe standard. Studiando gli "M-sottospazi" — particolari sottostrutture geometriche all'interno del dominio della funzione che rivelano la sua simmetria sottostante — gli autori hanno mostrato che queste funzioni ottimali possiedono una struttura unica e minimale che le funzioni standard semplicemente non possiedono.

La survey approfondisce anche un quadro più ampio e flessibile chiamato classe Maiorana-McFarland generalizzata. Questo framework permette funzioni che sono costruite partendo da pezzi affini di dimensioni variabili, anziché dalla dimensione fissa utilizzata nella classe standard. I ricercatori hanno caratterizzato esattamente quando una funzione in questa classe più ampia rimane all'interno della famiglia standard e quando ne esce. Hanno scoperto che, scegliendo attentamente i blocchi costruttivi, si possono creare funzioni che sono "quasi" standard ma comunque distinte, così come funzioni che sono completamente aliene alla famiglia standard. Il saggio conclude elencando diversi problemi aperti, riconoscendo che, sebbene abbiano mappato porzioni significative di questo territorio matematico, la piena enumerazione di tutte le funzioni bent rimane un mistero. Essi sfidano i futori ricercatori a trovare altre famiglie infinite di queste funzioni esotiche e a comprendere le precise strutture algebriche che le rendono uniche, assicurando che il campo continui a evolversi oltre i limiti dei progetti originali.

Sintesi Tecnica: Funzioni Bent e la Classe di Maiorana-McFarland Completata

Enunciato del Problema
Le funzioni booleane bent, introdotte da Rothlaus, rappresentano una classe fondamentale di funzioni in un numero pari di variabili che raggiungono la massima non linearità (massima distanza dalle funzioni affini). Mentre la classe di Maiorana-McFarland (M) e la sua versione completata ( $M^\#$ ) costituiscono la famiglia esplicita di funzioni bent più approfonditamente compresa, recenti evidenze computazionali indicano una significativa discrepanza tra il numero totale di funzioni bent e quelle appartenenti a $M^\#$ . Nello specifico, nella dimensione 8, il numero totale di funzioni bent è approssimativamente $2^{106}$ , mentre il numero di funzioni equivalenti a Maiorana-McFarland è stimato al massimo in $2^{81}$ . Questa osservazione motiva il problema centrale di questa survey: caratterizzare le funzioni bent che giacciono al di fuori della classe completata di Maiorana-McFarland ( $M^\#$ ), comprenderne le strutture algebriche e sviluppare metodi di costruzione espliciti per tali funzioni. Il documento si concentra sul "problema dell'esclusione": determinare l'intersezione di varie classi di funzioni bent con $M^\#$ e identificare le condizioni sotto le quali le funzioni sono provabilmente al di fuori di questa classe.

Metodologia
Il documento impiega una metodologia di survey esaustiva, sintetizzando i risultati fondamentali e i recenti progressi nella progettazione e nell'analisi delle funzioni booleane bent. L'approccio tecnico si basa fortemente su:

Caratterizzazione Algebrica: Utilizzo del criterio della derivata del secondo ordine (Lemma 1.2) per caratterizzare l'appartenenza a $M^\#$ . Una funzione appartiene a $M^\#$ se e solo se esiste un sottospazio $U$ di dimensione $m$ tale che tutte le derivate del secondo ordine $D_a D_b f$ si annullano per $a, b \in U$ .
Indice di Linearità e Sottospazi M: Analisi dell' "indice di linearità" ($ind(f)$), definito come la dimensione massima di un sottospazio M (un sottospazio in cui le derivate del secondo ordine si annullano). Le funzioni con $ind(f) = n/2$ appartengono a $M^\#$ , mentre quelle con indici minimi ($ind(f)=1$) sono definite $\ell$ -ottimali.
Costruzioni Secondarie: Investigazione di come operazioni quali somme dirette/indirette, concatenazioni (2-concatenazione e 4-concatenazione) e l'aggiunta di termini di traccia o indicatori di sottospazi influenzino l'appartenenza a $M^\#$ .
Framework Generalizzati: Estensione dell'analisi dalla classica classe $M$ ( $r=s=n/2$ ) alla classe di Maiorana-McFarland Generalizzata (GMM) ( $Mr,s$ ), dove $f(x,y) = x \cdot \phi(y) + h(y)$ con $x \in \mathbb{F}_2^r, y \in \mathbb{F}_2^s$ e $r \neq s$ .

Contributi Chiave e Risultati

Classi C e D di Carlet: Il documento dettaglia le classi C e D, che modificano la forma di Maiorana-McFarland aggiungendo indicatori di sottospazi vettoriali.
- Classe C: Funzioni della forma $x \cdot \pi(y) + 1_{L^\perp}(x)$ . Gli autori riassumono le condizioni sufficienti sulla permutazione $\pi$ e sul sottospazio $L$ (proprietà (C) specifica) che garantiscono che la funzione sia bent e al di fuori di $M^\#$ . Un risultato chiave riguarda le permutazioni le cui componenti mancano di strutture lineari non nulle.
- Classe D e $D_0$ : Funzioni della forma $x \cdot \pi(y) + 1_{E_1}(x)1_{E_2}(y)$ e la sottoclasse $D_0$ ( $x \cdot \pi(y) + \delta_0(x)$ ). Il documento fornisce una caratterizzazione completa di $D_0 \cap M^\#$ , mostrando che per le permutazioni quadratiche, l'appartenenza dipende dal fatto che la permutazione sia affine su un iperpiano affine. Per gradi superiori, le funzioni sono spesso al di fuori di $M^\#$ .
- Superclassi: La survey esamina le superclassi (SC, CD, SD) formate combinando gli indicatori. Identifica che, mentre alcune combinazioni (come SC) producono funzioni bent al di fuori di $M^\#$ , altre (come SD) non riescono affatto a produrre funzioni bent.
Termini di Traccia e la Proprietà $P_\tau$ :
- Il documento recensisce le funzioni bent monomiali, binomiali e correlate definite tramite termini di traccia (ad esempio, esponenti di Dillon e Kasami). Conferma che molte di esse, in particolare quelle con specifici esponenti Niho, si trovano al di fuori di $M^\#$ .
- Una parte significativa è dedicata alla proprietà $P_\tau$ , che riguarda l'aggiunta di combinazioni polinomiali di termini di traccia a una funzione bent. Il documento dettaglia come la proprietà $P_\tau$ , caratterizzata dall'annullamento delle derivate del secondo ordine della funzione duale, permetta la costruzione di famiglie infinite di funzioni bent al di fuori di $M^\#$ che non sono coperte dalle classi C o D.
Classe di Maiorana-McFarland Generalizzata (GMM):
- Il documento introduce la classe GMM ( $Mr,s$ ) e la sua versione completata. Caratterizza la natura bent in questa classe utilizzando "insiemi bent" e "funzioni bent parzialmente definite".
- Quasi Maiorana-McFarland ( $k=1$ ): Vengono analizzate le funzioni con indice di linearità $n/2 - 1$ . Il documento distingue tra partizioni "triviali", "non-proper" e "proper" del dominio, mostrando che specifiche partizioni "proper" generano funzioni bent al di fuori di $M^\#$ .
- Funzioni $\ell$ -ottimali: La survey discute le funzioni con indice di linearità minimo ($ind(f)=1$), notando che queste sono l'"opposto" delle funzioni Maiorana-McFarland. Vengono evidenziate le costruzioni che coinvolgono permutazioni con proprietà (P1) (derivate del secondo ordine non nulle) come metodo per generare tali funzioni.
Sottospazi M e Costruzioni Secondarie:
- Il documento fornisce un'analisi algebrica e combinatoria profonda dei sottospazi M. Stabilisce limiti sul numero di massimi sottospazi M e collega tali limiti alla classificazione delle funzioni bent.
- Presenta condizioni necessarie e sufficienti affinché le costruzioni secondarie (somma diretta, somma indiretta, 2- e 4-concatenazione) risultino in funzioni al di fuori di $M^\#$ . In particolare, dimostra che la 4-concatenazione di una funzione bent al di fuori di $M^\#$ con una funzione bent arbitraria genera una nuova funzione bent al di fuori di $M^\#$ .

Significato
Il documento si posiziona come una survey esaustiva che colma il divario tra la ben compresa classe di Maiorana-McFarland e il vasto spazio, in gran parte non classificato, delle funzioni bent. La sua importanza primaria risiede nel:

Sistematizzare l'Esclusione: Fornire un quadro unificato per determinare quando le funzioni bent cadono al di fuori di $M^\#$ , andando oltre gli esempi ad hoc verso caraterizzazioni strutturali basate su indici di linearità e sottospazi M.
Espandere i Metodi di Costruzione: Dettagliare metodi espliciti (C, D, $P_\tau$ , GMM) per generare famiglie infinite di funzioni bent al di fuori di $M^\#$ , affrontando la scarsità di esempi noti in dimensioni fisse.
Chiarire la Struttura Algebrica: Introdurre e perfezionare concetti come l'indice di linearità e i sottospazi M come strumenti fondamentali per comprendere le proprietà algebriche delle funzioni bent e la loro relazione con la gerarchia generalizzata di Maiorano-McFarland.
Identificare Problemi Aperti: Il documento si conclude elencando numerosi problemi aperti, tra cui l'esatta enumerazione delle classi di equivalenza EA in $M^\#$ , l'estensione di queste teorie alle funzioni bent $p$ -arie e la costruzione di insiemi differenziali al di fuori della classe di McFarland.

Gli autori mantengono un tono modesto, riconoscendo che, sebbene siano stati fatti progressi significativi nell'identificazione di funzioni al di fuori di $M^\#$ , l'enumerazione totale delle funzioni bent e una classificazione completa delle loro strutture algebriche rimangono sfide aperte. Il lavoro funge da riferimento fondamentale per i ricercatori che mirano a progettare funzioni booleane con proprietà di non linearità specificamente rilevanti dal punto di vista crittografico che non possono essere catturate dalla standard costruzione di Maiorana-McFarland.

Articoli simili