Symmetric measures of pseudorandomness for binary sequences

1. Il Problema

Le misure di pseudocasualità per le sequenze binarie sono fondamentali nell'analisi e nella progettazione dei cifrari a flusso. Due delle misure di complessità più importanti sono la complessità lineare (legata alla lunghezza del registro a scorrimento con retroazione lineare, LFSR) e la complessità 2-adica (legata ai registri a scorrimento con riporto, FCSR).

Finora, la ricerca si è concentrata principalmente sulle versioni "ordinarie" di queste misure. Tuttavia, in contesti crittografici, la sicurezza di una sequenza potrebbe essere compromessa non solo dalla sua struttura originale, ma anche dalla sua inversione (reversal). Sebbene siano stati studiati varianti simmetriche per alcune famiglie specifiche di sequenze periodiche, manca un confronto sistematico tra le misure ordinarie e quelle simmetriche (definite come il minimo tra la misura della sequenza e quella della sua inversione), specialmente nel contesto aperiodico (sequenze finite).

L'obiettivo del paper è colmare questa lacuna, confrontando rigorosamente la complessità lineare e 2-adica ordinaria con le loro controparti simmetriche, sia in ambito periodico che aperiodico.

2. Metodologia

Gli autori adottano un approccio misto che combina:

• Teoria dei Numeri e Algebrica: Utilizzo delle proprietà delle espansioni binarie di numeri primi, del massimo comun divisore e dell'ordine moltiplicativo modulo $p$.
• Analisi Combinatoria e Probabilistica: Studio dei valori attesi (expected values) su famiglie di sequenze binarie casuali di lunghezza $N$.
• Costruzione di Famiglie Specifiche: Creazione di esempi espliciti di sequenze (basate su primi non palindromi e configurazioni di bit specifiche) per dimostrare disuguaglianze strette tra complessità ordinaria e simmetrica.
• Stime Asintotiche: Derivazione di limiti superiori e inferiori per i valori attesi delle complessità simmetriche.

3. Contributi Chiave e Risultati

A. Caso Periodico

1. Complessità 2-adica Simmetrica:

   • Gli autori dimostrano che per sequenze periodiche costruite a partire dalle espansioni binarie di primi non palindromi, la complessità 2-adica simmetrica può essere strettamente inferiore alla complessità 2-adica ordinaria.
   • Viene presentato il Teorema 1: Se $p$ è un primo non palindromico e $q$ è il suo "inverso" binario, è possibile costruire una sequenza periodica di periodo $T$ tale che la sua complessità 2-adica è $\log_2(2^T-1)$, mentre quella simmetrica è ridotta di un fattore $\log_2(q)$.
   • Vengono forniti esempi numerici di coppie di primi reversibili (es. 11 e 13, 23 e 29) e liste di ordini moltiplicativi.

2. Complessità Lineare Simmetrica:

   • Viene fornita una prova diretta (basata sulla definizione di ricorrenza lineare) del fatto che la complessità lineare di una sequenza periodica è invariante sotto inversione.
   • Risultato: Nel caso periodico, $L(S) = L(S^{rev})$. Di conseguenza, la complessità lineare simmetrica coincide esattamente con quella ordinaria ($L_{sym}(S) = L(S)$). Non vi è quindi alcun vantaggio nel considerare la versione simmetrica per la complessità lineare in ambito periodico.

B. Caso Aperiodico (Sequenze Finite)

In questo contesto, le differenze diventano significative e le misure simmetriche rivelano debolezze non rilevate dalle misure ordinarie.

1. Famiglie di Sequenze con Complessità Ridotta:

   • Vengono identificate famiglie esplicite di sequenze finite in cui sia la complessità 2-adica simmetrica che quella lineare simmetrica sono sostanzialmente più piccole delle loro controparti ordinarie.
   • Esempi: Sequenze con una lunga sequenza di zeri seguita da un uno (o viceversa) mostrano che l'inversione può ridurre drasticamente la complessità necessaria per generare la sequenza.

2. Valori Attesi e Ordine di Grandezza:

   • Complessità Razionale e 2-adica: Viene dimostrato (Proposizione 2) che il valore atteso della complessità razionale simmetrica ($E_{rat-sym}$) è inferiore al valore atteso ordinario ($E_{rat}$) di almeno un termine dell'ordine di $N$ (specificamente $3N/8$).
   • Complessità Lineare Esponenziale: Analizzando il valore atteso di $2^{L(S_N)}$, si dimostra che la differenza tra il caso ordinario e quello simmetrico è dell'ordine di $2^{N/2}$. Questo indica che l'effetto della simmetrizzazione è visibile su una scala esponenziale.
   • Limiti Inferiori: Vengono stabiliti limiti inferiori per i valori attesi delle complessità simmetriche (Teoremi 2 e 3), confermando che, sebbene ridotte, rimangono comunque elevate per la maggior parte delle sequenze casuali, ma con un "gap" significativo rispetto al caso ordinario.

3. Confronto Numerico:

   • Le tabelle 3 e 4 nel paper mostrano dati numerici per piccole lunghezze $N$, confermando che la differenza tra i valori attesi cresce rapidamente, supportando l'ipotesi che la differenza sia dell'ordine di $2^{N/2}$.

4. Significato e Implicazioni

• Sicurezza Crittografica: Il lavoro evidenzia che la valutazione della sicurezza di una sequenza pseudocasuale basata solo sulla complessità ordinaria può essere fuorviante. Una sequenza potrebbe apparire sicura (alta complessità ordinaria) ma essere vulnerabile se la sua inversione ha una complessità molto bassa.
• Necessità di Misure Simmetriche: Nel contesto aperiodico (che è quello reale per molti cifrari a flusso che operano su blocchi finiti o flussi non perfettamente periodici), l'uso di misure simmetriche è cruciale per una valutazione accurata della robustezza contro attacchi basati su FCSR e LFSR.
• Distinzione tra Periodico e Aperiodico: Il paper chiarisce una distinzione fondamentale: mentre per le sequenze periodiche la complessità lineare è intrinsecamente simmetrica, la complessità 2-adica e le misure aperiodiche mostrano asimmetrie significative che devono essere considerate nella progettazione di generatori di numeri casuali.

In sintesi, Ren e Winterhof stabiliscono che la "simmetrizzazione" delle misure di complessità non è una mera formalità matematica, ma rivela vulnerabilità strutturali reali, specialmente per le sequenze finite, rendendo necessarie nuove linee guida per la valutazione della pseudocasualità.