CRT-Decomposed $Σ$-Protocols for CSIDH

기술 요약: CSIDH 클래스 그룹 작용을 위한 CRT 분해 $\Sigma$-프로토콜

문제 정의
본 논문은 CSIDH(Commutative Supersingular Isogeny Diffie-Hellman) 그룹 작용을 기반으로 구축된 이소제니 기반 블라인드 서명 및 식별 프로토콜의 보안 증명에서 나타나는 결정적인 약점을 다룬다. 현재의 최첨단 스킴들(예: CSI-Otter, Tanuki)은 인터랙티브 식별 프로토토콜에 의존하며, 이들의 보안 환원은 **포킹 렘마(forking lemma)**에 의존한다. 이 렘마는 비밀키를 추출하기 위해 양자 공격자를 "되감기(rewinding)"하는 과정을 요구하는데, 이는 이차적인 보안 손실을 초래하며, 내부 상태를 복제할 수 없는 양자 공격자에게는 이론적으로 유효하지 않다. 결과적으로, 이러한 증명들은 이 손실을 보상하기 위해 더 크고 느린 파라미터를 사용하도록 강제한다. 본 논문은 CSIDH 아이디얼 클래스 그룹의 대수적 구조를 활용하여 **직선 추출(straight-line extraction)**을 가능하게 함으로써 이러한 되감기 단계를 제거하고자 한다.

방법론
저자들은 CSIDH의 아이디얼 클래스 그룹의 중국인의 나머지 정리(CRT) 구조를 활용하는 영지식 지식 증명($\Sigma$-protocol)을 구성한다. 이 접근 방식은 그룹 구조가 정확히 알려진 경우에만 적용 가능한데, 현재 이 조건은 CSIDH-512에서만 충족된다.

1. CRT 분해: 차수가 $N$인 클래스 그룹 $C\ell(\mathcal{O})$를 각 소수의 거듭제곱 인자에 대응하는 독립적인 순환 성분들로 분해한다. 비밀키 $s$는 각 소인수 $q_i$에 대한 성분 $s_i$로 나뉜다.
2. 홉 커브(Hop Curves): 프로토콜은 그룹 작용의 중간 상태를 나타내는 일련의 "홉 커브"($F_0, \dots, F_k$)를 공개한다. 각 홉 $i$는 특정 부분군 $\langle h_i \rangle$ 내에서의 벡터화 문제(vectorization problem)에 대응한다.
3. 프로토콜 구조: 프로토콜은 $k$개의 홉으로 구성되며, 각 홉은 $t$개의 병렬 라운드에서 실행된다. 각 라운드에서 증명자는 무작위 변위(displacement)를 커밋하고, 검증자는 이진 챌린지($c \in \{0,1\}$)를 발행하며, 증명자는 값 $z$로 응답한다.
4. 대수적 추출: 서로 다른 챌린지를 가진 두 개의 수락된 트랜스크립트를 찾기 위해 되감기가 필요한 표준 증명과 달리, 이 프로토콜은 폐쇄형 대수 공식을 통해 비밀을 복구할 수 있다. 동일한 커밋먼트에 대해 두 개의 수락된 트랜스크립트가 주어지면, 비밀 성분은 단순히 응답의 차이($z_0 - z_1$)를 구한 뒤, 모듈로 역원을 취하고 CRT 결합을 수행하는 것과 같다.
5. QROM 컴파일: 각 라운드마다 정확히 두 개의 응답이 존재하므로, 이 프로토콜은 **Unruh의 변환(Unruh's transform)**과 호환된다. 이를 통해 인터랙티브 프로토콜을 **양자 랜덤 오라클 모델(QROM)**에서 직선 추출이 가능한 비인터랙티브 지식 증명으로 변환할 수 있으며, 포킹 렘마를 완전히 회피할 수 있다.

주요 기여
본 논문의 주요 기여는 다음과 같이 다섯 가지로 요약된다:

1. 공식 정의: 암호학적 그룹 작용에 대한 **약한 추출 가능성(weak extractability)**을 공식화하여, 추출자가 수락된 트랜스크립트로부터 (격자 축소나 휴리스틱 없이) 오직 환 연산만을 사용하여 비밀을 복구할 수 있는 보안 개념을 정의했다.
2. 프로토콜 구성 ($\Pi_{CRT}$): 다음 네 가지 속성을 증명하는 프로토콜을 구성한다:
   • 완전한 완전성(Perfect Completeness): 정직한 증명자는 항상 성공한다.
   • 완전한 특수 HVZK(Perfect Special HVZK): 트랜스크립트는 제한 없는 관찰자에게도 비밀에 대한 정보를 드러내지 않는다.
   • 2-특수 건전성(2-Special Soundness): 비밀은 단순한 뺄셈과 모듈로 역원을 통한 대수적 방식으로 두 트랜스크립트로부터 복구가 가능하다.
   • 지식 오류(Knowledge Error): 키 없이 증명자가 성공할 확률은 $2^{-t}$이다.
3. 기계 검증: 저자들은 CSIDH-512의 정확한 258비트 모듈러스 상에서 대수적 계층을 구현하였다. 10,000개의 무작위 인스턴스를 실행하여 대수적 추출이 완벽하게 작동하며, 실제 이소제니를 계산하지 않고도 프로토콜 로직이 유지됨을 확인하였다.
4. 결과의 한계 설정 (부정적 결과):
   • 챌린지 공간의 한계: CRT 분해는 라운드당 챌린지 공간을 확장시키지 않는다. 여러 커브를 공개하지 않는 한 이진 챌린지가 여전히 필요하다.
   • 보안 비용: 홉 커브를 공개함으로써 키 복구에 대한 고전적 보안이 $\approx 2^{128.6}$에서 $\approx 2^{67.3}$ 그룹 작용 평가 횟수로 감소한다. 이는 문제가 가장 큰 성분의 부분군 내에서 독립적인 벡터화 인스턴스로 분해되어, 미트 인 더 미들(meet-in-the-middle) 공격에 취약해지기 때문이다.
5. QROM 보안: 본 프로토콜을 Unruh의 변환을 통해 컴파일하면, QROM에서 **온라인 추출(online extraction)**이 가능한 비인터랙티브 증명을 얻을 수 있으며, 이는 곱셈적인 포킹 렘마 손실을 제거한다.

결과 및 정량적 분석

• 인스턴스화: 본 스킴은 CSIDH-512에 적용되었다. 클래스 그룹은 5개의 소수 인자(비트 길이: 2, 6, 21, 96, 135)를 갖는다.
• 보안 경계:
  • 고전적 보안: 보안은 가장 큰 소인수($q_{max} \approx 2^{135}$)에 의해 제한된다. 미트 인 더 미들 공격 비용은 $O(\sqrt{q_{max}}) \approx 2^{67.3}$이다. 논문은 홉 커브 공개로 인해 CSIDH-512가 이 구조 하에서 128비트 고전 보안을 달성하지 못함을 명시한다.
  • 양자 보안: 다른 CSIDH 스킴들과 유사하게 Kuperberg 스타일의 체(sieve)에 의해 경계가 정해진다.
• 성능:
  • 서명 크기: $t=128$ 라운드와 $k=5$ 성분에 대해, 서명 크기는 약 24.1 KiB이다 (CSI-FiSh의 263 B 및 CSI-Otter의 8 KiB와 비교됨).
  • 연산: 대수적 추출 및 시뮬레이션은 마이크로초 미만이다. 지배적인 비용은 여전히 이소제니 평가이며(액션당 약 40ms로 추정), 전체 서명 시간은 전체 프로토콜 기준 약 25.6초가 소요된다.
• 시뮬레이션: 몬테카를로 시뮬레이션을 통해, 추출 성능이 95% 신뢰 구간 내에서 이론적 $2^{-t}$ 경계와 일치함을 확인하였다.

의의 및 주장
본 논문은 이 구성이 알려진 구조를 가진 클래스 그룹(예: CSIDH-512)에 대해 구조적으로 완전하고 정확함을 주장한다. 본 논문의 주요 의의는 되감기 단계를 제거함으로써, 포스트 양자 보안 증명에서 알려진 취약점인 "되감기 문제"를 해결하고 이소제니 기반 지식 증명에 대한 양자 안전 보안 환원을 제공한다는 점에 있다.

그러나 저자들은 다음과 같은 트레이드오프를 명확히 밝히고 있다:

• 보안성에 대한 겸손함: 홉 커브 공개로 인한 보안 저하 때문에, 본 스킴은 CSIDH-512에 대해 정량적으로 128비트 보안을 달성하지 못한다. 저자들은 이 구성이 "각 소인수가 $\ge 256$ 비트인 미래의 파라미터 세트"에서만 정량적으로 안전하다고 언급한다.
• 만능 해결책이 아님: CRT 분해는 건전성을 위한 필요한 라운드 수를 줄이는 것이 아니라, 단지 추출 메커니즘을 변경할 뿐이다.
• 향ach 연구: 본 논문은 이 지식 증명에 기반한 블라인드 서명의 구축과, 이를 엔도모피즘 링 문제(endomorphism ring problem)로의 타이트한 불변성 환원하는 작업을 향후 과제로 남겨두었다.

요약하자면, 본 논문은 CSIDH 기반 지식 증명의 "되감기 문제"를 해결하는 수학적으로 엄밀하고 기계 검증된 프로토콜을 제시하며, 이는 더 큰 서명 크기와 현재 파라미터 세트에서의 감소된 고전 보안을 대가로 QROM 보안이 가능한 블라인드 서명으로 가는 경로를 제공한다.