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)인 경우에 중점을 두고 있습니다. 키는 세 부분으로 구성됩니다: (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)

암호 시스템 설계

키 구조

키는 삼중쌍 (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₁에 대해, (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. 혼합 방안: 전통 암호학 기법과 결합하여 실용성 향상

심층 평가

혁신성

  • 이론적 돌파: 번사이드 환 이론을 암호학에 처음으로 적용
  • 개념적 혁신: 유한 차원 플랫폼의 근본적 제한 극복
  • 수학적 깊이: 대수 위상, 표현론 및 암호학의 융합

기술적 기여

  • 엄밀한 수학적 증명 및 이론 분석
  • 상세한 보안성 평가 프레임워크
  • 명확한 공격 및 방어 메커니즘 설명

실용적 가치

  • 양자 후 암호학에 새로운 관점 제시
  • 순수 수학 이론의 응용 가능성 시연
  • 결정론적 암호화의 제한 이해에 기여

제한사항

  • 현대 암호학의 표준 보안 정의 미충족
  • 구현 복잡도가 높을 수 있음
  • 응용 시나리오가 상대적으로 제한적

본 논문은 암호학과 순수 수학의 교차 연구에 있어 흥미로운 시도를 나타내며, 실용성에서는 제한이 있지만 해당 분야의 이론적 발전에 가치 있는 기여를 제공합니다.