Z-Sigil: A Public-Key Cryptosystem with Chained Selection over a Fiber Bundle of Module-Lattice Keys

Z-Sigil: 모듈 격자 키의 파이버 번들 위에서 체인 선택을 사용하는 공개키 암호체계에 관한 기술 요약

문제 정의
표준적인 공개키 암호체계는 일반적으로 하나의 비밀 키를 고정하여 메시지의 모든 블록을 암호화한다. Z-Sigil은 "사전 생성된 비밀 키 패밀리(family of secret keys)를 어떤 순서로 접근할 것인가를 평문이 결정할 수 있는가?"라는 구조적 질문을 다룬다. 즉, 단일 키의 정적인 적용이 아니라, 키 공간을 통과하는 "워크(walk)"를 생성하는 것이다. 본 논문은 이러한 평문 기반 상태와 격자 키 패밀리를 결합한 구조가 보안성과 정확성을 유지하며 구축될 수 있는지, 그리고 이전의 기하학적 제안들이 평문 스칼라를 의도치 않게 노출했던 함정을 어떻게 피할 수 있는지를 조사한다.

방법론 및 구성
본 구성은 세 가지 뚜렷한 구성 요소로 이루어진다:

1. Module-LWE 기반: 핵심 산술은 모듈 학습 오류(Module-LWE) 가정에 기초한다. 공유된 공적 행렬 $A$와 공적 벡터들의 패밀리 $b_t = A s_t + e_t$가 생성된다. 여기서 $s_t$는 작은 비밀 벡터이며, $e_t$는 작은 오차 벡터이다.
2. 기하학적 추상화 (파이버 번들): 키 패밀리는 유한 기저 $P$(평탄한 카일러 토러스 상의 잉여 점들의 집합) 위의 이산 파이버 번들의 섹션 $\sigma$로 모델링된다. 공개 키는 이 섹션의 노이즈가 섞인 이미지이다. 메시지는 새로운 키를 생성하는 것이 아니라, 기저 $P$ 위에서 "워크" $\gamma$를 추적하며, 각 블록에 대해 어떤 파이버(따라서 어떤 비밀 키 $s_t$)를 사용할지 선택한다.
3. 체인 선택 메커니즘:
   • 상태 초기화: 공적 논스(nonce)가 해시 상태 $x_{-1}$를 초기화한다.
   • 블록 처리: 각 블록 $i$에 대해, 현재 상태 $x_{i-1}$을 해싱하여 키 인덱스 $t_i$를 선택하고 비트 마스크 $\kappa_i$를 도출한다.
   • 암호화: 평문 블록 $m_i$는 마스킹($\mu_i = m_i \oplus \kappa_i$)되며, 선택된 키 $s_{t_i}$를 통해 표준 Lindner–Peikert/Kyber 스타일의 블록 맵을 거쳐 암호문 $(u_i, v_i)$를 생성한다.
   • 상태 업데이트: 복구된 평문 $m_i$(송신자는 알고 있고 수신자에 의해 복구됨)는 다음 키를 결정하기 위해 해시 함수에 다시 입력되어 상태 $x_i$를 업데이트한다.

이는 키 선택의 궤적이 메시지 내용에 의존하게 만드는 종속성을 생성하지만, 키 자체는 암호화 전에는 메시지와 독립적으로 생성된다.

주요 기여
본 논문은 다음과 같은 구체적인 기술적 기여를 한다:

• 기하학적 프레임워크: 평탄한 카일러 토러스 위에서 모듈 격자 키의 이산 파이버 번들을 정의하며, 여기서 비밀 키는 섹션이고 공개 키는 파이버별 엔도모피즘(endomorphism) 하에서의 노이즈 섞인 이미지이다.
• 명시적 사양: 키 생성, 암호화, 복호화를 포함한 완전하고 분리된 사양을 제공하며, 구체적인 블록 맵과 체인 역전 명제(chained-inversion proposition)를 포함한다.
• 정확성 증명: 누적된 노이즈(키 생성 오차와 새로운 암호화 오차로부터 발생)가 특정 임계값 내에 머무를 경우 복호화가 성공함을 증명한다. 디코딩 실패 상한은 특정 키 패밀리 실현(예: 16개 키와 64개 블록에 대해 $< 2^{-192}$)을 조건으로 도출된다.
• 보안 환원: 전체 체인에 대한 조건부 IND-CPA(선택 평문 공격에 대한 구별 불가능성) 환원을 확립한다. 이 환원은 해시 함수를 랜덤 오라클로 모델링하지 않고도 공개 키가 알려진 후 메시지를 선택할 수 있도록 허용한다. 증명은 두 가지 경로를 사용한다: 파이버를 추측하는 방식(비용 $T$) 또는 모든 파이버에 동시에 챌린지를 임베딩하는 방식.
• 부분 노출 분석: 공격자가 키의 부분 집합을 보유한 "직접 접두사(direct-prefix)" 복구 모델에 대한 정확한 확률 법칙을 제공한다. 이는 노출된 키가 평문의 접두사 복구를 허용할 수는 있지만, 체인 구조가 노출된 키 위에서 워크가 지속되지 않는 한 후속 블록의 즉각적인 복구를 방지함을 입증한다.
• 이전 연구의 수정: 평문 스칼라가 공적 방향을 따라 노출되었던 이전의 기하학적 제안의 실패를 명시적으로 식별하고 수정함으로써, 평문이 가산적으로 입력되고 마스킹되도록 하여 스칼라 노출을 방지한다.

결과 및 경계

• 신뢰성: $T=16$개의 키와 $L=64$개의 블록 설정에 대해, 디코딩 실패 확률은 $2^{-192}$ 미만으로 제한된다. 이는 신뢰성 경계이지 보안 수준 추정치가 아니다.
• 보안: 체계의 기밀성은 결정적 모듈-LWE(Decisional Module-LWE) 문제의 난이도에 조건적으로 달려 있다. 환원은 선택된 환원 경로에 따라 곱셈적 손실(예: $T$ 또는 $L$ 인자)을 수반하며, 이는 본 체계가 기저 래티스 문제에 대한 추가적인 가정 없이 특정 구체적 보안 수준(예: 128비트)을 주장하지 않음을 의미한다.
• 노출 제한: 공격자가 키의 비율 $p$를 보유하는 제한된 모델에서, 직접 복구 가능한 블록의 기대치는 캡이 씌워진 기하 분포를 따른다. 그러나 논문은 이것이 후보 메시지 공격이나 알려진 평문을 사용하여 미래 상태를 추론할 수 있는 무제한 공격자를 제한하지는 않는다고 언급한다.

의의 및 주장
본 논문은 Z-Sigil을 새로운 암호 프리미티브나 표준 준수 구현(ML-KEM이 아님)이라기보다, 특정 **구성 아키텍처(composition architecture)**에 대한 연구로 겸허하게 규정한다.

• 인증 없음: 본 체계는 인증이나 선택 암호문(IND-CCA) 보안을 제공하지 않는다.
• 양자 가속 주장 없음: 기하학적 동기는 양자 중첩 개념(Manin 인용)을 참조하지만, 이는 아키텍처 연구를 위한 동기일 뿐, 본 체계가 양자 공격을 방지한다는 주장이 아님을 명시한다.
• 연구 방향: 본 연구는 경로 의존적 기하학을 탐구하기 위한 "테스트베드" 역할을 한다. 현재의 평탄한 기하학(표현으로서의 역할)과 수송(transport) 및 홀로노미(holonomy)를 가진 비자명한 곡률을 가진 미래의 곡률 기하학을 구분하며, 현재의 적분 수송 제약이 노이즈 예산을 보존하기 위한 부호 있는 치환(signed permutations)으로 제한되는 등 매우 엄격함을 언급한다.
• 검증 가능성: 논문은 바이트 프로필, 의사 코드, 기지 응답 벡터(known-answer vectors)를 제공하여 재현성을 강조하며, 수학적 증명과 구현 기록을 별도로 유지한다.

요약하자면, Z-Sigil은 노이즈 예산이 관리되고 기하학적 구조가 평문 스칼라를 의도치 않게 노출하지 않는다면, 사전 생성된 모듈 래티스 키 패밀리에 대한 평문 의존적 워크를 구축할 수 있음을 보여준다. 이는 명시적인 경계 내에서 조건부 기밀성을 갖는 특정 상태 기반, 키 패밀리 기반 암호화 클래스를 위한 엄격한 제안이다.