# KZG commitment scheme (PolyCommit\_Ped) {% hint style="warning" %} **목표 : 이 문서는 KZG 구조 위에 Pedersen 스타일 블라인딩을 얹어 정의되는 PolyCommit\_Ped 스킴의 전체 흐름을 정리하고, 이 스킴이 어떻게 무조건적 은닉성을 달성하는지 이해하는데 있다.** {% endhint %} 앞서 PolyCommit\_DL 스킴은 상수 크기 커밋, 증명과 효율적인 검증을 제공하지만, 기본적으로 계산적 은닉성만 제공한다는 한계가 있다. PolyCommit\_Ped는 이러한 DL 스킴의 구조를 유지하면서도 완전한 은닉성(unconditional hiding)을 제공하기 위해 Pedersen 스타일의 블라인딩을 다항식 커밋에 도입한 확장 커밋이다. ### PolyCommit\_Ped PolyCommit\_Ped는 앞서 간단히 설명한 페더슨 커밋먼트의 핵심 아이디어를 다항식 커밋먼트에 적용한 버전이다. 이 스킴의 목표는 계산 능력이 무한한 공격자에게도 커밋된 다항식에 대한 어떠한 정보도 노출하지 않는 더 강력한 **무조건적 은닉성(Unconditional Hiding)**을 달성하는 것이다. 이를 위해 원본 다항식 $$\phi(x)$$ 외에 내용을 가리는 용도로만 사용되는 동일한 차수의 무작위 다항식 $$\hat\phi(x)$$를 추가로 사용한다. 기본적인 작동 원리는 PolyCommit\_DL과 마찬가지로 "$$\phi(x)-\phi(i)$$는 항상 $$(x-i)$$로 나누어 떨어진다"는 대수적 속성을 기반으로 한다. #### Setup$$(1^k, t)$$ Setup 단계에서는 스킴에 필요한 공개 파라미터를 생성한다. 이 과정은 신뢰할 수 있는 기관에 의해 한 번만 수행된다. * **그룹 및 페어링 설정**: PolyCommit\_DL과 마찬가지로 소수 차수 $$p$$를 갖는 두 그룹 $$\mathbb{G}, \mathbb{G\_T}$$와 이들 사이의 대칭 빌리니어 페어링 $$e: \mathbb{G} \times \mathbb{G} \to \mathbb{G}\_T$$를 설정한다. * **생성원 선택:** 페더슨 커밋먼트처럼 서로 독립적인 두 개의 생성원 $$g, h \in\_R \mathbb{G}$$를 무작위로 선택한다. * **비밀 값 생성**: 비밀 값으로 $$\alpha \in\_R \mathbb{Z}^\*\_p$$를 무작위로 선택한다. 이 값은 생성 후 안전하게 파기되어야 한다. * **공개 키 생성**: 생성된 비밀 값 $$\alpha$$와 두 생성원 $$g, h$$를 사용하여 다음과 같이 공개 키를 계산한다. * $$PK = \langle G, g, g^{\alpha}, \dots, g^{\alpha^t}, h, h^{\alpha}, \dots, h^{\alpha^t} \rangle$$ #### Commit$$(PK, \phi(x))$$ Committer는 차수가 $$t$$이하인 다항식 $$\phi(x)$$에 대해 다음과 같이 커밋먼트 $$C$$를 생성한다. * **무작위 다항식 선택**: 원본 다항식 $$\phi(x)$$의 정보를 가리기 위해 동일한 최대 차수 $$t$$를 갖는 무작위 다항식 $$\hat\phi(x)$$를 선택한다. * **커밋먼트 계산**: 두 다항식 $$\phi(x)$$와 $$\phi'(x)$$를 비밀 지점 $$\alpha$$에서 평가하고 각각을 다른 생성원 $$g$$와 $$h$$에 묶어서 최종 커밋먼트 $$C$$를 계산한다. * $$C = g^{\phi(\alpha)}, h^{\hat\phi(\alpha)}$$ * 다항식 $$\phi(x) = \sum\_{j=0}^{t} \phi\_j x^j$$와 $$\hat{\phi}(x) = \sum\_{j=0}^{t} \hat{\phi}\_j x^j$$가 주어졌을 때, 이 계산은 공개 키를 사용하여 다음과 같이 수행된다. $$C = \left( \prod\_{j=0}^{deg(\phi)} (g^{\alpha^j})^{\phi\_j} \right) \left( \prod\_{j=0}^{deg(\hat{\phi})} (h^{\alpha^j})^{\hat{\phi}\_j} \right)$$ #### Open$$(PK, C, \phi(x), \hat{\phi}(x)) \ \mathbf{&} \ VerifyPoly(PK, C, \phi(x), \hat{\phi}(x))$$ * **Open**: 커미터는 커밋먼트 생성에 사용했던 두 다항식 $$\phi(x)$$와 $$\hat{\phi}(x)$$를 모두 공개한다. * **VerifyPoly**: 검증자는 공개된 두 다항식과 공개 키를 이용해 $$g^{phi(\alpha)}$$값을 직접 다시 계산해봅니다. 이 계산 결과가 처음에 받았던 커밋먼트 $$C$$와 일치하는지 확인하여 성공 또는 실패를 결정합니다. #### CreateWitness$$(PK, \phi(x), \hat{\phi}(x), i)$$ 특정 지점 $$i$$에서의 평가값 $$\phi(i)$$가 맞다는 것을 증명하기 위한 witness $$w\_i$$를 생성한다. * **몫 다항식 계산**: PolyCommit\_DL과 마찬가지로, 두 다항식 각각에 대해 나눗셈을 수행하여 몫 다항식 $$\psi\_i(x)$$와 $$\hat\psi\_i(x)$$를 계산한다. * $$\psi\_i(x) = \frac{\phi(x)-\phi(i)}{x-i}, \hat{\psi}\_i(x) = \frac{\hat{\phi}(x)-\hat{\phi}(i)}{x-i}$$ * **witness 계산**: 두 몫 다항식을 비밀 지점 $$\alpha$$에서 평가하고, 이를 각각의 생성원에 묶어서 단일 위트니스 $$w\_i$$를 생성한다. * $$w\_i = g^{\phi\_i(\alpha)}h^{\hat\psi\_i(\alpha)}$$ * **출력**: 최종적으로 평가값들과 witness를 포함하는 튜플 $$\langle i, \phi(i), \hat{\phi}(i), w\_i \rangle$$를 출력한다. #### VerifyEval$$(PK, C, i, \phi(i), \hat{\phi}(i), w\_i)$$ 검증자는 공개된 정보들을 사용하여 $$\phi(i)$$가 커밋먼트 $$C$$에 해당하는 다항식의 올바른 평가값인지 확인한다. * **검증 방정식:** 검증은 다음의 페어링 기반 등식이 성립하는지 확인하는 것으로 이루어진다. * $$e(\mathcal{C}, g) = e(w\_i, g^{\alpha}/g^i) \cdot e(g^{\phi(i)}h^{\hat{\phi}(i)}, g)$$ * **방정식 유도 과정**: 이 검증 방정식은 PolyCommit\_DL과 유사한 과정으로 유도된다. 1. 기본 다항식 항등식 * $$\phi(x) = \psi\_i(x)(x - i) + \phi(i)$$ * $$\hat{\phi}(x) = \hat{\psi}\_i(x)(x - i) + \hat{\phi}(i)$$ 2. 비밀 값 $$\alpha$$ 대입 * $$\phi(\alpha) = \psi\_i(\alpha)(\alpha - i) + \phi(i)$$ * $$\hat{\phi}(\alpha) = \hat{\psi}\_i(\alpha)(\alpha - i) + \hat{\phi}(i)$$ 3. 커밋먼트 $$C$$를 위 항등식을 이용해 재구성 $$C = g^{\phi(\alpha)} h^{\hat{\phi}(\alpha)} = g^{\psi\_i(\alpha)(\alpha-i)+\phi(i)} \cdot h^{\hat{\psi}\_i(\alpha)(\alpha-i)+\hat{\phi}(i)}$$ 4. 지수 법칙을 이용해 항을 재배열 $$\mathcal{C} = \left( g^{\psi\_i(\alpha)} h^{\hat{\psi}\_i(\alpha)} \right)^{(\alpha-i)} \cdot g^{\phi(i)} h^{\hat{\phi}(i)}$$ 5. $$w\_i = g^{\psi\_i(\alpha)} h^{\hat{\psi}\_i(\alpha)}$$로 치환 $$C = w\_i^{(\alpha-i)} \cdot g^{\phi(i)} h^{\hat{\phi}(i)}$$ 6. 양변에 페어링 $$e(\cdot, g)$$를 적용하고 전개하면 최종 검증 방정식이 도출된다. ### 보안 분석 및 고급 기능 지금까지 PolyCommit 스킴이 어떻게 작동하는지 살펴보았다. 이제 이 스킴이 얼마나 안전하고 또 어떤 유용한 추가 기능들을 가지고 있는지 알아보겠다. #### 핵심 보안 속성 분석 PolyCommit 스킴의 신뢰성은 여러 공식적인 보안 속성들로 뒷받침 되며 각 속성은 특정 암호학적 문제들이 "매우 풀기 어렵다"는 가정에 의해 보장된다. * **다항식 구속성(Polynomial Binding):** 이 속성은 커미터가 한번 커밋먼트 $$C$$를 공개한 뒤에 "사실 제가 커밋했던 다항식은 $$\phi(x)$$가 아니라 $$\phi'(x)$$였다.”라고 말을 바꾸는 것을 불가능하게 만든다. 하나의 커밋먼트가 서로 다른 두 다항식에 대응될 수 없다는 의미이다. 이 속성은 t-SDH 가정이 깨기 어렵다는 점에 직접적으로 의존한다. * **평가 구속성(Evaluation Binding):** 이는 다항식 구속성과 비슷하지만 다항식 전체가 아닌 특정 한 지점의 평가값에 대한 속성이다. 공격자가 동일한 커밋먼트 $$C$$와 인덱스 $$i$$에 대해, "$$\phi(i)$$의 값은 $$y$$입니다."라고 주장했다가 나중에 "$$y'$$입니다." 라고 말을 바꾸며 각각에 대한 유효한 증거를 모두 만들어내는 것은 불가능해야 한다. 이 역시 t-SDH 가정에 의해 보장된다. * **은닉성(Hiding)**: 이 스킴은 **무조건적 은닉성**을 제공합니다. 커밋 과정에서 진짜 다항식 $$\phi(x)$$ 외에 완전히 무작위적인 다항식 $$\hat\phi(x)$$를 섞어주기 때문에 계산 능력이 무한한 공격자라 할지라도 커밋먼트 $$C$$로부터 $$\phi(x)$$에 대한 어떤 정보도 통계적으로 알아낼 수 없다. * **강력한 정확성(Strong Correctness):** 이 속성은 커미터가 저지를 수 있는 또 다른 종류의 속임수를 방지한다. 예를 들어 시스템의 규칙상 최대 차수가 $$t$$로 정해져 있는데 공격자가 몰래 $$t$$보다 더 높은 차수의 다항식에 대해 커밋한 후 검증을 통과시켜 검증자를 속이는 것이 불가능해야 한다는 것이다. 이 속성은 특히 VSS(검증 가능한 비밀 공유)와 같은 응용에서 악의적인 딜러가 규칙을 어기는 것을 막는 데 매우 중요하며 t-polyDH 가정이 깨기 어렵다는 것에 기반한다. ### 결론 PolyCommit\_Ped는 KZG 구조가 제공하는 다항식 수준의 Correctness, Binding를 그대로 유지하면서, 여기에 Pedersen 스타일의 무작위 다항식 $$\hat\phi(x)$$를 섞어 넣어 무조건적 은닉성까지 확보한 변형이다. 커밋/위트니스는 여전히 상수 크기이고, 동형성, 배치 개방 같은 KZG의 장점도 그대로 유지되므로, 실제 프로토콜 설계에서는 PolyCommit\_DL을 거의 손대지 않고 교체 가능한, Hiding이 강화된 버전이라고 볼 수 있다. 다음 문서에서는 PolyCommit\_Ped를 다항식에 대해 커밋, 평가, 검증을 수행하는 기본 암호 프리미티브로 보고, Plonk가 회로 제약을 단일 다항식으로 통합한 뒤 이 프리미티브를 어떻게 활용해 검증하는지 살펴본다. ### Reference 1. --- # 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-2/kzg-plonk/kzg-commitment-scheme-polycommit_ped.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.