2025-11-22T00:52:16.221665

A Symmetric-Key Cryptosystem Based on the Burnside Ring of a Compact Lie Group

Ghanem
Classical linear ciphers, such as the Hill cipher, operate on fixed, finite-dimensional modules and are therefore vulnerable to straightforward known-plaintext attacks that recover the key as a fully determined linear operator. We propose a symmetric-key cryptosystem whose linear action takes place instead in the Burnside ring $A(G)$ of a compact Lie group $G$, with emphasis on the case $G=O(2)$. The secret key consists of (i) a compact Lie group $G$; (ii) a secret total ordering of the subgroup orbit-basis of $A(G)$; and (iii) a finite set $S$ of indices of irreducible $G$-representations, whose associated basic degrees define an involutory multiplier $k\in A(G)$. Messages of arbitrary finite length are encoded as finitely supported elements of $A(G)$ and encrypted via the Burnside product with $k$. For $G=O(2)$ we prove that encryption preserves plaintext support among the generators $\{(D_1),\dots,(D_L),(SO(2)),(O(2))\}$, avoiding ciphertext expansion and security leakage. We then analyze security in passive models, showing that any finite set of observations constrains the action only on a finite-rank submodule $W_L\subset A(O(2))$, and we show information-theoretic non-identifiability of the key from such data. Finally, we prove the scheme is \emph{not} IND-CPA secure, by presenting a one-query chosen-plaintext distinguisher based on dihedral probes.
academic

Un Sistema Crittografico a Chiave Simmetrica Basato sull'Anello di Burnside di un Gruppo di Lie Compatto

Informazioni Fondamentali

  • ID Articolo: 2510.10901
  • Titolo: A Symmetric-Key Cryptosystem Based on the Burnside Ring of a Compact Lie Group
  • Autore: Ziad Ghanem
  • Classificazione: cs.CR (Crittografia e Sicurezza), math.RA (Anelli e Algebre)
  • Data di Pubblicazione: 13 ottobre 2025 (preprint arXiv)
  • Link Articolo: https://arxiv.org/abs/2510.10901

Riassunto

I cifrari lineari tradizionali (come il cifrario di Hill) operano su moduli a dimensione finita fissa, risultando quindi vulnerabili ad attacchi diretti con testo in chiaro noto, dove l'attaccante può recuperare la chiave dell'operatore lineare completamente determinata mediante metodi di algebra lineare. Questo articolo propone un sistema crittografico a chiave simmetrica in cui le operazioni lineari avvengono nell'anello di Burnside A(G) di un gruppo di Lie compatto G, con focus particolare sul caso G=O(2). La chiave è composta da tre componenti: (i) un gruppo di Lie compatto G; (ii) un ordine totale segreto di una base di orbite di sottogruppi di A(G); (iii) un insieme finito S di indici di rappresentazioni irriducibili G, i cui gradi fondamentali associati definiscono un moltiplicatore involutorio k∈A(G). Messaggi di lunghezza finita arbitraria sono codificati come elementi a supporto finito di A(G) e cifrati mediante il prodotto di Burnside con k.

Contesto di Ricerca e Motivazione

Contesto del Problema

  1. Fragilità dei Cifrari Lineari Tradizionali: I cifrari lineari classici come il cifrario di Hill operano in uno spazio a dimensione finita fissa, permettendo agli attaccanti di costruire sistemi di equazioni lineari raccogliendo un numero sufficiente di coppie testo in chiaro-testo cifrato, recuperando così completamente la chiave.
  2. Necessità della Crittografia Post-Quantistica: La minaccia del calcolo quantistico spinge i ricercatori a cercare primitive crittografiche basate su assunzioni teoriche non tradizionali, inclusi schemi basati sulla teoria dei gruppi e sulla teoria dei grafi.
  3. Limitazioni Fondamentali delle Piattaforme a Dimensione Finita: Sebbene i sistemi crittografici algebrici esistenti offrano alternative importanti, operano ancora su piattaforme a dimensione finita, presentando lacune concettuali—un numero sufficiente di coppie testo in chiaro-testo cifrato può vincolare completamente l'operatore chiave.

Motivazione della Ricerca

La motivazione centrale di questo articolo è superare i limiti dell'impostazione a dimensione finita, trasferendo le operazioni di cifratura a moduli di rango infinito—l'anello di Burnside di gruppi di Lie compatti—evitando così teoricamente le debolezze fondamentali dei cifrari lineari tradizionali.

Contributi Principali

  1. Propone un nuovo sistema crittografico simmetrico basato sull'anello di Burnside: Applica per la prima volta l'anello di Burnside di gruppi di Lie compatti alla crittografia, in particolare nel caso del gruppo O(2).
  2. Dimostra la proprietà di preservazione del supporto: Per G=O(2), dimostra che il processo di cifratura preserva il supporto del testo in chiaro nei generatori {(D₁),...,(D_L),(SO(2)),(O(2))}, evitando l'espansione del testo cifrato e le fughe di sicurezza.
  3. Stabilisce l'analisi di sicurezza nel modello passivo: Dimostra che qualsiasi insieme di osservazioni finito può vincolare solo le operazioni su un sottomodulo di rango finito W_L⊂A(O(2)), mostrando l'indistinguibilità della chiave dal punto di vista della teoria dell'informazione da dati finiti.
  4. Dimostra l'insicurezza IND-CPA: Attraverso un distinguitore a query singola basato su sondaggio diedrale, dimostra che lo schema non soddisfa la sicurezza IND-CPA.

Dettagli Metodologici

Definizione del Compito

Progettare uno schema di cifratura a chiave simmetrica dove:

  • Input: Messaggi di lunghezza finita arbitraria
  • Output: Elementi cifrati nell'anello di Burnside
  • Vincoli: Sfruttare la struttura infinito-dimensionale per resistere agli attacchi tradizionali di algebra lineare

Fondamenti Teorici dell'Anello di Burnside

Costruzione dell'Anello di Burnside

Per un gruppo di Lie compatto G, l'anello di Burnside A(G) è definito come:

  • Base: L'insieme delle classi di coniugio di sottogruppi Φ₀(G) = {(H) : H ≤ G, W(H) finito}
  • Struttura: Modulo libero su Z: A(G) = ZΦ₀(G)
  • Prodotto: Prodotto di Burnside definito mediante conteggio di orbite

Anello di Burnside di O(2)

Per G = O(2), gli elementi base includono:

  • (O(2)): Classe di coniugio del gruppo stesso
  • (SO(2)): Classe di coniugio del gruppo ortogonale speciale
  • (Dₖ): Classi di coniugio di sottogruppi diedrali finiti, k ≥ 1

Le regole di prodotto sono mostrate nella tabella seguente:

·(O(2))(SO(2))(Dₘ)
(O(2))(O(2))(SO(2))(Dₘ)
(SO(2))(SO(2))2(SO(2))0
(Dₖ)(Dₖ)02(D_l), l=gcd(k,m)

Progettazione del Sistema Crittografico

Struttura della Chiave

La chiave è composta dalla terna (G,O,S):

  1. Gruppo G: Gruppo di Lie compatto, come G = O(2)
  2. Ordine O: Ordine totale segreto degli elementi base Φ₀(G)
  3. Insieme di Indici di Rappresentazione S: Insieme finito S = {k₁,k₂,...,kₘ}

Costruzione dell'Elemento Chiave

Dall'insieme S si costruisce l'elemento chiave: k=∏j∈Sdeg⁡Vjk = \prod_{j \in S} \deg_{V_j}

dove deg_ è il grado fondamentale della j-esima rappresentazione irriducibile. Per O(2):

  • deg_ = (O(2)) (rappresentazione banale)
  • deg_ = (O(2)) - (Dₘ) (rappresentazioni non banali)

Protocollo di Cifratura/Decifratura

  1. Preprocessamento: Conversione dei dati grezzi in vettore intero p⃗ ∈ Z^L
  2. Codifica ad Anello: Utilizzo dell'ordine segreto O per mappare il vettore a p ∈ A(G)
  3. Cifratura: Calcolo del testo cifrato c = p · k
  4. Trasmissione: Invio del testo cifrato a supporto finito
  5. Decifratura: Poiché k è involutorio, calcolo p = c · k
  6. Decodifica: Recupero dei dati originali

Punti di Innovazione Tecnica

  1. Piattaforma Infinito-Dimensionale: Superamento dei limiti a dimensione finita, operando in moduli di rango infinito
  2. Proprietà Involutoria: L'elemento chiave k soddisfa k² = (O(2)), semplificando il processo di decifratura
  3. Preservazione del Supporto: La cifratura non aumenta l'indice diedrale massimo del testo in chiaro, evitando l'espansione del testo cifrato

Analisi Teorica

Teorema di Preservazione del Supporto

Proposizione 3.1: Sia il testo in chiaro p = Σᵢ₌₁ᴸ aᵢ(Dᵢ), se la chiave k è il prodotto di gradi fondamentali arbitrari, allora il testo cifrato c = p·k è anch'esso un elemento del sottomodulo Z{(D₁),...,(D_L)}.

Punti Chiave della Dimostrazione:

  • (Dᵢ)·(O(2)) = (Dᵢ)
  • (Dᵢ)·(Dₘ) = 2(D_{gcd(i,m)})
  • Poiché gcd(i,m) ≤ i ≤ L, il supporto del risultato non esce dall'intervallo originale

Analisi di Sicurezza Passiva

Finestra di Osservazione Finita

Qualsiasi insieme di osservazioni finito {pⱼ,cⱼ} è limitato a un sottomodulo di rango finito: WL:=Z[{(D1),...,(DL)}]⊂A(O(2))W_L := \mathbb{Z}[\{(D_1),...,(D_L)\}] \subset A(O(2))

Indistinguibilità della Chiave

Proposizione 4.1: Sia S = {s₁,...,sₘ} l'insieme chiave, q un numero primo con q > L. Costruendo S' = {s₁q,...,sₘq}, allora k_S e k_{S'} generano la stessa trasformazione lineare su W_L.

Corollario 4.1: Per qualsiasi insieme finito di osservazioni in W_L, esistono infiniti insiemi chiave distinti coerenti con le osservazioni; la chiave è indistinguibile dal punto di vista della teoria dell'informazione.

Vulnerabilità agli Attacchi con Testo in Chiaro Scelto

Attacco di Sondaggio Diedrale

Per una query p = (Dₓ), il testo cifrato è: cx=(Dx)⋅kS=(Dx)+∑n≥12αS(n)(Dgcd(x,n))c_x = (D_x) \cdot k_S = (D_x) + \sum_{n≥1} 2α_S(n)(D_{gcd(x,n)})

dove α_S(n) è determinato dalla formula della Proposizione 2.1.

Proposizione 4.2: Per qualsiasi due insiemi chiave distinti S₀ ≠ S₁, esiste x ∈ ℕ tale che (Dₓ)·k_{S₀} ≠ (Dₓ)·k_{S₁}.

Distinguitore a Query Singola:

  1. Calcolo di β_{S₀}(x) e β_{S₁}(x)
  2. Selezione di x che soddisfa β_{S₀}(x) ≠ β_{S₁}(x)
  3. Query di p = (Dₓ), determinazione della chiave in base ai coefficienti

Valutazione della Sicurezza

Vantaggi

  1. Resistenza agli Attacchi Passivi: Sotto attacchi con testo cifrato e testo in chiaro noto, la chiave possiede indistinguibilità dal punto di vista della teoria dell'informazione
  2. Assenza di Espansione del Testo Cifrato: La proprietà di preservazione del supporto evita l'allargamento del testo cifrato
  3. Innovazione Teorica: Primo utilizzo di strumenti di topologia algebrica in crittografia

Limitazioni

  1. Non Soddisfa IND-CPA: La costruzione lineare deterministica non può raggiungere l'indistinguibilità standard
  2. Limitazioni Pratiche: La struttura matematica complessa potrebbe influenzare l'efficienza dell'implementazione pratica
  3. Scenari di Applicazione Limitati: Principalmente applicabile a scenari che richiedono sicurezza passiva ma possono accettare cifratura deterministica

Lavori Correlati

Cifrari Lineari Tradizionali

  • Cifrario di Hill e sue varianti
  • Analisi della vulnerabilità delle trasformazioni lineari a dimensione finita

Crittografia Post-Quantistica

  • Sistemi crittografici con mappature di gruppi di permutazioni (PGM)
  • Cifrari a blocchi simmetrici basati sulla teoria dei grafi
  • Metodi di albero di generazione minima (MST) e matrice di adiacenza

Crittografia Algebrica

  • Applicazioni della teoria dei gruppi in crittografia
  • Teoria della rappresentazione e teoria del grado equivariante

Conclusioni e Discussione

Conclusioni Principali

  1. Costruzione riuscita di un sistema crittografico simmetrico basato sull'anello di Burnside infinito-dimensionale
  2. Dimostrazione di sicurezza teorica nel modello di attacco passivo
  3. Evidenziazione dei limiti fondamentali degli schemi lineari deterministici

Direzioni Future

  1. Estensioni Non-Deterministiche: Introduzione di randomizzazione per evitare attacchi CPA
  2. Altri Gruppi di Lie: Esplorazione delle proprietà crittografiche di diversi gruppi di Lie compatti
  3. Ottimizzazione dell'Implementazione: Sviluppo di algoritmi efficienti per le operazioni dell'anello di Burnside
  4. Schemi Ibridi: Combinazione di tecniche crittografiche tradizionali per migliorare l'applicabilità pratica

Valutazione Approfondita

Innovatività

  • Avanzamento Teorico: Primo utilizzo della teoria dell'anello di Burnside in crittografia
  • Innovazione Concettuale: Superamento dei limiti fondamentali della piattaforma a dimensione finita
  • Profondità Matematica: Integrazione di topologia algebrica, teoria della rappresentazione e crittografia

Contributi Tecnici

  • Dimostrazioni matematiche rigorose e analisi teorica
  • Quadro di valutazione della sicurezza dettagliato
  • Descrizione chiara dei meccanismi di attacco e difesa

Valore Pratico

  • Fornisce nuove prospettive per la crittografia post-quantistica
  • Dimostra il potenziale della teoria matematica pura nelle applicazioni
  • Fornisce un caso di studio per comprendere i limiti della cifratura deterministica

Limitazioni

  • Non soddisfa le definizioni di sicurezza standard della crittografia moderna
  • La complessità dell'implementazione potrebbe essere elevata
  • Gli scenari di applicazione sono relativamente limitati

Questo articolo rappresenta un interessante tentativo di ricerca interdisciplinare tra crittografia e matematica pura, che, sebbene presenti limitazioni in termini di applicabilità pratica, fornisce contributi teorici preziosi allo sviluppo del campo.