Lattice-based extended withdrawability

기술 요약: 격자 기반 확장 가능 철회 서명 (Lattice-based Extended Withdrawability)

문제 정의
디지털 서명은 전통적으로 영속성을 제공한다: 일단 서명되면, 메시지는 서명자의 공개 키 하에서 영구적으로 검증 가능한 상태로 남는다. 그러나 많은 탈중앙화 애플리케이션(예: 제한된 시간 접근, 철회 가능한 계약, 탈중앙화 에스크로)은 서명자가 비밀 키를 노출하거나 다른 서명을 무효화하지 않고도 서명을 철회할 수 있는 능력을 필요로 한다. Liu, Susilo, 그리고 Baek은 확장 가능 철회 서명(extended withdrawable signatures, EWS)을 도입하여 이를 해결하였는데, 이는 실제 서명자가 "확인"하기 전까지 서명을 잠재적 서명자 집합 사이에서 모호하게 유지할 수 있도록 한다. 이들의 구조는 이산 로그 프리미티브(Schnorr 서명 및 1-out-of-N 서명)에 의존한다.

본 논문은 "포스트 퀀텀 갭(post-quantum gap)" 문제를 다룬다: Shor의 알고리즘은 기존 EWS의 기초가 되는 이산 로그 구조를 파괴한다. Dilithium과 같은 격자 기반 서명들이 존재하지만, Liu-Susilo-Baek(LSB) 구조를 격자로 직접 "직역(literal transcription)"하는 것은 구조적 장애물로 인해 실패한다. 구체적으로, LSB 스킴은 서명자의 기여분을 재무작위화(re-randomize)하기 위해 공개 키의 곱셈 이동(multiplicative shifts)을 게시하는 것에 의존한다. 격자 환경(abort가 있는 Fiat-Shamir 방식)에서 이러한 이동은 서명자의 공개 키 $t_i = As_1 + s_2$와 공통 인자 $As_1$를 공유하는 $As_1 s_j$ 형태를 띤다. 이러한 이동값을 게시하는 것은 서명자의 신원을 유출하여 요구되는 모호성을 깨뜨린다.

방법론
저자들은 LSB 방식에서 벗어나, 본 구조를 (Park과 Sealfon의) *클레임 가능한 링 서명(claimable ring signature)*으로 취급하는 새로운 격자 기반 EWS 구조를 제안한다. 공개 키를 명시적으로 재무작위화하려고 시도하는 대신, 이 구조는 EWS의 두 가지 핵심 기능을 분리한다:

1. 모호성(Ambiguity): 블랙박스로 사용되는 익명 1-out-of-N (링) 서명에 의해 제공된다.
2. 확인(Confirmation): 서명자의 클레임(claim)에 의해 제공되며, 이는 철회 가능한 객체에 대한 결합력 있는(binding) 서명과 서명자의 인덱스에 대한 은닉 커밋먼트(hiding commitment)의 개방으로 구성된다.

이 구조는 Fiat-Shamir with aborts 패러다임 위에서 작동하며 세 가지 모듈형 구성 요소에 의존한다:

• 베이스 서명 스킴 (예: no-hint, full-$t$ Dilithium 스타일 스킴).
• 익명 1-out-of-N 서명 (격자 1-out-of-many 증명으로 인스턴스화됨).
• 은닉 및 결합 커밋먼트 스킴 (Ajtai 스타일).

철회 가능한 서명 $\sigma$는 메시지에 대한 링 서명 $\sigma_r$과 서명자의 인덱스에 대한 커밋먼트 $C$, 그리고 공개 키 집합으로 구성된다. 확인을 위해, 서명자는 $C$의 개방 값 $(i, \rho)$를 공개하고, 자신의 베이스 비밀 키로 철회 가능한 객체 $\langle \mu, \pi, \sigma \rangle$ 전체에 서명한다.

주요 기여

1. 보안 모델 정교화: 저자들은 LSB의 보안 모델을 정교화한다.

   • LSB의 "완전성(completeness)" 정의를 은닉 보장을 명시적으로 포착하는 클레임 전까지의 익명성(anonymity-until-claim) 불변성 게임(정의 14)으로 대체한다.
   • 클레임 가능성 건전성(claimability soundness)(정의 16)을 도입하여, 확정된 서명이 고유한 서명자 인덱스에 결합되도록 보장함으로써 공격자가 동일한 서명을 서로 다른 링 멤버에게 귀속시키는 것을 방지한다.
   • 고정된 타겟 인덱스에 대한 *내부 부패 하의 위조 불가능성(unforgeability under insider corruption)*을 정식화하며, 이는 LSB 증명에 존재하는 곱셈 $q_H$ (해시 쿼리) 감소를 피한다.

2. 일반적 구조(Generic Construction): Fiat-Shamir with aborts 패러다임 상의 EWS에 대한 일반적인 구조를 제시한다. 결정적으로, 이 구조는 서명자 유래 값을 명시적으로 전혀 게시하지 않는다. 모호성은 오직 링 서명의 영지식 특성으로부터 도출되며, 추적 가능성은 커밋먼트의 결합성으로부터 도출된다.

3. 불가능성 결과: 본 논문은 LSB의 1-out-of-N 서명(가산 챌린지 분할 사용)을 격자로 직역하는 것이 안전하지 않음을 증명한다(명제 2). 희소 챌레지(sparse challenges)를 사용하는 격자 환경에서, 정직한 서명자가 유효한 챌린지 분할을 생성할 확률은 무시할 만한 수준($2^{-\Omega(n)}$)이며, 완전성을 패치하더라도 시뮬레이션된 트랜스크립트가 실제 트랜스크립트와 구별 불가능하지 않기 때문에 익명성이 실패하게 된다.

4. 완전한 보안 증명: 저자들은 다음 항목들에 대해 (양자) 랜덤 오라클 모델(QROM)에서의 명시적인 게임 기반 환원(reduction)을 제공한다:

   • 정확성(Correctness): 기본 프리미티브의 정확성으로 환원.
   • 확장 가능 철회 가능성(Extended Withdrawability): 커밋먼트의 은닉성(Decisional MLWE) 및 1-out-of-N 스킴의 익명성으로 환원.
   • 위조 불가능성(Unforgeability): 베이스 서명의 EUF-CMA 보안으로 환원 (리와인딩 없이, $q_H$ 손실 없이).
   • 클레임 가능성 건전성(Claimability Soundness): 커밋먼트의 결합성(MSIS)으로 환원.

5. 인스턴스화: 본 스킴은 no-hint, full-$t$ Dilithium 스타일의 베이스 서명과 확립된 격자 1-out-of-many 증명을 사용하여 인스턴스화된다. 논문은 파라미터 선택을 논의하며, HAETAE가 대안적인 베이스가 될 수 있음을 언급한다.

결과
본 논문은 제안된 구조가 다음과 같음을 입증한다:

• 정확하다: 정직한 서명은 압도적인 확률로 검증된다.
• 확장 가능하게 철회 가능하다: 모든 비밀 키를 보유한 공격자라도 서명자가 확인하기 전까지는 링의 어떤 멤버가 철회 가능한 서명을 생성했는지 구별할 수 없다.
• 위조 불가능하다: 타겟 멤버를 제외한 모든 링 멤버의 비밀 키와 서명 오라클에 접근할 수 있는 공격자라도, 새로운 메시지에 대해 확정된 서명을 위조할 수 없다.
• 건전하다: 확정된 서명을 두 명의 서로 다른 서명자에게 귀속시킬 수 없다.

보안은 표준 모듈 격자 가정인 Decisional MLWE, MSIS, SelfTargetMSIS 및 1-out-of-N 증명의 영지식 특성에 기반한다.

의의
본 논문은 최초의 안전한 포스트 퀀티엄 확장 가능 철회 서명을 제공함으로써 그 의의를 주장한다. 이는 공유된 값의 "자유로운 재무작위화"가 결여된 탓에 LSB의 이산 로그 구조를 격자로 직접 이식할 수 없음을 보여준다. 문제를 클레임 가능한 링 서명으로 재구성하고 커밋먼트 기반의 확인 메커니즘을 활용함으로써, 저자들은 다음과 같은 특성을 가진 스킴을 달성하였다:

• 포스트 퀀티즘 보안: 격자 가정을 통해 양자 공격자에 대해 저항력을 갖는다.
• 공개 검증 가능: 지정 검증자 변형과 달리, 누구나 철회 가능한 서명을 검증할 수 있다.
• 모듈성: 보안 증명이 기본 프리미티브의 인터페이스에만 의리하므로, 전체 시스템을 다시 증명할 필요 없이 서로 다른 격자 기반 구성 요소(예: 다른 베이스 서명 또는 링 증명)를 교체할 수 있다.
• 원래 목표에 충실함: 설계는 격자 환경에서의 구조적 결함을 수정하면서도, 원래 LSB 스킴의 기능적 목표와 직관을 보존한다.