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

Ein symmetrisches Kryptosystem basierend auf dem Burnside-Ring einer kompakten Lie-Gruppe

Grundlegende Informationen

  • Papier-ID: 2510.10901
  • Titel: A Symmetric-Key Cryptosystem Based on the Burnside Ring of a Compact Lie Group
  • Autor: Ziad Ghanem
  • Klassifizierung: cs.CR (Kryptographie und Sicherheit), math.RA (Ringe und Algebren)
  • Veröffentlichungsdatum: 13. Oktober 2025 (arXiv-Preprint)
  • Papierlink: https://arxiv.org/abs/2510.10901

Zusammenfassung

Traditionelle lineare Kryptosysteme (wie die Hill-Chiffre) operieren auf fest definierten endlichdimensionalen Modulen und sind daher anfällig für direkte Known-Plaintext-Attacken, bei denen Angreifer durch lineare Algebraverfahren den vollständig bestimmten linearen Operatorschlüssel wiederherstellen können. Dieses Papier präsentiert ein symmetrisches Kryptosystem, bei dem lineare Operationen im Burnside-Ring A(G) einer kompakten Lie-Gruppe G durchgeführt werden, mit Fokus auf den Fall G=O(2). Der Schlüssel besteht aus drei Komponenten: (i) einer kompakten Lie-Gruppe G; (ii) einer geheimen Totalordnung einer Umlaufbahnbasis von Untergruppen von A(G); (iii) einer endlichen Menge S von Indizes irreduzibler G-Darstellungen, deren zugehörige fundamentale Grade einen Involutionsmultiplikator k∈A(G) definieren. Beliebig lange Nachrichten werden als endlich getragene Elemente von A(G) kodiert und durch Multiplikation mit k im Burnside-Produkt verschlüsselt.

Forschungshintergrund und Motivation

Problemhintergrund

  1. Schwäche traditioneller linearer Kryptosysteme: Klassische lineare Kryptosysteme wie die Hill-Chiffre operieren in festem endlichdimensionalem Raum, was es Angreifern ermöglicht, durch Sammlung ausreichend vieler Klartext-Geheimtext-Paare ein lineares Gleichungssystem aufzubauen und damit den Schlüssel vollständig wiederherzustellen.
  2. Anforderungen der Post-Quanten-Kryptographie: Die Bedrohung durch Quantencomputer treibt Forscher an, kryptographische Primitive zu suchen, die auf nicht-traditionellen zahlentheoretischen Annahmen basieren, einschließlich Schemata basierend auf Gruppentheorie und Graphentheorie.
  3. Grundlegende Einschränkungen endlichdimensionaler Plattformen: Obwohl existierende algebraische Kryptosysteme wichtige Alternativen bieten, operieren sie dennoch auf endlichdimensionalen Plattformen mit konzeptionellen Schwachstellen – ausreichend viele Klartext-Geheimtext-Paare können den Schlüsseloperator vollständig einschränken.

Forschungsmotivation

Die Kernmotivation dieses Papiers ist es, die Einschränkungen der endlichdimensionalen Einstellung zu überwinden, indem Verschlüsselungsoperationen auf unendlich rangige Module – den Burnside-Ring kompakter Lie-Gruppen – verlagert werden, um theoretisch die grundlegenden Schwächen traditioneller linearer Kryptosysteme zu vermeiden.

Kernbeiträge

  1. Vorschlag eines neuen symmetrischen Kryptosystems basierend auf dem Burnside-Ring: Erstmalige Anwendung des Burnside-Rings einer kompakten Lie-Gruppe auf die Kryptographie, insbesondere für den Fall der O(2)-Gruppe.
  2. Beweis der Träger-Erhaltungseigenschaft: Für G=O(2) wird bewiesen, dass der Verschlüsselungsprozess den Träger des Klartexts in den Generatoren {(D₁),...,(D_L),(SO(2)),(O(2))} bewahrt, was Geheimtext-Expansion und Sicherheitslecks vermeidet.
  3. Etablierung der Sicherheitsanalyse im passiven Modell: Es wird bewiesen, dass jede endliche Beobachtungsmenge nur Operationen auf einem endlich rangigen Untermodul W_L⊂A(O(2)) einschränken kann, und es wird die informationstheoretische Ununterscheidbarkeit des Schlüssels aus endlichen Daten gezeigt.
  4. Beweis der IND-CPA-Unsicherheit: Durch einen auf Dieder-Sondierung basierenden Single-Query-Chosen-Plaintext-Distinguisher wird bewiesen, dass das Schema die IND-CPA-Sicherheit nicht erfüllt.

Methodische Details

Aufgabendefinition

Entwurf eines symmetrischen Verschlüsselungsschemas, wobei:

  • Eingabe: Beliebig lange Nachrichten endlicher Länge
  • Ausgabe: Verschlüsselte Elemente im Burnside-Ring
  • Einschränkungen: Nutzung der unendlichdimensionalen Struktur zur Widerstandsfähigkeit gegen traditionelle lineare Algebraangriffe

Theoretische Grundlagen des Burnside-Rings

Konstruktion des Burnside-Rings

Für eine kompakte Lie-Gruppe G wird der Burnside-Ring A(G) definiert als:

  • Grundlage: Die Menge der Konjugationsklassen von Untergruppen Φ₀(G) = {(H) : H ≤ G, W(H) endlich}
  • Struktur: Freies Z-Modul A(G) = ZΦ₀(G)
  • Produkt: Burnside-Produkt definiert durch Umlaufbahnzählung

Burnside-Ring von O(2)

Für G = O(2) umfassen die Grundelemente:

  • (O(2)): Konjugationsklasse der Gruppe selbst
  • (SO(2)): Konjugationsklasse der speziellen orthogonalen Gruppe
  • (Dₖ): Konjugationsklassen endlicher Diederuntergruppen, k ≥ 1

Die Produktregeln sind in der folgenden Tabelle dargestellt:

·(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)

Kryptosystem-Design

Schlüsselstruktur

Der Schlüssel besteht aus dem Tripel (G,O,S):

  1. Gruppe G: Kompakte Lie-Gruppe, wie G = O(2)
  2. Ordnung O: Geheime Totalordnung der Grundelemente Φ₀(G)
  3. Darstellungsindex-Menge S: Endliche Menge S = {k₁,k₂,...,kₘ}

Konstruktion des Schlüsselelements

Konstruktion des Schlüsselelements aus der Menge S: k=∏j∈Sdeg⁡Vjk = \prod_{j \in S} \deg_{V_j}

wobei deg_ der fundamentale Grad der j-ten irreduziblen Darstellung ist. Für O(2):

  • deg_ = (O(2)) (triviale Darstellung)
  • deg_ = (O(2)) - (Dₘ) (nicht-triviale Darstellung)

Verschlüsselungs-/Entschlüsselungsprotokoll

  1. Vorverarbeitung: Umwandlung der Rohdaten in einen Ganzzahlvektor p⃗ ∈ Z^L
  2. Ring-Kodierung: Verwendung der geheimen Ordnung O zur Abbildung des Vektors auf p ∈ A(G)
  3. Verschlüsselung: Berechnung des Geheimtexts c = p · k
  4. Übertragung: Versand des endlich getragenen Geheimtexts
  5. Entschlüsselung: Da k eine Involution ist, Berechnung von p = c · k
  6. Dekodierung: Wiederherstellung der Originaldaten

Technische Innovationspunkte

  1. Unendlichdimensionale Plattform: Überwindung der endlichdimensionalen Einschränkung durch Operationen auf unendlich rangigen Modulen
  2. Involutionseigenschaft: Das Schlüsselelement k erfüllt k² = (O(2)), was den Entschlüsselungsprozess vereinfacht
  3. Träger-Erhaltung: Verschlüsselung erhöht nicht den maximalen Dieder-Index des Klartexts und vermeidet damit Geheimtext-Expansion

Theoretische Analyse

Träger-Erhaltungssatz

Proposition 3.1: Sei der Klartext p = Σᵢ₌₁ᴸ aᵢ(Dᵢ), und sei der Schlüssel k ein beliebiges Produkt fundamentaler Grade. Dann ist der Geheimtext c = p·k auch ein Element des Untermoduls Z{(D₁),...,(D_L)}.

Beweisskizze:

  • (Dᵢ)·(O(2)) = (Dᵢ)
  • (Dᵢ)·(Dₘ) = 2(D_{gcd(i,m)})
  • Da gcd(i,m) ≤ i ≤ L, überschreitet der resultierende Träger nicht den ursprünglichen Bereich

Sicherheitsanalyse im passiven Modell

Endliches Beobachtungsfenster

Jede endliche Beobachtungsmenge {pⱼ,cⱼ} ist auf ein endlich rangiges Untermodul beschränkt: WL:=Z[{(D1),...,(DL)}]⊂A(O(2))W_L := \mathbb{Z}[\{(D_1),...,(D_L)\}] \subset A(O(2))

Schlüssel-Ununterscheidbarkeit

Proposition 4.1: Sei S = {s₁,...,sₘ} die Schlüsselmenge, q eine Primzahl mit q > L. Konstruiere S' = {s₁q,...,sₘq}. Dann erzeugen k_S und k_{S'} auf W_L die gleiche lineare Transformation.

Korollar 4.1: Für jede endliche Beobachtungsmenge in W_L existieren unendlich viele verschiedene Schlüsselmengen, die mit der Beobachtung konsistent sind. Der Schlüssel ist im informationstheoretischen Sinne ununterscheidbar.

Anfälligkeit gegenüber Chosen-Plaintext-Attacken

Dieder-Sondierungs-Attacke

Für eine Abfrage p = (Dₓ) ist der Geheimtext: 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)})

wobei α_S(n) durch die in Proposition 2.1 angegebene Formel bestimmt wird.

Proposition 4.2: Für beliebige zwei verschiedene Schlüsselmengen S₀ ≠ S₁ existiert x ∈ ℕ, so dass (Dₓ)·k_{S₀} ≠ (Dₓ)·k_{S₁}.

Single-Query-Distinguisher:

  1. Berechnung von β_{S₀}(x) und β_{S₁}(x)
  2. Wahl von x, das β_{S₀}(x) ≠ β_{S₁}(x) erfüllt
  3. Abfrage von p = (Dₓ), Bestimmung des Schlüssels anhand der Koeffizienten

Sicherheitsbewertung

Vorteile

  1. Widerstand gegen passive Attacken: Unter Geheimtext- und Known-Plaintext-Attacken besitzt der Schlüssel informationstheoretische Ununterscheidbarkeit
  2. Keine Geheimtext-Expansion: Die Träger-Erhaltungseigenschaft vermeidet Geheimtext-Vergrößerung
  3. Theoretische Innovation: Erstmalige Einführung algebraisch-topologischer Werkzeuge in die Kryptographie

Einschränkungen

  1. Nicht IND-CPA-sicher: Deterministische lineare Konstruktionen können die Standard-Ununterscheidbarkeit nicht erreichen
  2. Praktische Einschränkungen: Die komplexe mathematische Struktur kann die Implementierungseffizienz beeinträchtigen
  3. Begrenzte Anwendungsszenarien: Hauptsächlich geeignet für Szenarien, die passive Sicherheit erfordern, aber deterministische Verschlüsselung akzeptieren

Verwandte Arbeiten

Traditionelle lineare Kryptosysteme

  • Hill-Chiffre und ihre Varianten
  • Schwächenanalyse endlichdimensionaler linearer Transformationen

Post-Quanten-Kryptographie

  • Permutationsgruppen-Mapping (PGM) Kryptosysteme
  • Symmetrische Blockchiffren basierend auf Graphentheorie
  • Methoden mit minimalem Spannbaum (MST) und Adjazenzmatrizen

Algebraische Kryptographie

  • Anwendungen der Gruppentheorie in der Kryptographie
  • Darstellungstheorie und äquivariante Gradtheorie

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Erfolgreiche Konstruktion eines symmetrischen Kryptosystems basierend auf dem unendlichdimensionalen Burnside-Ring
  2. Demonstration theoretischer Sicherheit unter passiven Attacken
  3. Beweis der grundlegenden Einschränkungen deterministischer linearer Schemata

Zukünftige Richtungen

  1. Nicht-deterministische Erweiterungen: Einführung von Randomisierung zur Vermeidung von CPA-Attacken
  2. Andere Lie-Gruppen: Erforschung der kryptographischen Eigenschaften verschiedener kompakter Lie-Gruppen
  3. Implementierungsoptimierung: Entwicklung effizienter Burnside-Ring-Operationsalgorithmen
  4. Hybridschema: Kombination mit traditionellen kryptographischen Techniken zur Verbesserung der Praktikabilität

Tiefgehende Bewertung

Innovativität

  • Theoretischer Durchbruch: Erstmalige Anwendung der Burnside-Ring-Theorie auf die Kryptographie
  • Konzeptionelle Innovation: Überwindung der grundlegenden Einschränkungen endlichdimensionaler Plattformen
  • Mathematische Tiefe: Integration von algebraischer Topologie, Darstellungstheorie und Kryptographie

Technische Beiträge

  • Strenge mathematische Beweise und theoretische Analysen
  • Detailliertes Sicherheitsanalysegerüst
  • Klare Beschreibung von Angriffsszenarien und Abwehrmechanismen

Praktischer Wert

  • Neue Perspektiven für die Post-Quanten-Kryptographie
  • Demonstration des Potenzials reiner mathematischer Theorie in Anwendungen
  • Fallstudie zum Verständnis der Einschränkungen deterministischer Verschlüsselung

Einschränkungen

  • Erfüllt nicht die modernen kryptographischen Standardsicherheitsdefinitionen
  • Die Implementierungskomplexität könnte erheblich sein
  • Anwendungsszenarien sind relativ begrenzt

Dieses Papier stellt einen interessanten Versuch der interdisziplinären Forschung zwischen Kryptographie und reiner Mathematik dar. Obwohl es praktische Einschränkungen aufweist, trägt es wertvoll zur theoretischen Entwicklung des Feldes bei.