はじめに

本記事では、ゼロ知識証明を非対話で行えるようにしたプロトコルである非対話型ゼロ知識証明（もしくは、ゼロ知識非対話証明）について説明します。非対話型ゼロ知識証明の概要と、これまでの研究の流れ、それから近年主流となっているzk-SNARKとzk-STARKについても簡単に紹介します。

非対話型ゼロ知識証明とは

非対話型ゼロ知識証明とは、やりとりをすることなく証明者から検証者に対して証明を一方的に送りつけるだけで証明が完了するようなゼロ知識証明です。

実際にゼロ知識証明を使う場面では、やりとりを何度も行う対話型であるよりは、一度情報を送ればやりとりが完了するような非対話型で行うことができる方が便利です。非対話化することによって、非同期処理が可能となったり、証明者から検証者に対して一方的に証明を送りつけるだけで本人確認が可能になるなど、多くのメリットがあります。

安全性の仮定

非対話型ゼロ知識証明は、標準的な仮定（プロトコルに対する攻撃者の計算能力が確率的多項式時間であると仮定する）のもとでは、プロトコルに利用する問題に確率的多項式時間で解けてしまうような自明な問題を利用したものしか構築できないことが知られています。つまり、検証者はゼロ知識証明プロトコルを使うまでもなく証明者の証明の正しさを自らの計算によって検証できてしまいます。

そこで、何らかの仮定を置くことが必要となりますが、ベースに据える仮定には大きく分ければ以下の2種類があります。

共通参照情報（CRS: Common Reference String）
証明系を利用するすべての関係者が、信頼できる第三者によって生成された同じ文字列（乱数）を利用できると仮定する。
ランダムオラクル（RO: Random Oracle）
ハッシュ関数を真のランダムな関数であると仮定する。

以下では、これらを仮定するモデルをCRSモデル、ROモデルのように呼称することにします。これらの2つの考え方について、ああ簡単にプロトコルとその特徴を説明します。

CRSモデル

CRSモデルでは、以下のようにプロトコルが進行します。

プロトコルの流れ

信頼できる第三者が共通参照情報 $\sigma$ を生成する。
証明者Pは $(\sigma,x,w)$ に基づいて証明 $\pi$ を送信する。
検証者Vは $(\sigma,x,\pi)$ に基づいて証明者の主張を受け入れるか拒否するかを選ぶ。

CRSの仮定は、様々な効率的暗号プリミティブを構築するのに非常に使いやすいことが知られており、CRSが正しく生成される場合には安全性が保証されます。逆に言えば、CRSを生成する第三者が信頼できないものであれば、安全性には問題が生じます。この問題は、CRSをマルチパーティに分散化すれば解決されるようにも見えますが、それらのパーティ内で結託が起きないことが前提とされます。

ROモデル

ROモデルでのプロトコルの進行を、ここでは構成から示します。

ここではゼロ知識証明プロトコルとして、以下のようなシグマプロトコルを考えます。

プロトコルの設定

証明者Pと検証者Vはともに計算能力が多項式時間に制限されている。
証明者Pと検証者Vには命題 $x$ が与えられ、証明者Pにはその解 $w$ が与えられる。
「命題 $x$ の解 $w$ を知っている」という証明者Pの主張が正しいことを、検証者Vに $w$ を明かすことなく示したいとする。

プロトコルの流れ

証明者Pは検証者Vにメッセージ $a$ を送信する。
検証者Vは証明者Pに乱数 $e$ を送信する。
証明者Pは検証者Vに $z$ を送信する（ここで $z$ は $e$ に依存した値）。検証者Vは $(x,a,e,z)$ に基づいて証明者の主張を受け入れるか拒否するかを選ぶ。

このプロトコルにおいて、乱数 $e$ をランダムオラクル $H$ からの出力で代用してしまうことを考えると、この置き換えによって対話型プロトコルを非対話型プロトコルに変換することができます。この変換手法が**フィアット・シャミア変換（Fiat-Shamir Transform / Fiat-Shamir Heuristic）**です[3]。この変換は、効率的な署名を作成するのによく使われる手法ですが、このように非対話型ゼロ知識証明の構成にも利用されます。この変換によってプロトコルの流れは以下のように変更されます。

プロトコルの流れ

証明者Pはメッセージ $a$ を生成する。これを利用して $e=H(a)$ とする。さらに、 $e$ を利用して $z$ を生成する。
証明者Pは検証者Vに対して $(a,e,z)$ を送信する。
検証者Vは $(x,a,e,z)$ に基づいて証明者の主張を受け入れるか拒否するかを選ぶ。

ただし、現実にはランダムオラクル $H$ は存在しないため、実際には代わりにハッシュ関数が利用されます。

ランダムオラクルの仮定のもとで、実用上効率的なプロトコルを構築することができ、構築したプロトコルの安全性を証明できることが知られています。しかしながら、真にランダムなハッシュ関数は存在しないため、ヒューリスティックな安全性に依存しているという問題もあります。

非対話型ゼロ知識証明の変遷

はじめての非対話型ゼロ知識証明はBlumらによって考案されました[4]。彼らが導入したアイデアがCRSでした。

その後、トラップドア一方向性置換関数（逆算が難しい置換関数だが、トラップドアと呼ばれる秘密鍵があれば逆演算が効率的にできる）の存在を仮定したもとで、非対話型ゼロ知識証明が構成できることが示されました[5]。しかしながら、この方式は決して実用的であるとはいえず、実際の応用例は知られていません。

一方で、実用的なプロトコルを目指し、CRSを利用しないROベースの証明も考案されてきました。

Kilianは効率的な対話ゼロ知識アーギュメントを考案しました[6]。彼は、入力サイズに対して高々対数ビットの乱数列と、それにより位置が定まるおおよそ定数回のクエリを投げるだけでNP問題が解ける（PCP定理）というNP問題の特徴を利用することで、検証に必要な計算量を従来と比較して対数多項式時間に削減することに成功しました。

はじめての簡潔（Succinct、詳細は後述）な非対話ゼロ知識証明は、Micaliによって構成されたRO仮定に基づくものです[7]。その方法は、Kilianの方法を応用して構成した対話型証明をフィアット・シャミア変換を利用して非対話型へ変換したものです。

しばらくの間は、CRSベースの安全性を持つが非効率的な非対話ゼロ知識証明と、効率的だがヒューリスティックな安全性を持つROベースの非対話ゼロ知識証明の2種類が共存していました。しかしながら、ペアリング暗号の登場により、CRSを使った方法でも効率的なプロトコルを作ることができるようになりました[8]。

その後、このアイデアを引き継ぐ形で、QSP（2次スパン問題：Quadratic Span Program）に基づく方法が提案され[9]、これ基づいてPinocchio[10]が実装されました。近年ではより効率的なGroth16[11]がデファクトスタンダードとされている方式になっています。

それでは、ROに基づく研究は下火になってしまったかといえば、そういうわけでもありません。近年のROに基づく手法として代表的にはSTARK[12]が知られており、libstark[13]などの実装が知られています。

zk-SNARKとzk-STARK

ここでは、近年よく使われている非対話型ゼロ知識証明の手法であるzk-SNARKとzk-STARKについて簡単な紹介と比較をします。これら2つの名前は似ていますが、特徴は大きく異なっています。

zk-SNARK

zk-SNARKは、Zero-Knowledge Succinct Non-Interactive Argument of Knowledgeの略です。Zero-Knowledge Argument of Knowledge（知識のゼロ知識アーギュメント）が持つ性質である完全性、（計算量）健全性、ゼロ知識性に加えて

簡潔性（Succinct）
示したい命題の証明が、システム全体の計算量と比較して非常に小さい、もしくは、システム全体の計算量に依存せず一定のサイズである。

の性質を持ちます。

この手法では、証明サイズは一定ですが、証明者や検証者の計算量は命題の複雑さに伴って増加します。また、CRSを利用するために第三者が信頼できるものかどうかという疑問は常につきまとうことになります。さらに、ペアリング暗号の仕組みを利用しているため、耐量子性を持ちません。

zk-STARK

zk-STARKは、Zero-Knowledge Scalable Transparent Argument of Knowledgeの略です。Zero-Knowledge Argument of Knowledgeが持つ3つの性質に加えて

スケーラビリティ（Scalability）
命題の複雑さが証明者と検証者による証明の生成と検証に要する処理時間に対して与える影響が少ない。
透過性（Transparency）
検証者が使用する乱数の生成規則、すなわちランダム性が公開されている。

の性質を持ちます。

この手法では、証明者や検証者の計算量は少なくて済みます。また、ハッシュ関数を利用する（ROに基づく安全性を持つ）ため、第三者のセットアップが不要であり、さらに耐量子性を持ちます。しかしながら、証明サイズは命題の複雑さに伴って増加します。

応用

ここで紹介したzk-SNARKとzk-STARKはいずれも「演算の証明」つまり「証明者が任意の演算が正しく実行されたことを検証者に証明する」ことによく使われており、この仕組みは主にブロックチェーンで応用されています。

まとめ

非対話型ゼロ知識証明は主に共通参照情報（CRS：Common Reference String）モデル、もしくはランダムオラクル（RO：Random Oracle）モデルのもとでの構成が知られている。
CRSを利用したプロトコルは近年ではペアリング写像を利用したものが主流であり、それらはzk-STARKとよばれる。
ROを利用したプロトコルはフィアット・シャミア変換などを利用して構築されることが多く、近年のプロトコルとしてはzk-STARKなどが知られている。
CRSを利用したプロトコルは標準的仮定をおく一方で、第三者の信頼性や耐量子性が問題となる。
ROを利用したプロトコルは第三者のセットアップが不要で耐量子性を持つが、ハッシュ関数の安全性が問題となる。

参考文献

[1] 岡本龍明著. 現代暗号の誕生と発展 : ポスト量子暗号・仮想通貨・新しい暗号. 近代科学社, 2019.

[2] A. Nitulescu. zk-snarks: a gentle introduction, 2020.

[3] A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Crypto, Vol. 86, pp. 186–194. Springer, 1986.

[4] M. BLUM. Non-interactive zero-knowledge and its applications. ACM Symposium on Theory of Computing (STOC) 1988, pp. 103–112, 1988.

[5] U. Feige, D. Lapidot, and A. Shamir. Multiple non-interactive zero knowledge proofs based on a single random string. In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pp. 308–317 vol.1, 1990.

[6] J. Kilian. A note on efficient zero-knowledge proofs and arguments. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pp. 723–732, 1992.

[7] S. Micali. Cs proofs. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 436–453. IEEE, 1994.

[8] J. Groth and A. Sahai. Efficient non-interactive proof systems for bilinear groups. In Advances in Cryptology–EUROCRYPT 2008: 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings 27, pp. 415–432. Springer, 2008.

[9] R. Gennaro, C. Gentry, B. Parno, and M. Raykova. Quadratic span programs and succinct nizks without pcps. In Advances in Cryptology–EUROCRYPT 2013: 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings 32, pp. 626–645. Springer, 2013.

[10] B. Parno, J. Howell, C. Gentry, and M. Raykova. Pinocchio: Nearly practical verifiable computation. Communications of the ACM, Vol. 59, No. 2, pp. 103–112, 2016.

[11] J. Groth. On the size of pairing-based non-interactive arguments. In Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35, pp. 305–326. Springer, 2016.

[12] E. Ben-Sasson, I. Bentov, Y. Horesh, and M. Riabzev. Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, 2018.

[13] https://github.com/elibensasson/libSTARK