非対話型ゼロ知識証明

非対話型ゼロ知識証明は暗号プリミティブであり、証明者と検証者間の情報は、証明者が文自体の妥当性以外の具体的な情報を一切明かすことなく認証することができます。これにより、証明者と検証者間の直接的な通信は不要になり、実質的に仲介者を排除できます。

非対話型ゼロ知識証明の主な利点は、証明者と検証者の間で対話の可能性がない状況、例えば両者がリアルタイムで通信できないオンライン取引などにおいて使用できることです。そのため、非対話型ゼロ知識証明は、取引がノードのネットワークによって検証され、検証プロセスを監督する中央機関が存在しないブロックチェーンのような分散型システムにおいて特に有用です。 [ 1 ]

非対話型ゼロ知識証明のほとんどは、楕円曲線暗号やペアリングベース暗号といった数学的構成に基づいており、これにより、文の真偽を示す簡潔で容易に検証可能な証明を作成できます。証明者と検証者の間で複数回の対話を必要とする対話型ゼロ知識証明とは異なり、非対話型ゼロ知識証明は効率性を重視して設計されており、多数の文を同時に検証することができます。[ 1 ]

歴史

ブルーム、フェルドマン、ミカリ[ 2 ]は1988年に、証明者と検証者の間で共有される共通の参照文字列が、相互作用を必要とせずに計算ゼロ知識を実現するのに十分であることを示した。ゴールドライヒとオーレン[ 3 ]は、標準モデルにおけるワンショットゼロ知識プロトコルの不可能性を示した。2003年には、シャフィ・ゴールドワッサーとヤエル・タウマン・カライが、任意のハッシュ関数によって安全でないデジタル署名スキームが生成される識別スキームの例を発表した[ 4 ] 。

モデルは、ゼロ知識プロトコルから得られる特性に影響を与える。Pass [ 5 ]は、共通参照文字列モデルにおいて、非対話型ゼロ知識プロトコルは対話型ゼロ知識プロトコルの特性の全てを保持しない（例えば、否認可能性を保持しない）ことを示した。また、ランダムオラクルモデルにおいても、フィアット・シャミール・ヒューリスティックを用いることで、非対話型ゼロ知識証明を得ることができる。[ 6 ]

ブロックチェーンアプリケーション

最も広く使用されている証明システムの比較

2012年、アレッサンドロ・キエーザらは、ゼロ知識簡潔非対話型知識論証の頭字語であるzk-SNARKプロトコルを開発した。[ 7 ] zk-SNARKが初めて広く応用されたのはZerocashブロックチェーンプロトコルであり、ゼロ知識暗号が計算基盤を提供し、一方の当事者が特定の情報を所有していることを数学的に証明し、その情報が何であるかを明らかにすることなく容易にする。[ 8 ] Zcashはzk-SNARKを利用して、プライベート、シールディング、デシールディング、パブリックの4つの異なるトランザクションタイプを実現した。このプロトコルにより、ユーザーは各トランザクションで公開台帳と共有されるデータの量を決定できた。[ 9 ]イーサリアムのzk-ロールアップもスケーラビリティを向上させるためにzk-SNARKを利用している。[ 10 ]

2017年にはBulletproofs [ 11 ]がリリースされ、これは、フィールドとグループの要素の対数（範囲のビット長）を使用して、コミットされた値が範囲内にあることを証明することを可能にしました。[ 12 ] Bulletproofsは後にMimblewimbleプロトコル（GrinとBeam、および拡張ブロックを介してLitecoinの基礎）と暗号通貨Moneroに実装されました。[ 13 ]

2018 年に、zk-STARK (ゼロ知識スケーラブルで透明な知識論証) プロトコルが Eli Ben-Sasson、Iddo Bentov、Yinon Horesh、Michael Riabzev によって導入され、[ 14 ]透明性 (信頼されたセットアップなし)、準線形証明時間、多重対数検証時間を提供しました。 ゼロ知識簡潔透明知識論証は、一方の当事者 (証明者) がもう一方の当事者 (検証者) に対して特定のステートメントが真であることを証明できるようにする暗号証明システムの一種で、ステートメント自体の真実性以外の追加情報を明らかにする必要はありません。zk-STARK は簡潔であるため、検証しやすい短い証明を作成でき、透明性があるため、誰でも秘密情報を必要とせずに証明を検証できます。[ 14 ]

第一世代のzk-SNARKとは異なり、zk-STARKはデフォルトで信頼されたセットアップを必要としないため、ブロックチェーンのような分散型アプリケーションに特に有用です。さらに、zk-STARKは一度に多くのステートメントを検証できるため、スケーラブルで効率的です。[ 1 ]

2019年には、信頼できるセットアップのないHALO再帰zk-SNARKが発表されました。[ 15 ] Pickles [ 16 ]前者の構成に基づくzk-SNARKは、簡潔に検証可能な最初のブロックチェーンであるMinaの基盤となっています。[ 17 ]

以下に、ゼロ知識証明プロトコルとライブラリのリストと、透明性、普遍性、そして妥当なポスト量子セキュリティに基づく比較を示します。透過的なプロトコルとは、信頼された設定を必要とせず、公開された乱数を利用するプロトコルです。普遍的なプロトコルとは、各回路に個別の信頼された設定を必要としないプロトコルです。最後に、妥当なポスト量子セキュリティを持つプロトコルとは、量子アルゴリズムを含む既知の攻撃の影響を受けないプロトコルです。

非対話型ゼロ知識証明システム
ZKPシステム 出版年 プロトコル 透明 ユニバーサル 量子コンピュータ攻撃に対して安全である可能性が高い
ピノキオ[ 18 ]2013 zk-SNARK いいえ いいえ いいえ
ジェペット[ 19 ]2015 zk-SNARK いいえ いいえ いいえ
タイニーRAM [ 20 ]2013 zk-SNARK いいえ いいえ いいえ
ビュッフェ[ 21 ]2015 zk-SNARK いいえ いいえ いいえ
vRAM [ 22 ]2018 zk-SNARG いいえ はい いいえ
vnTinyRAM [ 23 ]2014 zk-SNARK いいえ はい いいえ
ミラージュ[ 24 ]2020 zk-SNARK いいえ はい いいえ
ソニック[ 25 ]2019 zk-SNARK いいえ はい いいえ
マーリン[ 26 ]2020 zk-SNARK いいえ はい いいえ
PLONK [ 27 ]2019 zk-SNARK いいえ はい いいえ
スーパーソニック[ 28 ]2020 zk-SNARK はい はい いいえ
防弾[ 29 ]2018 防弾 はい はい いいえ
ハイラックス[ 30 ]2018 zk-SNARK はい はい いいえ
ハロー[ 15 ]2019 zk-SNARK はい はい いいえ
乙女座[ 31 ]2020 zk-SNARK はい はい はい
リジェロ[ 32 ]2017 zk-SNARK はい はい はい
オーロラ[ 33 ]2019 zk-SNARK はい はい はい
zk-STARK [ 14 ] [ 34 ]2019 zk-STARK はい はい はい
ゼロ[ 35 ] [ 36 ]2021 zk-STARK はい はい はい

意味

当初、[ 2 ]非対話型ゼロ知識証明は、単一の定理証明システムとしてのみ定義されていました。このようなシステムでは、各証明には独自の新しい共通参照文字列が必要です。共通参照文字列は一般にランダムな文字列ではありません。例えば、すべてのプロトコル当事者が使用するランダムに選択されたグループ要素で構成される場合があります。グループ要素はランダムですが、参照文字列はランダムではありません。これは、ランダム性と区別できる特定の構造（例えば、グループ要素）を含むためです。その後、Feige、Lapidot、およびShamir [ 37 ]は、非対話型ゼロ知識証明のより汎用的な概念として、複数定理ゼロ知識証明を導入しました。

ペアリングベースの非対話型証明

ペアリングベースの暗号は、いくつかの暗号技術の進歩をもたらした。これらの進歩の 1 つは、より強力で効率的な非対話型ゼロ知識証明である。独創的なアイデアは、ペアリング評価の値をコミットメントに隠すというものだった。さまざまなコミットメント スキームを使用して、このアイデアは、サブグループの隠蔽[ 38 ]および決定線形仮定[ 39 ]の下でのゼロ知識証明システムを構築するために使用された。これらの証明システムは回路の充足可能性を証明し、したがってCook–Levin の定理によってNP のすべての言語のメンバーシップを証明できる。共通参照文字列と証明のサイズは比較的小さいが、ステートメントをブール回路に変換するとかなりのオーバーヘッドが発生する。

ペアリングベース暗号で一般的なペアリング積方程式を直接証明することを可能にする、部分群隠蔽、決定線形仮定、外部ディフィー・ヘルマン仮定に基づく証明システムが提案されている。[ 40 ]

強い知識仮定の下では、 NP完全言語に対して、線形長未満で計算的に健全な証明システムを構築する方法が知られている。より正確には、そのような証明システムにおける証明は、少数の双線形群の元のみから構成される。[ 41 ] [ 42 ]

参考文献

  1. ^ a b c Gong, Yinjie; Jin, Yifei; Li, Yuchan; Liu, Ziyi; Zhu, Zhiyi (2022年1月). 「主要なゼロ知識証明スキームの分析と比較」. 2022年国際ビッグデータ・情報・コンピュータネットワーク会議 (BDICN) . pp.  366– 372. doi : 10.1109/BDICN55575.2022.00074 . ISBN 978-1-6654-8476-3. S2CID  248267862 .
  2. ^ a bマヌエル・ブルム、ポール・フェルドマン、シルヴィオ・ミカリ. 非対話型ゼロ知識とその応用. 第20回ACMコンピューティング理論シンポジウム (STOC 1988) の議事録. 103–112. 1988
  3. ^ Oded GoldreichとYair Oren. ゼロ知識証明システムの定義と特性. Journal of Cryptology. Vol 7(1). 1–32. 1994 (PS)
  4. ^シャフィ・ゴールドワッサーとヤエル・カライ. フィアット・シャミール・パラダイムの（不）安全性について. 第44回IEEEコンピュータサイエンス基礎シンポジウム（FOCS'03）議事録. 2003
  5. ^ラファエル・パス. 共通参照文字列とランダムオラクルモデルにおける否認可能性について. 暗号学の進歩 – CRYPTO 2003. 316–337. 2003 (PS)
  6. ^ Wu, H. (2014). 「非対話型ゼロ知識証明システムの概観」 . Scientific World Journal . 2025年9月19日閲覧。
  7. ^ Bitansky, Nir; Canetti, Ran; Chiesa, Alessandro; Tromer, Eran (2012年1月). 「抽出可能な衝突耐性から簡潔な非対話型知識議論へ、そしてまた戻る」 .第3回理論計算機科学イノベーション会議ITCS '12議事録. ACM . pp.  326– 349. doi : 10.1145/2090236.2090263 . ISBN 978-1-4503-1115-1. S2CID  2576177 .
  8. ^ Ben-Sasson, Eli; Chiesa, Alessandro; Garman, Christina; Green, Matthew; Miers, Ian; Tromer, Eran; Virza, Madars (2014年5月18日). 「Zerocash: Bitcoinからの分散型匿名決済」(PDF) . IEEE . 2016年1月26日閲覧。
  9. ^ベン＝サッソン、イーライ;キエーザ、アレッサンドロ。「zk-SNARKsって何？」。 z.現金。2022 年11 月 3 日に取得。
  10. ^ 「ゼロ知識ロールアップ」 . ethereum.org . 2023年2月25日閲覧。
  11. ^ Bünz, Benedikt; Bootle, Jonathan; Boneh, Dan; Poelstra, Andrew; Wuille, Pieter; Maxwell, Greg (2018年5月). 「Bulletproofs: 機密トランザクションなどのための短縮証明」. 2018 IEEE Symposium on Security and Privacy (SP) . pp.  315– 334. doi : 10.1109/SP.2018.00020 . ISBN 978-1-5386-4353-2. S2CID  3337741 .
  12. ^ Bünz, Benedikt; Bootle, Jonathan; Boneh, Dan; Poelstra, Andrew; Wuille, Pieter; Maxwell, Greg (2018年5月). 「Bulletproofs: 機密トランザクションなどのための短縮証明」(PDF) . 2018 IEEE Symposium on Security and Privacy (SP) . pp.  315– 334. doi : 10.1109/SP.2018.00020 . ISBN 978-1-5386-4353-2. S2CID  3337741 . 2022年12月2日閲覧.
  13. ^ Odendaal, Hansie; Sharrock, Cayle; Heerden, SW. 「Bulletproofs and Mimblewimble」 . Tari Labs University. 2020年9月29日時点のオリジナルよりアーカイブ。 2020年12月3日閲覧。
  14. ^ a b c Eli Ben-Sasson、Iddo Bentov、Yinon Horesh、Michael Riabzev (2018年3月6日). 「スケーラブルで透明性があり、量子コンピュータによる安全な計算整合性」(PDF) .国際暗号研究協会. 2021年10月24日閲覧。
  15. ^ a b Bowe, Sean; Grigg, Jack; Hopwood, Daira (2019). 「信頼されたセットアップを使用しない再帰的証明合成」 . Cryptology ePrint Archive .
  16. ^ 「Pickles SNARKのご紹介：Coda Protocolでスマートコントラクトを実現する」 Mina Protocol . 2023年2月25日閲覧。
  17. ^ボノー、ジョセフ、メックラー、アイザック、ラオ、V、エヴァン、シャピロ (2021). 「Mina：大規模な分散型暗号通貨」（PDF） . S2CID 226280610 . 
  18. ^パーノ, ブライアン; ハウエル, ジョン; ジェントリー, クレイグ; レイコバ, マリアナ (2013年5月). 「ピノキオ：ほぼ実用的な検証可能計算」. 2013 IEEE セキュリティとプライバシーシンポジウム. pp.  238– 252. doi : 10.1109/SP.2013.47 . ISBN 978-0-7695-4977-4. S2CID  1155080 .
  19. ^クレイグ・コステロ、セドリック・フルネット、ジョン・ハウエル、マルクルフ・コールワイス、ベンジャミン・クロイター、マイケル・ネーリッグ、ブライアン・パルノ、サミー・ザフル（2015年5月）。「Geppetto：多用途で検証可能な計算」。2015 IEEE セキュリティ・プライバシーシンポジウム、 pp .  253– 270。doi : 10.1109/ SP.2015.23。ISBN 978-1-4673-6949-7. S2CID  3343426 .
  20. ^ Ben-Sasson, Eli; Chiesa, Alessandro; Genkin, Daniel; Tromer, Eran; Virza, Madars (2013). 「SNARKs for C: プログラム実行の簡潔かつゼロ知識検証」 . Canetti, Ran; Garay, Juan A. (編). Advances in Cryptology – CRYPTO 2013 . Lecture Notes in Computer Science. Vol. 8043. ベルリン、ハイデルベルク: Springer. pp.  90– 108. doi : 10.1007/978-3-642-40084-1_6 . hdl : 1721.1/87953 . ISBN 978-3-642-40084-1。
  21. ^ Wahby, Riad S.; Setty, Srinath; Ren, Zuocheng; Blumberg, Andrew J.; Walfish, Michael (2015).検証可能なアウトソーシング計算における効率的なRAMと制御フロー. doi : 10.14722/ndss.2015.23097 . ISBN 978-1-891562-38-9. 2023年2月25日閲覧。
  22. ^ Zhang, Yupeng; Genkin, Daniel; Katz, Jonathan; Papadopoulos, Dimitrios; Papamanthou, Charalampos (2018年5月). 「VRAM: プログラムに依存しない前処理による高速検証可能RAM」. 2018 IEEE Symposium on Security and Privacy (SP) . pp.  908– 925. doi : 10.1109/SP.2018.00013 . ISBN 978-1-5386-4353-2. S2CID  41548742 .
  23. ^ベン＝サッソン、イーライ;キエーザ、アレッサンドロ。トロマー、エラン。ヴィルザ、マダース (2014)。フォン・ノイマン アーキテクチャに関する簡潔な {非インタラクティブ} ゼロ知識。 USENIX協会。ページ 781–796。ISBN​​ 978-1-931971-15-7。
  24. ^ Kosba, Ahmed; Papadopoulos, Dimitrios; Papamanthou, Charalampos; Song, Dawn (2020). 「MIRAGE: ランダム化アルゴリズムの簡潔な議論とユニバーサルzk-SNARKへの応用」 . Cryptology ePrint Archive .
  25. ^ Maller, Mary; Bowe, Sean; Kohlweiss, Markulf; Meiklejohn, Sarah (2019-11-06). 「Sonic」 . 2019 ACM SIGSAC コンピュータと通信セキュリティ会議議事録. CCS '19. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  2111– 2128. doi : 10.1145/3319535.3339817 . ISBN 978-1-4503-6747-9. S2CID  60442921 .
  26. ^ Chiesa, Alessandro; Hu, Yunceng; Maller, Mary; Mishra, Pratyush; Vesely, Noah; Ward, Nicholas (2020). 「Marlin: ユニバーサルかつ更新可能なSRSによるzkSNARKの前処理」 . Canteaut, Anne; Ishai, Yuval (編). Advances in Cryptology – EUROCRYPT 2020 . Lecture Notes in Computer Science. Vol. 12105. Cham: Springer International Publishing. pp.  738– 768. doi : 10.1007/978-3-030-45721-1_26 . ISBN 978-3-030-45721-1. S2CID  204772154 .
  27. ^ガビゾン、アリエル、ウィリアムソン、ザカリー・J、チオボタル、オアナ (2019). 「PLONK: ラグランジュ基底上の順列による、エキュメニカルな非対話型知識論証」暗号学eプリントアーカイブ.
  28. ^ Bünz, Benedikt; Fisch, Ben; Szepieniec, Alan (2020). 「DARKコンパイラからの透過的なSNARK」 . Canteaut, Anne; Ishai, Yuval (編). Advances in Cryptology – EUROCRYPT 2020 . Lecture Notes in Computer Science. Vol. 12105. Cham: Springer International Publishing. pp.  677– 706. doi : 10.1007/978-3-030-45721-1_24 . ISBN 978-3-030-45721-1. S2CID  204892714 .
  29. ^ Bünz, Benedikt; Bootle, Jonathan; Boneh, Dan; Poelstra, Andrew; Wuille, Pieter; Maxwell, Greg (2018年5月). 「Bulletproofs: 機密トランザクションなどのための短縮証明」. 2018 IEEE Symposium on Security and Privacy (SP) . pp.  315– 334. doi : 10.1109/SP.2018.00020 . ISBN 978-1-5386-4353-2. S2CID  3337741 .
  30. ^ Wahby, Riad S.; Tzialla, Ioanna; Shelat, Abhi; Thaler, Justin; Walfish, Michael (2018年5月). 「信頼されたセットアップなしで二重に効率的なzkSNARKs」. 2018 IEEE Symposium on Security and Privacy (SP) . pp.  926– 943. doi : 10.1109/SP.2018.00060 . ISBN 978-1-5386-4353-2. S2CID  549873 .
  31. ^ Zhang, Jiaheng; Xie, Tiancheng; Zhang, Yupeng; Song, Dawn (2020年5月). 「透明な多項式委任とゼロ知識証明への応用」. 2020 IEEE Symposium on Security and Privacy (SP) . pp.  859– 876. doi : 10.1109/SP40000.2020.00052 . ISBN 978-1-7281-3497-0. S2CID  209467198 .
  32. ^ Ames, Scott; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (2017-10-30). "Ligero" . Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security . CCS '17. ニューヨーク、ニューヨーク州、米国: Association for Computing Machinery. pp.  2087– 2104. doi : 10.1145/3133956.3134104 . ISBN 978-1-4503-4946-8. S2CID  5348527 .
  33. ^ Ben-Sasson, Eli; Chiesa, Alessandro; Riabzev, Michael; Spooner, Nicholas; Virza, Madars; Ward, Nicholas P. (2019). 「Aurora: Transparent Succinct Arguments for R1CS」 . Ishai, Yuval; Rijmen, Vincent (eds.). Advances in Cryptology – EUROCRYPT 2019 . Lecture Notes in Computer Science. Vol. 11476. Cham: Springer International Publishing. pp.  103– 128. doi : 10.1007/978-3-030-17653-2_4 . ISBN 978-3-030-17653-2. S2CID  52832327 .
  34. ^ Ben-Sasson, Eli; Bentov, Iddo; Horesh, Yinon; Riabzev, Michael (2019). 「信頼されたセットアップを必要としないスケーラブルなゼロ知識」 . Boldyreva, Alexandra; Micciancio, Daniele (編). Advances in Cryptology – CRYPTO 2019 . Lecture Notes in Computer Science. Vol. 11694. Cham: Springer International Publishing. pp.  701– 732. doi : 10.1007/978-3-030-26954-8_23 . ISBN 978-3-030-26954-8. S2CID  199501907 .
  35. ^ Computing, Trustworthy (2021年8月30日). 「Zilchによる透明なゼロ知識証明」 . Medium . 2023年2月25日閲覧。
  36. ^ Mouris, Dimitris; Tsoutsos, Nektarios Georgios (2021). 「Zilch: 透過的なゼロ知識証明を導入するためのフレームワーク」. IEEE Transactions on Information Forensics and Security . 16 : 3269–3284 . Bibcode : 2021ITIF...16.3269M . doi : 10.1109/TIFS.2021.3074869 . ISSN 1556-6021 . S2CID 222069813 .  
  37. ^ウリエル・ファイゲ、ドロール・ラピドット、アディ・シャミール：「一般的な仮定の下での多重非対話型ゼロ知識証明」SIAM J. Comput. 29(1): 1–28 (1999)
  38. ^ Jens Groth、Rafail Ostrovsky、Amit Sahai：「NPのための完全な非対話型ゼロ知識」 EUROCRYPT 2006: 339–358
  39. ^ Jens Groth、Rafail Ostrovsky、Amit Sahai：「非対話型ZapとNIZKの新技術」CRYPTO 2006: 97–111
  40. ^ Jens Groth, Amit Sahai: 双線形群のための効率的な非対話型証明システム EUROCRYPT 2008: 415–432
  41. ^ Jens Groth. ショートペアリングベースの非対話型ゼロ知識証明. ASIACRYPT 2010: 321–340
  42. ^ヘルガー・リップマー. 漸進自由集合と劣線形ペアリングに基づく非対話型ゼロ知識議論. TCC 2012: 169–189
「 https://en.wikipedia.org/w/index.php?title=Non-interactive_zero-knowledge_proof&oldid=1320899284」より取得