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

コンパクトリー群のバーンサイド環に基づく対称鍵暗号システム

基本情報

  • 論文ID: 2510.10901
  • タイトル: A Symmetric-Key Cryptosystem Based on the Burnside Ring of a Compact Lie Group
  • 著者: Ziad Ghanem
  • 分類: cs.CR（暗号化とセキュリティ）、math.RA（環と代数）
  • 発表日時: 2025年10月13日（arXivプレプリント）
  • 論文リンク: https://arxiv.org/abs/2510.10901

要旨

従来の線形暗号（Hill暗号など）は固定の有限次元加群上で動作するため、攻撃者が線形代数的手法により完全に決定された線形演算子鍵を復元できる直接的な既知平文攻撃に容易に脆弱である。本論文は、線形演算がコンパクトリー群Gのバーンサイド環A(G)内で実行される対称鍵暗号システムを提案し、G=O(2)の場合に焦点を当てている。鍵は3つの部分から構成される：(i) コンパクトリー群G；(ii) A(G)の部分群軌道基の秘密全順序；(iii) 既約G-表現指標の有限集合S。その関連する基本次数が対合乗数k∈A(G)を定義する。任意の有限長メッセージはA(G)の有限台元素として符号化され、kとのバーンサイド積による乗算を通じて暗号化される。

研究背景と動機

問題背景

  1. 従来の線形暗号の脆弱性：Hill暗号などの古典的線形暗号は固定の有限次元空間で動作するため、攻撃者は十分な平文-暗号文対を収集することで線形方程式系を構築し、鍵を完全に復元できる。
  2. 耐量子暗号の必要性：量子計算の脅威により、研究者は非従来的数論仮定に基づく暗号原始を求めており、群論およびグラフ理論に基づくスキームを含む。
  3. 有限次元プラットフォームの根本的制限：既存の代数暗号システムは重要な代替案を提供するが、依然として有限次元プラットフォーム上で動作し、概念的欠陥が存在する——十分な平文-暗号文対は鍵演算子を完全に制約できる。

研究動機

本論文の核心的動機は、有限次元設定の制限を突破し、暗号化操作を無限秩加群——コンパクトリー群のバーンサイド環——に移行することで、従来の線形暗号の根本的弱点を理論的に回避することである。

核心的貢献

  1. バーンサイド環に基づく新型対称暗号システムの提案：コンパクトリー群のバーンサイド環を暗号学に初めて応用し、特にO(2)群の場合を扱う。
  2. 台保持性質の証明：G=O(2)に対して、暗号化プロセスが生成元{(D₁),...,(D_L),(SO(2)),(O(2))}における平文の台を保持することを証明し、暗号文膨張と安全性漏洩を回避する。
  3. 受動モデル下の安全性分析の確立：任意の有限観測集合が有限秩部分加群W_L⊂A(O(2))上の操作のみを制約でき、有限データからの鍵の情報論的識別不可能性を示す。
  4. IND-CPA非安全性の証明：二面体探査に基づく単一クエリ選択平文区別器を通じて、本スキームがIND-CPA安全性を満たさないことを証明する。

方法の詳細

タスク定義

対称鍵暗号スキームを設計する。ここで：

  • 入力：任意の有限長メッセージ
  • 出力：バーンサイド環内の暗号化元素
  • 制約：無限次元構造を利用して従来の線形代数攻撃に抵抗する

バーンサイド環理論の基礎

バーンサイド環の構成

コンパクトリー群Gに対して、バーンサイド環A(G)は以下のように定義される：

  • 基礎：部分群共役類の集合Φ₀(G) = {(H) : H ≤ G, W(H)は有限}
  • 構造：自由Z-加群A(G) = ZΦ₀(G)
  • 積：軌道計数により定義されるバーンサイド積

O(2)のバーンサイド環

G = O(2)に対して、基礎元素は以下を含む：

  • (O(2))：群自体の共役類
  • (SO(2))：特殊直交群の共役類
  • (Dₖ)：有限二面体部分群の共役類、k ≥ 1

積規則は以下の表に示される：

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

暗号システム設計

鍵構造

鍵は3元組(G,O,S)から構成される：

  1. 群G：コンパクトリー群、例えばG = O(2)
  2. 順序O：基礎元素Φ₀(G)の秘密全順序
  3. 表現指標集合S：有限集合S = {k₁,k₂,...,kₘ}

鍵元素の構成

集合Sから鍵元素を構成する： k=∏j∈Sdeg⁡Vjk = \prod_{j \in S} \deg_{V_j}

ここで、deg_はj番目の既約表現の基本次数である。O(2)に対して：

  • deg_ = (O(2))（自明表現）
  • deg_ = (O(2)) - (Dₘ)（非自明表現）

暗号化/復号化プロトコル

  1. 前処理：生データを整数ベクトルp⃗ ∈ Z^Lに変換
  2. 環符号化：秘密順序Oを使用してベクトルをp ∈ A(G)にマッピング
  3. 暗号化：暗号文c = p · kを計算
  4. 送信：有限台の暗号文を送信
  5. 復号化：kが対合であるため、p = c · kを計算
  6. 復号：元のデータを復元

技術的革新点

  1. 無限次元プラットフォーム：有限次元の制限を突破し、無限秩加群内で動作
  2. 対合性質：鍵元素kはk² = (O(2))を満たし、復号化プロセスを簡略化
  3. 台保持：暗号化は平文の最大二面体指標を増加させず、暗号文膨張を回避

理論的分析

台保持定理

命題3.1：平文をp = Σᵢ₌₁ᴸ aᵢ(Dᵢ)とし、鍵kが任意の基本次数の積であるとする。すると暗号文c = p·kも部分加群Z{(D₁),...,(D_L)}の元である。

証明の要点：

  • (Dᵢ)·(O(2)) = (Dᵢ)
  • (Dᵢ)·(Dₘ) = 2(D_{gcd(i,m)})
  • gcd(i,m) ≤ i ≤ Lであるため、結果の台は元の範囲を超えない

受動安全性分析

有限観測窓

任意の有限観測集合{pⱼ,cⱼ}は有限秩部分加群に制限される： WL:=Z[{(D1),...,(DL)}]⊂A(O(2))W_L := \mathbb{Z}[\{(D_1),...,(D_L)\}] \subset A(O(2))

鍵識別不可能性

命題4.1：S = {s₁,...,sₘ}を鍵集合とし、qを素数でq > Lとする。S' = {s₁q,...,sₘq}を構成すると、k_Sとk_{S'}はW_L上で同じ線形変換を生成する。

系4.1：W_L内の任意の有限観測集合に対して、観測と一致する異なる鍵集合が無限に多く存在し、鍵は情報論的意味で識別不可能である。

選択平文攻撃脆弱性

二面体探査攻撃

クエリp = (Dₓ)に対して、暗号文は： 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)})

ここで、α_S(n)は命題2.1で与えられた公式により決定される。

命題4.2：任意の2つの異なる鍵集合S₀ ≠ S₁に対して、(Dₓ)·k_{S₀} ≠ (Dₓ)·k_{S₁}となるx ∈ ℕが存在する。

単一クエリ区別器：

  1. β_{S₀}(x)とβ_{S₁}(x)を計算
  2. β_{S₀}(x) ≠ β_{S₁}(x)を満たすxを選択
  3. p = (Dₓ)をクエリし、係数に基づいて鍵を決定

安全性評価

利点

  1. 受動攻撃への耐性：暗号文攻撃および既知平文攻撃下で、鍵は情報論的識別不可能性を有する
  2. 暗号文膨張なし：台保持性質は暗号文拡張を回避する
  3. 理論的革新：代数位相学的ツールを暗号学に初めて導入

制限事項

  1. IND-CPAを満たさない：決定的線形構成は標準的不可区別性に到達できない
  2. 実用性の制限：複雑な数学構造は実装効率に影響する可能性がある
  3. 限定的応用シーン：主に受動安全性を要求するが決定的暗号化を受け入れられるシーンに適用可能

関連研究

従来の線形暗号

  • Hill暗号およびその変種
  • 有限次元線形変換の脆弱性分析

耐量子暗号学

  • 置換群マッピング(PGM)暗号システム
  • グラフ理論に基づく対称ブロック暗号
  • 最小全域木(MST)および隣接行列法

代数暗号学

  • 群論の暗号学への応用
  • 表現論および等変次数理論

結論と考察

主要な結論

  1. 無限次元バーンサイド環に基づく対称暗号システムの構成に成功
  2. 受動攻撃モデル下での理論的安全性を実証
  3. 決定的線形スキームの根本的制限を証明

今後の方向性

  1. 非決定的拡張：CPA攻撃を回避するためのランダム化の導入
  2. 他のリー群：異なるコンパクトリー群の暗号学的性質の探索
  3. 実装最適化：効率的なバーンサイド環演算アルゴリズムの開発
  4. ハイブリッドスキーム：従来の暗号学的技術との結合による実用性向上

深度評価

革新性

  • 理論的突破：バーンサイド環理論を暗号学に初めて応用
  • 概念的革新：有限次元プラットフォームの根本的制限を突破
  • 数学的深さ：代数位相学、表現論、暗号学の融合

技術的貢献

  • 厳密な数学的証明と理論的分析
  • 詳細な安全性評価フレームワーク
  • 攻撃および防御メカニズムの明確な記述

実用的価値

  • 耐量子暗号学に新たな視点を提供
  • 純粋数学理論の応用における可能性を実証
  • 決定的暗号化の制限を理解するための事例を提供

制限事項

  • 現代暗号学の標準的安全定義を満たさない
  • 実装複雑度が高い可能性がある
  • 応用シーンが相対的に限定的

本論文は暗号学と純粋数学の交差研究における興味深い試みを代表しており、実用性に制限があるものの、当該分野の理論的発展に価値ある貢献を提供している。