🦔

ゼロ知識証明の論文紹介

2023/05/01に公開

はじめに

ゼロ知識証明の概要は雰囲気で理解していますが、もう少し踏み込んだ知識を得るために有名な論文をざっくり読んだので紹介します。
内容を完全に理解したわけではなく、現時点まで到達するまでの流れをなんとなく頭に入れるのが目的なのでもし間違っていたらご指摘頂けると幸いです。

非対話式のzkpは対話式より一般的に検証が早い
元々SNARG（Succinct Non-interactive ARGument）という概念が存在しており、ECRHが存在すれば、ある知識（Knowledge）についても証明でき、これをSNARKと呼ぶ。定義的には、健全性（Soundness）が強化されたSNARGのことをSNARKと呼ぶ。
ECRH：Extractable Collision-Resistant Hash functions：耐衝突性を持ち、かつ生成したハッシュ値はハッシュ化の際に使ったkeyが分かっていればハッシュ化前の元の値を導出できる関数
SNARKs自体はzkpに特化したものではなく、CRS(Common Reference String) ModelにおいてZK-SNARKsを得られる

Grothさんが書いた2016年の論文だからGroth16っていうのかも
元々Grothさんはペアリングを用いたNIZK（Non-Interactive Zero Knowledge）を実現していて、計算量の部分を改善したものがGroth16
算術回路の充足可能性問題について、3つの群要素のみでNIZKを実現している
検証も容易で、ステートメントのサイズに比例する数の指数計算と、3つのペアリングしかない単一のペアリング積の方程式をチェックするだけで良い
セキュリティに関しては一般的な双線型群（Bilinear Group Model）におけるセキュリティに依存する

同じSRS（Structured Reference String）をある境界内のサイズを持つ回路に関して使い回すことができる、かつ更新も可能であることがzk-SNARKsの目下の注目事である。
PlonkはSonicと呼ばれるzk-SNARKのアルゴリズムより証明書の実行時間が大幅に改善した

zk-SNARKsはセットアップフェーズが必要なため、透明性がない。また、このフェーズで非公開のランダム性を用いるため、漏洩するとセキュリティに問題が発生する
現時点では、zk-STARKsはzk-SNARKsより約1000倍時間がかかるため、短縮化が課題
zk-STARKsとの比較対象として、hPKC（Homomorphic public-key cryptography）、DLP（Discretelogarithmproblem）、IP（Interactive Proofs based）、MPC（Secure multi-party computation）、IVC（Incrementally Verifiable Computation）+　hPKCを上げている（いずれも、zk、チューリング完全、コードで実現しているシステム）
Scalable and Transparent IOP of Knowledge(STIK)を実現することで結果としてSTARKが実現できている
IOP（Interactive Oracle Proof）とは一種のゼロ知識証明
STARKは主に2種類
- Interactive STARK（iSTARK）: 対話型STARK
- Non-interactive STARK(nSTARK): 非対話型STARK
非対話型STARKは、証明者からの単一のメッセージで構成されるという利点がある一方で、より強い仮定に依存している。（この仮定はよく分からず）

（）内の年数は論文に書いてある数字をそのまま転記したものなので、提出年、発行年等は曖昧ですのでご注意ください。
新しく論文読んだり、理解を深める度にこの辺は更新できたらと思います。