Withdrawability in Fiat-Shamir with aborts constructions

기술 요약: 중단(Aborts)이 있는 피아트-샤미르(Fiat–Shamir)에서의 철회 가능성(Withdrawability)

문제 정의
디지털 서명은 전통적으로 영속성을 제공합니다. 즉, 한 번 생성된 서명은 서명자의 개인키를 손상시키거나 다른 서명을 무효화하지 않고서는 철회할 수 없습니다. 이러한 한계는 참여자가 변화하는 조건에 따라 약속을 철회해야 하는 블록체인 스마트 컨트랙트, 탈중앙화 전자 투표, 에스크로 서비스와 같은 동적인 환경에서 문제를 야기합니다. Liu, Baek, 그리고 Susilo [LBS23]는 서명자가 지정된 검증자에 의해서만 검증 가능한 서명을 생성한 후, 이를 나중에 공개적으로 검증 가능한 서명으로 변환할 수 있게 하는 "철회 가능한 서명(withdrawable signatures)"이라는 프리미티브를 도입했습니다. 그러나 그들의 구성은 양자 공격에 취약한 고전적 가정(이산 로그, 디피-헬먼)에 의존합니다.

본 논문이 다루는 과제는 철회 가능한 서명의 개념을 중단이 있는 피아트-샤미르(Fiat–Shamir with aborts) 패러다임, 특히 Dilithium (ML-DSA) 및 HAETAE와 같은 선도적인 양자 내성 서명 체계의 기반이 되는 패러다임 내에서 포스트 양자 환경으로 확장하는 것입니다. 구체적인 구조적 장애물이 존재합니다. 기존의 Liu–Baek–Susilo 구성은 서명자/검증자 모호성과 지정(designation)을 동시에 달성하기 위해 "자유로운" 디피-헬먼 공유 비밀(shared secret)에 의존합니다. 격자 기반 암호학에는 이와 유사한 저렴하고 효율적인 공유 비밀의 아날로그가 부족하며, 이는 새로운 아키텍처적 접근을 필요로 합니다.

방법론
본 논문은 중단이 있는 피아트-샤미르 패러다임에 기반한 철회 가능한 서명을 위한 일반적인 추상적 구성을 제안한 후, 구체적인 인스턴스화를 수행합니다.

1. 추상적 구성:
   저자들은 KeyGen, WSign(철회 가능 서명), WSVerify(철회 가능 검증), Confirm, 그리고 CVerify의 다섯 가지 알고리즘으로 구성된 프레임워크를 정의합니다.

• 핵심 메커니ism: 이 스킴은 **이인자(two-party) 피아트-샤미르 중단 OR-증명(OR-proof)**을 활용합니다. 철회 가능한 서명은 서명자에 의해 생성된 브랜치(서명자의 비밀키 사용)와 검증자의 브랜치를 모방하기 위해 서명자에 의해 시뮬레이션된 브랜치의 두 가지 분기로 구성됩니다.
• 모호성(Ambiguity): 서명자와 지정된 검증자 모두 유효한 브랜치를 생성할 수 있기 때문에(서명자는 검증자를 시뮬레이션함으로써, 검증자는 서명자를 시뮬레이션함으로써), 제3자에게는 서명의 기원을 구별할 수 없습니다.
• 확인(Confirmation): 서명을 공개적으로 검증 가능하게 만들기 위해, 서명자는 Confirm 알고리즘을 실행합니다. 이 알고리즘은 메시지, 공개키 집합, 그리고 철회 가능한 서명 자체에 대한 표준적인 일반 서명을 생성하여, (거부 샘플링으로 인해 격자 기반 FS-with-aborts에서는 재유도가 불가능한) 공유 무작위성을 다시 유도할 필요 없이 철회 가능한 서명을 서명자의 신원과 결합합니다.

2. 강한 지정 검증자(SDVS) 변형:
   철회 가능한 서명이 공개적으로 검증 가능하지 않도록 보장하기 위해(Liu–Baek–Susilo 모델과 일치하도록), 저자들은 서명의 공개 코어를 공개 키 암호화(PKE) 스킴(구체적으로 ML-KEM/Kyber의 기초가 되는 CPA-secure module-LWE 암호화)을 사용하여 암호화합니다.

• 서명은 지정된 검증자의 공개키와 서명자의 공개키 모두로 암호화됩니다. 이를 통해 검증자는 복호화하여 검증할 수 있고, 서명자는 복호화하여 상태를 유지하며(statelessly) Confirm 연산을 수행할 수 있습니다.
• 이 접근 방식은 디피-헬만 공유 비밀을 명시적 암호화로 대체하며, 이는 현재 격자 기반 비대화형 키 교환(NIKE)이 이 용도로 사용하기에는 너무 비효율적임을 인정한 결과입니다.

3. 구체적 인스턴스화:
   추상적 프레임워크는 no-hint, full-$t$ Dilithium 스타일 구성을 사용하여 인스턴스화됩니다.

• 저자들은 "힌트"($t_1$/$t_0$ 분리)를 사용하지 않는 Dilithium 변형을 활용하여, 영지식 증명의 시뮬레이터가 완벽($\varepsilon_{zk} = 0$)하도록 보장합니다.
• 이러한 선택은 힌트 기반 스킴과 관련된 작은 통계적 오차를 피함으로써, 특히 철회 가능성 속성에 대한 보안 증명을 단순화합니다.

주요 기여

• 일반 프레임워크: 본 논문은 피아트-샤미르 중단 패러드임에 기반한 철회 가능한 서명의 첫 번째 추상적 구성을 도입하여, Liu–Baek–Susilo 모델과 포스트 양자 격자 암호학 사이의 간극을 메웁니다.
• 보안 증명:
  • 위조 불가능성(Unforgeability): 스킴은 (양자) 무작위 오라클 모델(QROM)에서 내부 부패(내부자가 검증자의 비밀키를 보유한 경우) 하에서도 위조 불가능함이 증명되었습니다. 증명은 기초가 되는 격자 서명 스킴의 EUF-CMA 보안으로 환원됩니다(SelfTargetMSIS/MSIS 가정).
  • 철회 가능성(Withdrawability): 스킴은 철회 가능함이 증명되었습니다. 즉, 공격자는 서명이 서명자에 의해 생성되었는지 아니면 지정된 검증자에 의해 생성되었는지 구별할 수 없습니다. no-hint 인스턴스의 경우, 이 속성은 기초가 되는 식별 스킴의 완벽한 naHVZK(non-abort honest-verifier zero-knowledge)와 커밋먼트의 최소 엔트로피에 의존하여 통계적(정보 이론적) 속성($\varepsilon_{zk} = 0$)을 가집니다.
• 포스트 양자 제약 적응: 본 논문은 디피-헬만 공유 비밀의 부재를 명시적으로 다룹니다. 지정(designation)은 NIKE가 아닌 공개 키 암호화(PKE)를 통해 달성될 수 있으며, 모호성(ambiguity)은 대수적 대칭성이 아닌 OR-증명을 통해 달성될 수 있음을 보여줍니다.

결과

• 구체적 보안: no-hint Dilithium 인스턴스에 대해, 본 논문은 구체적인 보안 경계치를 제공합니다. 위조 불가능성 이점은 기초 스킴의 보안성에 무작위 오라클 프로그래밍과 관련된 무시할 수 있는 항($2^{-1024}$)을 더한 값으로 제한됩니다. 철회 가능성 이점은 $1/2$에 무시할 수 있는 통계적 항을 더한 값으로 제한되며, no-hint 케이스의 경우 지정된 검증자에 대해 사실상 완벽한 모호성을 달성합니다.
• 비교: 저자들은 Liu–Baek–Susilo 스킴과의 상세한 비교를 제공합니다(표 2). 격자 기반 구성은 추가적인 키 자료(암호화 키)를 필요로 하고 암호화 오버헤드로 인해 서명이 더 커지는 결과가 나타나지만, 두 가지 중요한 속성을 얻습니다. 즉, 철회 가능한 서명은 의사 난수(pseudorandom) 형태이며(제3자로부터 존재를 숨김), 지정된 검증자에 대한 비전달성(non-transferability)은 계산적 수준이 아닌 통계적 수준으로 완벽합니다.

의의
본 논문은 철회 가능한 서명 프리미티브를 포스트 양자 시대로 전환하기 위한 필수적인 적응이라고 주장합니다. 본 논문은 비효식적인 디피-헬만의 격자 기반 아날로그에 의존하지 않고도 격자 기반 암호학에서 철회 가능성을 달성할 수 있음을 입증합니다. 지정(encryption)과 모호성(OR-proofs)의 메커니즘을 분리함으로써, 저자들은 Dilithium과 같은 기초 스킴의 보안 특성을 유지하면서도 서명 철회라는 중요한 유연성을 추가하는 견고하고 증명 가능한 구성을 제공합니다. 이 연구는 거래 철회가 필요하지만 구현하기 어려웠던 블록체인 시스템에서 양자 내성을 강화할 수 있는 방법을 제시합니다.