KZG 多項式コミットメント

KZG 多項式コミットメント (Kate-Zaverucha-Goldberg)

多項式 $f(X)$ に対して短いコミットメント (1 群要素) を発行し、後から「$f(z)=y$ である」という点の評価を、多項式全体を開示せずに高速に証明・検証できる仕組み。zk-SNARK の構成要素として広く使われる。

何が嬉しいか

• コミットメントとして使える: 値（ここでは多項式）を固定したことを公開し、後で改竄できない。
• 多項式上の点の包含 / 評価判定を定数サイズの証明で高速に検証できる。コミットも証明も 1 群要素で済むのが格子・Merkle ベースに対する利点。

仕組みの直観

楕円曲線ペアリングと、信頼できるセットアップで生成した秘密点 $\tau$ のべき $\{[{\tau }^i]G\}$ (structured reference string) を使う。

• commit: $C=[f(\tau )]G$。$\tau$ は誰も知らないので $C$ から $f$ は復元できない。
• open ($f(z)=y$ の証明): 因数定理より $f(X)-y$ は $(X-z)$ で割り切れる。商多項式 $q(X)=\frac{f(X)-y}{X-z}$ のコミット $\pi =[q(\tau )]G$ を証明として送る。
• verify: ペアリング $e$ で $e(C-[y]G,G)\stackrel{?}{=}e(\pi ,[\tau ]G-[z]G)$ を確認。これは $f(\tau )-y=q(\tau )(\tau -z)$ をペアリング上でチェックしているだけ。

文脈

• ゼロ知識証明全般は zk-proofs を参照。Σ-protocol（対話的・知識証明）とは別系統で、KZG は非対話な多項式 IOP / SNARK の土台になる。
• 楕円曲線・ペアリングの基礎は ecdh-key-exchange の楕円曲線群が前提。
• 関心の起点: 「コミットメントとして使え、点の包含判定が高速」という性質が CryptoHack の ZKP 系演習に向けて気になった (2024-11)。

関連ノート

• _moc-crypto