# Cryptographic Commitments
{% hint style="warning" %}
**목표 : 커밋먼트(Commitment)의 기본 개념과 프로토콜 단계(커밋, 오픈), 핵심 보안 속성인 은닉성(hiding)과 결속성(binding)을 이해한다. 나아가 Pedersen 커밋먼트의 수학적 구조와 동형성, 그리고 이를 활용한 각종 증명 기법을 익힌다.**
{% endhint %}
zkp에서 **커밋먼트**는 사실상 **무결성과 일관성을 보장하는 역할**을한다. 증명자는 먼저 비밀 값에 대해 커밋을 만들어 두고, 이후 필요할 때 해당 값을 열어, "**이 커밋들끼리 이런 관계를 만족한다**"는 사실을 증명한다. **Pedersen 커밋먼트처**럼 **은닉성**과 **결속성**을 모두 가지면서 **덧셈 동형성**까지 제공하는 스킴은, 다항식 커밋먼트, 범위 증명, 복잡한 zk 회로 설계의 기본 빌딩 블록으로 쓰인다.
이 글에서는 커밋먼트의 직관적 의미와 형식적 정의를 살펴본 뒤, Pedersen 커밋먼트가 왜 zkp에서 쓰이는지 **DLP 기반 결속성, 완전/통계적 은닝성, 동형성** 관점에서 정리한다.
### 커밋먼트(Commitment)란?
정의: 어떤 값 m 또는 명제에 '잠금'을 걸어 상대에게 전달하고, 추후 원하면 열쇠(오프닝 정보)로 그 값을 공개할 수 있게 해주는 암호학적 프리미티브이다.
슈노르 서명에서도 Prover가 임의 값 $$r$$로 만든 $$A$$를 $$g^r$$를 먼저 고정(commit)해두어, 이후 챌린지-응답 단계에서 메시지가 변조되지 않음을 보장한다. ("먼저 무작위 $$r$$에 대한 커밋 $$A = g^r$$을 고정해 두고, 그 다음 챌린지-응답 과정을 통해 $$X = g^w$$ 의 지수 $$w$$를 내가 알고 있음을 증명할게."로 이해할 수 있다.)
> 커밋먼트 스킴을 시각화하는 방법은 송신자가 메시지를 잠긴 상자에 넣고 그 상자를 수신자에게 주는 것으로 생각하는 것이다. 상자 안의 메시지는 수신자에게 숨겨져 있으며, 수신자는 스스로 자물쇠를 열 수 없다. 수신자가 상자를 가지고 있기 때문에 안의 메시지는 변경될 수 없으며, 나중에 송신자가 열쇠를 주기로 선택한 경우에만 공개될 수 있다.
### 왜 커밋먼트가 필요한가?
영지식 증명, 디지털 서명, 검증 가능한 비밀 공유 → 다자간 연산(MPC) 등 다양한 암호화 프로토콜에서 응용되고 있다. 특히 영지식 증명에서는 두 가지 목적으로 사용된다. 첫째, 증명자가 검증자에게 학습할 내용을 선택할 수 있는 선택형(cut and choose) 증명에 참여할 수 있도록 한다. 검증자는 선택 사항에 해당하는 내용만 공개한다. 둘째, 검증자가 커밋을 통해 자신의 선택 사항을 미리 명시하는 경우가 많다. 이를 통해 증명자에게 추가적인 정보를 공개하지 않고도 영지식 증명을 병렬로 작성할 수 있다.
### 프로토콜 단계
커밋먼트는 일반적으로 3단계를 거쳐 실행된다. (보통 셋업을 제외하고 두 단계라고 많이 말한다.)
1. setup: 증명자, 검증자가 공통 시스템 매개변수에 합의한다.
2. commit: 증명자가 무작위 값 r과 메시지 m으로 커밋먼트 c를 계산하여 검증자에게 전송한다.
3. open/verify: decommit, reveal 이라고도 한다.
1. 증명자가 (m, r)을 공개한다.
2. 검증자가 (m, r)을 받아 c 검증 후 참/거짓을 반환한다.
### 커밋먼트 필수 속성
또한 커밋먼트 스킴에는 고려해야 할 두 가지 주요 속성이 존재한다.
1. **은닉성(hiding)** 또는 **기밀성(confidentiality)**: open되기 전, 공격자가 커밋먼트 c를 보더라도 커밋 값에 대한 어떠한 정보도 알 수 없어야 한다. 즉, 공개 전에 m을 추측할 수 없어야 한다.
1. **완전 은닉(perfect hiding)**: 무한한 계산 능력을 가진 공격자라도 커밋된 메시지 m을 reveal할 수 없다.
2. **계산적 은닉(computationally hiding)**: 무한한 계산 능력으로 공격자가 어려운 문제(트랩도어 함수, 소인수분해, 이산로그 등)를 풀고 커밋된 메시지 m을 찾을 수 있다.
2. **결속성(binding)**: 당사자가 커밋 후 m을 다른 값으로 변경할 수 없다.
### Pederson commitments scheme
### 개요
페더슨 커밋먼트는 1992년 페더슨의 검증 가능한 비밀 공유 방식의 일부로 처음 설명되었다. 페더슨 논문의 3절에서는 이 커밋먼트 방식이 Bos, Chaum, Purdy가 투표 시스템을 제안하며 미발표 노트에서 제안한 방식과 "매우 유사하다"고 언급하고 있다.
페더슨 커밋먼트는 단순하다. 값에 커밋하는 것은 단지 두 번의 모듈러 지수 연산과 하나의 곱셈만 필요하다. 각 커밋먼트에 랜덤 값이 필요하기 때문에, 커밋먼트들은 비결정적이다. 그리고 페더슨 커밋먼트는 군 구조에 크게 의존하기 때문에, 커밋된 값들에 대한 유용한 연산과 증명을 가능하게 하는 많은 유용한 속성들을 상속받는다.
페더슨의 원래 제안은 $${Z}^\*\_p$$의 차수- $$q$$부분군 관점에서 커밋먼트를 설명했지만, 이 글에서는 더 일반적인 용어로 설명한다. 이는 이산 로그 문제가 어렵다고 여겨지는 모든 군 $$G$$(타원곡선 군 등)에 적용 가능하기 때문이다.
### 수학적 정의
소수 차수 $$q$$ 를 가진 유한군 $$G$$ 로 시작하며, 여기서 $$q$$ 는 충분히 크다. 예를 들어, $$q$$ 가 $$p$$ 를 나누는 곱셈군 $${Z}^\*\_p$$ 의 차수- $$q$$ 부분군이나 타원곡선 군 또는 부분군을 사용할 수 있다. $$\log\_g(h)$$ 가 알려지지 않은 $$G$$ 의 두 생성자 $$g, h$$를 선택한다. 커밋먼트 방식의 매개변수는 $$(G, q, g, h)$$이다.
$$0 < s < q$$ 인 비밀 정수 $$s$$에 대한 커밋먼트 $$c ∈ G$$ 를 생성하려면, $$t \stackrel{}{←} \mathbb{Z}\_q$$를 랜덤하게 샘플링하고 다음을 계산한다:
$$c = C\_{g,h}(s,t) = g^s h^t$$
($$g, h$$가 문맥상 명확할 때는 단순히 $$C(s,t)$$로 쓸 수 있다.)
커밋먼트를 열기 위해서는 단순히 $$s$$와 $$t$$를 공개한다.
#### 페더슨 커밋먼트가 결속성을 가지는 이유에 대한 직관 (Computational)
Alice가 Bob에게 값 $$s$$에 대한 커밋먼트 $$c = C(s,t)$$를 보냈다고 가정해보자. 이제 Alice가 $$s' ≠ s$$에 해당하는 $$c$$의 오픈 값을 Bob에게 보내서 속이려고 한다. 다시 말해, Alice는 페더슨 커밋먼트의 결속성 속성을 깨뜨리려고 합니다.
이는 Alice가 $$g^{s'}h^{t'} = c$$가 되는 $$t'$$를 찾아야 함을 의미한다. $$g^{s'}$$와 $$c$$가 이미 고정되어 있으므로, Alice는 $$h^{t'} = cg^{-s'}$$를 풀어야 한다. 다시 말해, 그녀는 $$t' = \log\_h(cg^{-s'})$$를 계산해야 한다. $$G$$에서 이산 로그 문제가 어렵다고 가정되므로, Alice는 $$t'$$를 찾는 데 어려움을 겪는다.
값에 커밋하기 전에, Alice는 $$s$$와 $$s'$$의 특정 값에 관계없이 $$C(s,t) = C(s',t')$$가 되는 서로 다른 쌍 $$(s,t), (s',t')$$를 찾을 수도 있다. 이 또한 $$G$$에서 이산 로그를 계산하는 것과 동등하다. 페더슨 논문에서 지적한 바와 같이: $$s' ≠ s$$인 $$C(s,t) = C(s',t')$$가 주어지면, $$t' ≠ t$$이고, $$g$$에 대한 $$h$$의 이산 로그를 계산할 수 있다:
$$\log\_g(h) = \frac{s-s'}{t'-t} \pmod{q}$$
요약하면, 페더슨 커밋먼트의 결속성 속성을 깨뜨리는 것은 이산 로그 문제를 푸는 것과 동등하다.
#### 페더슨 커밋먼트가 은닉성을 가지는 이유에 대한 직관 (Perfect/통계적)
Alice가 Bob에게 값 $$s$$에 대한 커밋먼트 $$c = C(s,t)$$를 보냈다고 가정해자. Bob은 $$c$$로부터 $$s$$나 적어도 $s$에 대한 무언가를 알아내어 속이려고 한다.
$$t$$는 균등하게 랜덤하게 샘플링되므로, $$t$$의 모든 값이 선택될 가능성이 같으며, 이는 $$h^t$$의 모든 값이 같은 가능성을 갖는다는 것을 의미한다. $$h$$가 $$G$$의 생성자이므로, $$t$$는 $$G$$의 모든 원소를 균등하게 랜덤하게 선택한다.
Bob이 $$c$$로부터 $$s$$나 $$g^s$$의 값을 추측하는 데 어떤 이점을 얻을 수 있다면, 그는 필연적으로 $$t$$나 $$h^t$$를 추측하는 데도 이점을 얻게 된다. 그러나 $$t$$는 균등하게 랜덤하게 선택되므로, $$h^t$$는 $$G$$의 균등한 랜덤 원소입니다. 균등한 랜덤 분포에 대해서는 정보를 얻을 수 없다.
#### 덧셈 동형성
두 커밋먼트 $$c\_1 = C(s\_1, t\_1) = g^{s\_1}h^{t\_1}$$과 $$c\_2 = C(s\_2, t\_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)$$이다. 즉, 임의의 두 페더슨 커밋먼트의 곱은 커밋된 값들의 합에 대한 커밋먼트이다.
이는 또한 지수화를 통한 스칼라 곱셈을 가능하게 한다: $$C(x,y)^n = C(nx, ny)$$.
이 덧셈 속성은 매우 유용할 수 있다. 이를 통해 커밋된 값들을 공개하기 전에 다양한 연산을 수행할 수 있다. 예를 들어, Bulletproofs와 같은 시스템은 페더슨 방식의 이 속성을 활용하여 전체 값들의 벡터에 한 번에 커밋하고, 커밋먼트들을 단일 값으로 집계한다.
### 페더슨 커밋먼트의 유용한 알고리즘과 속성들
#### 비밀의 지식 증명
커밋먼트 $$A = C\_{g,h}(x,y) = g^x h^y$$가 주어졌을 때, Alice는 $$x$$와 $$y$$ 중 어느 것도 공개하지 않고 Bob에게 그녀가 $$x$$와 $$y$$를 알고 있다는 것을 증명할 수 있다. 이는 페더슨 커밋먼트의 덧셈 속성이 악용되는 것을 방지하는 데 유용한 프로토콜이다. 프로토콜은 다음과 같이 작동한다:
| Alice | Bob |
| ---------------------------------------------------- | ------------------------------------------ |
| $$t\_1, t\_2 \stackrel{$}{←} \mathbb{Z}\_q$$ | |
| $$T = g^{t\_1}h^{t\_2}$$ | |
| $$T$$ → | |
| | ← $$k \stackrel{$}{←} \mathbb{Z}\_q$$ |
| $$s\_1 = x \cdot k + t\_1, s\_2 = y \cdot k + t\_2$$ | |
| $$s\_1, s\_2$$ → | |
| | $$g^{s\_1}h^{s\_2} \stackrel{?}{=} A^k T$$ |
이것이 작동하는 이유:
$$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^x h^y)^k T = A^k T$$
이는 Bob을 속이기 위해서는 Alice가 이산 로그 문제를 풀어야 하기 때문에 안전하다.
Fiat-Shamir 변환의 직접적인 적용으로 이를 비인터랙티브 증명으로 바꿀 수 있다. Alice가 $$k = Hash(g | h | A | T)$$를 선택하고, 여기서 $$Hash()$$의 출력이 $$q$$와 같은 비트 길이를 가진다면, Alice는 $$k$$가 균등하게 랜덤하게 선택된 것처럼 진행할 수 있습니다. Bob은 같은 방식으로 $$k$$를 계산하고, 거기서부터 나머지 증명을 검증할 수 있습니다.
#### 동일 메시지 증명(Equal Opening)
같은 생성자 집합을 사용하여 비밀 $$s$$에 대한 두 커밋먼트 $$c\_1 = C(s, t\_1)$$과 $$c\_2 = C(s, t\_2)$$ (여기서 $$t\_2 ≠ t\_1$$)가 주어졌을 때, Alice는 $$c\_1$$과 $$c\_2$$ 모두가 같은 값에 커밋한다는 것을 쉽게 보여줄 수 있다. 즉, 두 커밋이 같은 m을 포함했음을 증명하는 것이다. 페더슨이 제시한 가장 간단한 방법은 Alice가 $$r = t\_1 - t\_2 \pmod{q}$$를 Bob에게 공개하는 것이다.
이것이 작동하는 이유는 Bob이 다음을 확인할 수 있기 때문이다:
$$c\_1 c\_2^{-1} = g^s h^{t\_1} g^{-s} h^{-t\_2} = g^{s-s} h^{t\_1-t\_2} = h^{t\_1-t\_2} = h^r$$
#### 다른 베이스 동일 메시지 증명
Alice가 $$c\_1 = C\_{g\_1,h}(s, t\_1)$$과 $$c\_2 = C\_{g\_2,h}(s, t\_2)$$를 가지고 있고, 여기서 $$g\_1 ≠ g\_2$$일 수 있다고 가정해봅시다. Alice는 Bob에게 $$c\_1$$과 $$c\_2$$가 같은 값에 커밋한다는 것을 증명할 수 있다.
Alice는 랜덤 정수$$r\_1, r\_2, r\_3 \stackrel{}{←} \mathbb{Z}q$$ *를 선택한 다음,* $$c\_3 = C{g\_1,h}(r\_1, r\_2) = g\_1^{r\_1} h^{r\_2}$$와 $$c\_4 = C\_{g\_2,h}(r\_1, r\_3) = g\_2^{r\_1} h^{r\_3}$$를 계산합니다. Alice는 $$c\_3, c\_4$$를 Bob에게 보낸다.
Bob은 랜덤 챌린지 값 $$k \stackrel{}{←} \mathbb{Z}\_q$$를 선택하고 Alice에게 보낸다.
Alice는 $${Z}\_q$$에서 $$z\_1 = ks + r\_1$$, $$z\_2 = kt\_1 + r\_2$$, $$z\_3 = kt\_2 + r\_3$$를 계산하고 $$z\_1, z\_2, z\_3$$를 Bob에게 보낸다.
Bob은 $$c\_3 c\_1^k = C\_{g\_1,h}(z\_1, z\_2)$$와 $$c\_4 c\_2^k = C\_{g\_2,h}(z\_1, z\_3)$$를 확인합니다. 조건이 성립하면, Bob은 증명을 유효한 것으로 받아들인다.
이것이 작동하는 이유:
c_3 c_1^k = (g_1^{r_1} h^{r_2})(g_1^s h^{t_1})^k = g_1^{r_1} h^{r_2} g_1^{ks} h^{kt_1} = g_1^{ks+r_1} h^{kt_1+r_2} = g_1^{z_1} h^{z_2} = C_{g_1,h}(z_1, z_2)
그리고
c_4 c_2^k = (g_2^{r_1} h^{r_3})(g_2^s h^{t_2})^k = g_2^{r_1} h^{r_3} g_2^{ks} h^{kt_2} = g_2^{ks+r_1} h^{kt_2+r_3} = g_2^{z_1} h^{z_3} = C_{g_2,h}(z_1, z_3)
#### 다이어그램:
| Alice | Bob |
| ------------------------------------------------------------------ | --------------------------------------------- |
| $$r\_1, r\_2, r\_3 \stackrel{$}{←} \mathbb{Z}\_q$$ | |
| $$c\_3 = C\_{g\_1,h}(r\_1, r\_2), c\_4 = C\_{g\_2,h}(r\_1, r\_3)$$ | |
| $$c\_3, c\_4$$ → | |
| | ← $$k \stackrel{$}{←} \mathbb{Z}\_q$$ |
| $$z\_1 = ks + r\_1$$ | |
| $$z\_2 = kt\_1 + r\_2$$ | |
| $$z\_3 = kt\_2 + r\_3$$ | |
| $$z\_1, z\_2, z\_3$$ → | |
| | $$c\_3 c\_1^k \stackrel{?}{=} C(z\_1, z\_2)$$ |
| | $$c\_4 c\_2^k \stackrel{?}{=} C(z\_1, z\_3)$$ |
다시, 이는 Fiat-Shamir 변환을 사용하여 Non-Interactive하게 만들 수 있다. Alice는 $$k = Hash(g\_1 | g\_2 | h | c\_1 | c\_2 | c\_3 | c\_4)$$를 사용할 수 있으며, $$k$$와 $$q$$가 같은 비트 길이를 갖도록 해시를 선택한다.
이 구성은 더 복잡하지만, $$g\_1 ≠ g\_2$$일 때 커밋먼트를 만들 수 있다는 이점이 있다.
#### 제곱 커밋먼트의 증명
위의 커밋먼트 동등성 증명을 사용하여 비밀 $$s$$와 그 제곱 모두에 커밋할 수 있다.
Alice가 랜덤 $$t\_1$$과 해당 커밋먼트 $$c\_1 = C\_{g,h}(s, t\_1) = g^s h^{t\_1}$$을 가지고 있다고 가정해보자. Alice는 랜덤 $$t\_2$$를 선택하고 $$c\_2 = C\_{c\_1,h}(s, t\_2) = (c\_1)^s h^{t\_2}$$를 계산할 수 있습니다.
$$c\_2 = C\_{c\_1,h}(s, t\_2) = (c\_1)^s h^{t\_2} = (g^s h^{t\_1})^s h^{t\_2} = g^{s^2} h^{st\_1+t\_2} = C\_{g,h}(s^2, st\_1+t\_2)$$이므로, $$c\_2$$는 베이스 $$g$$에서 $$s^2$$에 대한 커밋먼트다.
$$c\_1$$이 생성되면, Alice는 쉽게 $$c\_2$$를 생성하고, 두 값을 Bob에게 제공하며, 위의 동등성 증명을 사용하여 $$c\_2$$가 $$c\_1$$에 의해 커밋된 값의 제곱에 커밋한다는 것을 증명할 수 있다.
### 보안 고려사항
#### 생성자 선택
Alice가 $$l = \log\_g(h)$$를 알고 있고 커밋먼트 $$c = C(s,t) = g^s h^t$$를 가지고 있다고 가정해보자.
그러면 Alice는 커밋먼트 $$c = g^s h^t$$를 $$c = g^s (g^l)^t = g^s g^{tl} = g^{s+tl}$$로 다시 쓸 수 있다. $$s' = s + l$$과 $$t' = t - 1$$이라고 하면, 그녀는 $$(s', t')$$를 보내서 커밋먼트 $$c$$를 부정하게 오픈할 수 있다. 다음과 같은 이유로 Bob에게는 유효한 오픈 값으로 보일 것이다:
g^{s'} h^{t'} = g^{s+1} (g^l)^{t-1} = g^{s+l} g^{l(t-1)} = g^{s+l} g^{tl-l} = g^{s+tl} = c
$$g$$에 대한 $$h$$의 이산 로그가 Alice에게 알려져 있다면(또는 이산 로그 계산을 쉽게 만드는 불안전한 군이 선택된다면), **결속성 속성이 상실된다**.
이것이 생성자 $$g$$와 $$h$$가 독립적으로 선택되도록 보장하는 것이 중요한 이유이다. 이상적으로는, $$g$$와 $$h$$는 nothing-up-my-sleeve 구성을 사용하여 서로 독립적으로 선택되어야 한다. 예를 들어, $$g$$와 $$h$$는 합의된 PRF와 ANSI X9.62 표준의 알고리즘 D.3.1("타원곡선에서 점 찾기")을 사용하여 선택할 수 있다.
#### 난수 생성기 문제
은닉 값 $$t \stackrel{$}{←} \mathbb{Z}\_q$$를 선택할 때, $$t$$가 진정으로 균등해야 한다.
$$t$$를 생성하는 과정에 공격이 있고, 반드시 구별되지 않는 비밀 $$s\_1, s\_2, \ldots, s\_n$$에 대한 커밋먼트 집합 $$c\_1, c\_2, \ldots, c\_n$$이 있다고 가정해보자. 공격자는 각 $$h^{t\_i}$$를 공격하여 $$g^{s\_i}$$에 해당하는 값들을 복구할 수 있다. 이로부터 공격자는 같은 값에 대한 반복된 커밋먼트를 빠르게 식별할 수 있다. 커밋먼트들이 간단한 선형 관계를 가질 것으로 의심되는 경우(예: 알려진 $$k$$ 값에 대해 $$s\_i = k \cdot s\_j$$ 또는 $$s\_i = s\_j + k$$), 이러한 관계들도 $$g^{s\_i} g^k$$와 $$(g^{s\_i})^k$$를 조사함으로써 복구될 수 있다.
### Reference
1. \[Pedersen91] Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing (1991).
2.
3.
4.
5.
6.
***
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://upsidezkp.gitbook.io/upside-zkp-docs/step-0/prerequisite/cryptographic-commitments.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.