기술 요약: 아이소제니 기반의 컴팩트한 양자 내성 강한 지정 검증자 서명 방식

문제 정의

전통적인 디지털 서명은 비부인성(non-repudiation)을 제공하며, 이는 서명자의 공개 키에 접근할 수 있는 모든 당사자가 서명의 진위 여부를 검증할 수 있음을 의미한다. 이러한 특성은 많은 응용 분야에서 유용하지만, 서명자(앨리스)가 특정 수신자(밥)에게 메시지를 인증하되, 밥이 해당 메시지가 앨리스로부터 왔음을 제3자에게 증명할 수 없기를 원하는 "오프 더 레코드(off-the-record)" 통신 시나리오에서는 바람직하지 않다.

이러한 문제를 해결하기 위해 **강한 지정 검증자 서명(Strong Designated Verifier Signatures, SDVS)**이 도입되었다. SDVS 방식은 지정된 검증자만이 서명을 검증할 수 있도록 보장한다. 결정적으로, 이 방식은 **비전송성(non-transferability)**을 만족한다. 즉, 지정된 검증자는 실제 서명과 계산적으로 구별 불가능한 서명을 시뮬레이션할 수 있으므로, 제3자에게 서명의 유효성을 입증할 수 없다. 또한, SDVS 방식은 **서명자 신원 프라이버시(Privacy of Signer's Identity, PSI)**를 충족해야 한다. 이는 유효한 서명과 여러 후보 공개 키가 주어졌을 때, 제3자가 어떤 키가 사용되었는지 결정할 수 없음을 보장하는 것이다.

기존의 클래식 암호학(쌍선형 페어링 또는 슈노르 서명 기반) 기반 SDVS 방식은 쇼어 알고리즘(Shor's algorithm)을 통한 양자 공격에 취약하다. 코드(codes) 또는 격자(lattices) 기반의 기존 양자 내성 제안들은 종종 큰 키 및 서명 크기($O(\lambda^2)$ 복잡도)를 갖거나, 비전송성 속성이 결여된 것으로 밝혀지기도 했다. 최근의 아이소제니 기반 제안들은 보안 결함(예: SIDH)을 겪었거나, 충분히 견고하다고 간주되지 않는 가정에 의존하고 있다.

방법론

저자들은 CSIDH(Commutative Supersingular Isogeny Diffie-Hellman) 군 작용(group action)에 기반한 새로운 SDVS 방식인 CSI-SDVS를 제안한다. 이 구성은 허수 이차체(imaginary quadratic field)의 이상 클래스 군(ideal class group)이 유한체 $\mathbb{F}_p$ 상의 초특이 타원 곡선 집합에 작용하는 대수적 구조를 활용한다.

핵심 구성 요소

1. 군 작용 설정: 본 방식은 유효한 군 작용 $(G, X, *)$ 내에서 작동한다. 여기서 $G$는 허수 이차체의 순서(order)에 대한 이상 클래스 군이며, $X$는 초특이 타원 곡선의 집합이다. 이 작용은 자유롭고 추이적(transitive)이다.
2. 키 생성:
   • 서명자와 검증자는 $\mathbb{Z}_N$($N$은 클래스 수) 내의 무작위 정수로서 비밀 키($sk_S, sk_V$)를 생성한다.
   • 공개 키는 베이스 곡선 $E$에 군 작용을 적용하여 생성된다: $pk_S = [g^{sk_S}] * E$ 및 $pk_V = [g^{sk_V}] * E$.
3. 서명 및 시뮬레이션:
   • 서명: 메시지 $m$에 서명하기 위해, 서명자는 무작위 $z \in \mathbb{Z}_N$를 선택하고, $Y = [g^{z+sk_S}] * pk_V$를 계산한 후, $h = H(Y || m)$인 $\sigma = (h, z)$를 설정한다.
   • 시뮬레이션: $sk_V$를 보유한 검증자는 무작위 $z$를 선택하고, $Y = [g^{z+sk_V}] * pk_S$를 계산한 후, $h = H(Y || m)$인 $\sigma = (h, z)$를 설정함으로써 서명을 시뮬레이션할 수 있다.
   • 정당성(Correctness): 군 작용의 가환성(commutativity) 덕분에, $[g^{z+sk_S}] * pk_V = [g^{z+sk_S+sk_V}] * E = [g^{z+sk_V}] * pk_S$가 성립한다. 따라서 서명자와 시뮬레이터가 계산하는 $Y$ 값은 동일하며, 이는 두 명 모두 동일한 해시 입력에 대해 유효한 서명을 생성함을 보장한다.
4. 검증: 검증자는 $h = H([g^{z+sk_V}] * pk_S || m)$인지 확인한다.

주요 기여

1. 컴팩트한 양자 내성 SDVS: 본 논문은 효율적인 SDVS 방식인 CSI-SDVS를 제시하며, 키와 서명에 대해 $O(\lambda)$ 복잡도를 가진다. CSIDH-512 파라미터를 사용할 경우 다음과 같은 성능을 보인다:
   • 비밀 키: 256 비트.
   • 공개 키: 512 비트.
   • 서명: 512 비트.
     이는 종종 $O(\lambda^2)$ 크기를 갖는 기존 격자 기반 SDVS 방식이나 더 큰 공개 키를 갖는 아이소제니 기반 방식보다 크게 개선된 수치이다.
2. ROM 및 AGAM에서의 보안 증명:
   • 비전송성 (NT): 실제 서명과 시뮬레이션된 서명의 분포가 동일하므로 무조건적으로 증명된다.
   • 강한 위조 불가능성 (SUF-CMA) 및 PSI: 무작위 오라클 모델(ROM) 하에서 군 작용 결정적 디피-헬먼(GA-DDH) 가정에 따라 안전함이 증명된다.
   • 타이트한 축약(Tight Reductions): 저자들은 나아가 **대수적 군 작용 모델(AGAM)**에서, CSI-SDVS의 SUF-CMA 및 PSI 보안이 결정적 문제가 아닌 계산적 문제인 **군 작용 역 문제(GAIP)**로 타이트하게 축약됨을 증명한다.
3. 보안 분석: 본 방식은 깨진 프로토콜인 SIDH에 의존하지 않고, 현재까지 안전하다고 믿어지는 CSIDH 군 작용을 활용하여 모든 표준 SDVS 보안 정의(NT, SUph-CMA, PSI)를 만족함을 보여준다.

결과

본 논문은 다음을 입증하는 공식적인 보안 증명을 제공한다:

• 본 방식은 무조건적으로 비전송성을 갖는다.
• ROM 하의 GA-DDH 가정 하에서, 본 방식은 강한 위조 불가능성을 가지며 서명자의 신원 프라이버시를 제공한다.
• AGAM 및 ROM 하의 GAIP 가정 하에서, 본 방식은 SUF-CMA 및 PSI 보안에 대해 타이트한 축약을 달성한다.
• 성능: 논문의 표 1은 CSI-SDVS를 이전 연구들(Sun 등 [26] 및 Khuc 등 [12])과 비교한다. CSI-SDFS는 비교된 양자 내성 방식들 중 가장 작은 공개 키(512 비트)와 서명(512 비트)을 제공하면서도, 256 비트의 비밀 키 크기를 유지한다.

의의

저자들은 CSI-SDVS를 실용적이고 안전한 양자 내성 지정 검증자 서명 솔루션으로 포지셔닝한다. 본 연구의 의의는 다음과 같다:

• 효율성: 기존의 격자 기반 및 아이소제니 기반 제안들의 크기 제한 문제를 해결하여, 자원이 제한된 환경에 적합한 컴팩트한 파라미터를 달 achieves 한다.
• 견고성: AGAM에서 GAIP(계산적 가정)에 기반하여 보안을 구축함으로써, 군 작용 환경에서 때때로 더 약하거나 직관적이지 않을 수 있는 결정적 가정에 대한 의존을 피했다.
• 완결성: 본 연구는 비전송성이 결여되었거나 비효율적이었던 기존 방식들이 남긴 공백을 메우며, 양자 내성 환경에서 SDVS의 세 가지 핵심 축(비전송성, 위조 불가능성, 서명자 프라이버시)에 대한 완전한 보안 분석을 제공한다.

결론적으로, CSI-SDVS는 보안과 효율성 사이의 균형 잡힌 트레이드오프를 제공하며, 양자 내성 및 비전송 인증이 필요한 응용 분야에 대한 유망한 후보임을 시사한다.