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

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

基本信息

  • 论文ID: 2510.10901
  • 标题: A Symmetric-Key Cryptosystem Based on the Burnside Ring of a Compact Lie Group
  • 作者: Ziad Ghanem
  • 分类: cs.CR (Cryptography and Security), math.RA (Rings and Algebras)
  • 发表时间: 2025年10月13日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.10901

摘要

传统的线性密码（如Hill密码）在固定的有限维模块上操作，因此容易受到直接的已知明文攻击，攻击者可以通过线性代数方法恢复完全确定的线性算子密钥。本文提出了一种对称密钥密码系统，其线性操作在紧致李群G的Burnside环A(G)中进行，重点关注G=O(2)的情况。密钥由三部分组成：(i) 紧致李群G；(ii) A(G)的子群轨道基的秘密全序；(iii) 不可约G-表示指标的有限集合S，其相关的基本度定义了对合乘子k∈A(G)。任意有限长度的消息被编码为A(G)的有限支撑元素，并通过与k的Burnside乘积进行加密。

研究背景与动机

问题背景

  1. 传统线性密码的脆弱性：经典的线性密码如Hill密码在固定的有限维空间中操作，使得攻击者可以通过收集足够的明文-密文对来构建线性方程组，从而完全恢复密钥。
  2. 后量子密码学需求：量子计算的威胁促使研究者寻找基于非传统数论假设的密码原语，包括基于群论和图论的方案。
  3. 有限维平台的根本限制：现有的代数密码系统虽然提供了重要的替代方案，但仍然在有限维平台上操作，存在概念性漏洞——足够的明文-密文对可以完全约束密钥算子。

研究动机

本文的核心动机是突破有限维设置的限制，将加密操作转移到无穷秩模块——紧致李群的Burnside环中，从而在理论上避免传统线性密码的根本性弱点。

核心贡献

  1. 提出了基于Burnside环的新型对称密码系统：首次将紧致李群的Burnside环应用于密码学，特别是O(2)群的情况。
  2. 证明了支撑保持性质：对于G=O(2)，证明了加密过程保持明文在生成元{(D₁),...,(D_L),(SO(2)),(O(2))}中的支撑，避免了密文扩展和安全泄漏。
  3. 建立了被动模型下的安全性分析：证明了任何有限观察集合只能约束有限秩子模块W_L⊂A(O(2))上的操作，并展示了密钥从有限数据的信息论不可识别性。
  4. 证明了IND-CPA不安全性：通过基于二面体探测的单查询选择明文区分器，证明该方案不满足IND-CPA安全性。

方法详解

任务定义

设计一个对称密钥加密方案，其中：

  • 输入：任意有限长度的消息
  • 输出：在Burnside环中的加密元素
  • 约束：利用无穷维结构抵抗传统的线性代数攻击

Burnside环理论基础

Burnside环的构造

对于紧致李群G，Burnside环A(G)定义为：

  • 基础：子群共轭类的集合Φ₀(G) = {(H) : H ≤ G, W(H)有限}
  • 结构：自由Z-模块A(G) = ZΦ₀(G)
  • 乘积：通过轨道计数定义的Burnside乘积

O(2)的Burnside环

对于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)

密码系统设计

密钥结构

密钥由三元组(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：对于任意两个不同密钥集合S₀ ≠ S₁，存在x ∈ ℕ使得(Dₓ)·k_{S₀} ≠ (Dₓ)·k_{S₁}。

单查询区分器：

  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. 成功构造了基于无穷维Burnside环的对称密码系统
  2. 在被动攻击模型下展现了理论安全性
  3. 证明了确定性线性方案的根本限制

未来方向

  1. 非确定性扩展：引入随机化避免CPA攻击
  2. 其他李群：探索不同紧致李群的密码学性质
  3. 实现优化：开发高效的Burnside环运算算法
  4. 混合方案：结合传统密码学技术提升实用性

深度评价

创新性

  • 理论突破：首次将Burnside环理论应用于密码学
  • 概念创新：突破有限维平台的根本限制
  • 数学深度：融合了代数拓扑、表示论和密码学

技术贡献

  • 严格的数学证明和理论分析
  • 详细的安全性评估框架
  • 清晰的攻击和防御机制描述

实用价值

  • 为后量子密码学提供新思路
  • 展示了纯数学理论在应用中的潜力
  • 为理解确定性加密的限制提供了案例

局限性

  • 不满足现代密码学的标准安全定义
  • 实现复杂度可能较高
  • 应用场景相对有限

该论文代表了密码学与纯数学交叉研究的一个有趣尝试，虽然在实用性上存在局限，但为该领域的理论发展提供了有价值的贡献。