[암호학 기본 05] Cryptographic Commitments scheme

omin·2025년 8월 13일

Cryptography commitments scheme 암호학

암호학 기본

목록 보기

5/6

커밋먼트(Commitment)란?

커밋먼트는 암호학에서 사용되는 중요한 개념으로, 특정 값이나 메시지에 '잠금'을 걸어 상대방에게 전달하고, 필요할 때만 그 내용을 공개할 수 있게 해주는 원시 요소(primitive)이다.

정의: 송신자가 메시지 m을 잠긴 상태로 수신자에게 보내면, 수신자는 상자 안의 내용을 알 수 없다. 송신자만이 나중에 '열쇠(opening information)'를 제공하여 메시지를 공개할 수 있다.

활용 예시 하나를 살펴보면, 이전에 보았던 Schnorr Signature에서 Prover는 무작위 r을 사용하여 $A=g^r$ 을 미리 commit해 둔다. 이 과정을 통해 증명자는 챌린지-응답 단계에서 메시지가 변조되지 않았음을 보장한다. 이는 특정 값을 고정해두고, 그 다음 challenge-response 과정을 통해 특정 값을 자신이 알고 있음을 증명하는 것이다.

Why Commitment

Commitment는 영지식 증명, 디지털 서명, 검증 가능한 비밀 공유를 통한 MPC(다자간 연산) 등 다양한 암호화 프로토콜에서 중요한 역할을 한다. 특히 영지식 증명에서는 다음의 두 가지 목적으로 사용된다.

선택형 증명(Cut-and-Choose): 증명자가 여러 증명 후보에 커밋하고, 검증자가 이 중 일부를 선택하여 검증하도록 함으로써 효율성을 높인다.
병렬화: 검증자가 자신의 선택 사항을 커밋먼트로 미리 명시하여, 증명자에게 추가 정보를 노출하지 않고도 증명 과정을 병렬로 진행할 수 있게 한다.

커밋먼트 프로토콜 단계

일반적으로 커밋먼트는 세 단계로 이루어진다.

셋업(Setup): 증명자와 검증자가 공통 시스템 매개변수에 합의한다.
커밋(Commit): 증명자는 메시지 m과 무작위 값 r을 이용해 커밋먼트 c를 계산한 후 검증자에게 보낸다.
오픈/검증(Open/Verify): 증명자가 $(m, r)$ 을 공개하면, 검증자는 이를 받아 커밋먼트 c가 올바른지 확인한다.

(보통 셋업을 제외하고, 커밋과 오픈/검증의 두 단계로 한다.)

커밋먼트 스킴의 주요 특성

커밋먼트 스킴은 아래와 같은 2가지 특성을 지닌다.

은닉성(hiding) 또는 기밀성(confidentiality): open되기 전, 공격자가 커밋먼트 c를 보더라도 커밋 값에 대한 어떠한 정보도 알 수 없어야 한다. 즉, 공개 전에 m을 추측할 수 없어야 한다.
결속성(binding): 당사자가 커밋 후 m을 다른 값으로 변경할 수 없다.

Pederson commitments scheme

그림은 Pederson Commitments의 과정을 보여준다.
출처 : Formalising Σ-Protocols and Commitment Schemes Using CryptHOL

Pedersen Commitments은 이산 로그 문제(DLP)의 난이도에 기반한 간단하면서도 강력한 커밋먼트 스킴이다.

수학적 정의

매개변수 설정

소수 차수 q를 가진 유한군 G를 선택한다.
G의 두 생성자 g,h를 선택한다. 이때 g에 대한 h의 이산 로그 $\log_g(h)$ 는 알려져 있지 않다.
시스템 매개변수는 $(G, q, g, h)$ 입니다.

커밋(Commit) 과정

0<s<q 인 비밀 정수 s에 대한 커밋먼트 c∈G 를 생성하려면, t ←$Z_q를 랜덤하게 샘플링하고 다음을 계산한다.(랜덤 값 t를 선택한다.)
$c=C_{g,h}(s,t)=g^sh^t$

오픈(Open) 과정

s와 t를 공개하면, 검증자는 $c=g^sh^t$ 를 확인하여 유효성을 검증한다.

Pedersen Commitments의 속성

결속성 (Computational Binding):
만약 송신자가 s와 다른 값 $s'$ 에 대해 동일한 커밋먼트 c를 만들 수 있다면, 즉 $g^s h^t = g^{s'} h^{t'}$ 이 성립한다면, 이는 $\log_g(h)$ 를 계산하는 것과 동등해진다.
결국 이산 로그 문제를 푸는 것과 같으므로, 페더슨 커밋먼트는 계산적 결속성을 가진다.
은닉성 (Perfect/Statistical Hiding):
랜덤 값 t는 $Z_q$ 에서 균등하게 샘플링된다. 커밋먼트 $c=g^sh^t$ 에서 $h^t$ 는 G의 균등한 랜덤 원소와 같다. 따라서 어떤 $s$ 와 $s'$ 에 대해서도 적절한 $t$ 와 $t'$ 를 선택하면 동일한 c를 만들 수 있다. 즉, 커밋먼트 c만으로는 s에 대한 어떠한 정보도 얻을 수 없다.(영지식 증명의 zero-knowledge(영지식성)과 유사한 개념) 따라서 페더슨 커밋먼트는 완전 은닉성을 가진다.

덧셈 동형성(Additive Homomorphism)

Pedersen Commitments가 가지는 특이한 속성에 대해 알아보자. Pedersen Commitments는 두 커밋먼트를 곱하면 커밋된 값들의 합에 대한 새로운 커밋먼트가 되는 특별한 성질을 가지고 있다.

c_1=g^{s_1}h^{t_1}

c_2=g^{s_2}h^{t_2}

c_1 * c_2=g^{s_1+s_2}h^{t_1+t_2} = C(s_1+s_2,t_1+t_2)

이러한 특성 덕분에, 커밋된 값들을 공개하기 전에 다양한 연산을 수행할 수 있어 영지식 증명 등에서 매우 유용하게 활용된다.

페더슨 커밋먼트의 유용한 속성들

페더슨 커밋먼트는 몇 가지 증명 프로토콜과 함께 사용될 수 있다.

비밀의 지식 증명(Proof of Knowledge of a Secret)

커밋먼트 $A=C_{g,h}(x,y)=g^xh^y$ 가 주어졌을 때, A는 x와 y 중 어느 것도 공개하지 않고 B에게 자신이 x와 y를 알고 있다는 것을 증명할 수 있다. 이는 페더슨 커밋먼트의 덧셈 속성이 악용되는 것을 방지하는 데 유용한 프로토콜이다.

g^{s_1}h^{s_2}=g^{xk+t_1}h^{yk+t_2}=g^{xk}h^{yk}g^{t_1}h^{t_2}=(g^xh^y)^kT=A^kT

이는 B를 속이기 위해서는 A가 이산 로그 문제를 풀어야 한다는 것을 의미하므로 안전하다.

동일 메시지 증명(Equal Opening)

같은 생성자 집합을 사용하여 비밀 $s$ 에 대한 두 커밋먼트

c_{1} = C(s, t_{1}), \quad c_{2} = C(s, t_{2}) \quad (t_{2} \neq t_{1})

A는 $c_{1}$ 과 $c_{2}$ 모두 같은 값 $m$ 에 커밋했다는 것을 증명할 수 있다.
페더슨이 제시한 가장 간단한 방법은 A가 $r = t_{1} - t_{2} \pmod{q}$ 를 Bob에게 공개하는 것이다. 이는 아래 식으로 인해 만족한다.

c_{1} c_{2}^{-1} = g^{s} h^{t_{1}} \cdot g^{-s} h^{-t_{2}} = g^{s-s} h^{t_{1} - t_{2}} = h^{t_{1} - t_{2}} = h^{r}

Reference

[Pedersen91] Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing (1991).
https://www.zkdocs.com/docs/zkdocs/commitments/pedersen/
https://www.cs.cornell.edu/courses/cs754/2001fa/129.PDF
https://www.zkdocs.com/docs/zkdocs/commitments/pedersen/
https://medium.com/@icostan/commitment-schemes-8b523d48aa1e
https://cseweb.ucsd.edu/classes/fa19/cse206A-a/LecCommit.pdf

omin

이전 포스트

[암호학 기본 04] DLP-based Public-Key Cryptography

다음 포스트

[암호학 기본 05] Cryptographic Commitments scheme