Loading article…
非対話型ゼロ知識証明は、証明者と検証者間の情報を証明者が認証できる暗号プリミティブであり、ステートメント自体の有効性以外の特定の情報を一切公開しません。これにより、証明者と検証者間の直接通信が不要になり、仲介者が事実上排除されます。
非対話型ゼロ知識証明の主な利点は、証明者と検証者の間で対話の可能性がない状況、例えば両者がリアルタイムで通信できないオンライン取引などで使用できることです。これにより、非対話型ゼロ知識証明は、取引がノードのネットワークによって検証され、検証プロセスを監督する中央機関が存在しないブロックチェーンなどの分散型システムで特に役立ちます。 [1]
非対話型ゼロ知識証明のほとんどは、楕円曲線暗号やペアリングベース暗号などの数学的構造に基づいており、ステートメントの真実性を証明する短くて簡単に検証できる証明を作成できます。証明者と検証者の間で複数回の対話を必要とする対話型ゼロ知識証明とは異なり、非対話型ゼロ知識証明は効率的に設計されており、多数のステートメントを同時に検証するために使用できます。[1]
歴史
Blum、Feldman、Micali [2]は1988年に、証明者と検証者の間で共有される共通の参照文字列が、相互作用を必要とせずに計算ゼロ知識を達成するのに十分であることを示した。GoldreichとOren [3]は、標準モデルにおけるワンショットゼロ知識プロトコルの不可能性の結果[明確化が必要]を示した。2003年に、Shafi GoldwasserとYael Tauman Kalaiは、任意のハッシュ関数が安全でないデジタル署名スキームを生成する識別スキームの例を公開した。[4]
モデルはゼロ知識プロトコルから得られる特性に影響を及ぼします。Pass [5]は、共通参照文字列モデルでは、非対話型ゼロ知識プロトコルは対話型ゼロ知識プロトコルのすべての特性を保持しない、つまり否認可能性を保持しないことを示しました。非対話型ゼロ知識証明は、フィアット・シャミールヒューリスティックを使用してランダムオラクルモデルでも取得できます。[要出典]
ブロックチェーンアプリケーション
2012年、アレサンドロ・キエーザらは、ゼロ知識簡潔非対話型知識論証の頭字語であるzk-SNARKプロトコルを開発した。[6] zk-SNARKが最初に広く応用されたのは、ゼロ知識暗号が計算バックボーンを提供するZerocash ブロックチェーンプロトコルであり、一方の当事者が特定の情報を所有していることを数学的に証明し、その情報が何であるかを明らかにすることなく容易にする。 [7] Zcashは、zk-SNARKを利用して、プライベート、シールド、デシールド、パブリックの4つの異なるトランザクションタイプを容易にした。このプロトコルにより、ユーザーは各トランザクションでパブリック台帳と共有されるデータの量を決定できた。[8] イーサリアムzk-ロールアップも、スケーラビリティを向上させるためにzk-SNARKを利用している。[9]
2017年にBulletproofs [10]がリリースされ、フィールドとグループ要素の対数（範囲のビット長）を使用して、コミットされた値が範囲内にあることを証明できるようになりました。[11] Bulletproofsは後にMimblewimbleプロトコル（GrinとBeam、および拡張ブロックを介したLitecoinの基礎）と暗号通貨Moneroに実装されました。[12]
2018年に、zk-STARK （ゼロ知識スケーラブル透明知識論証）[13]プロトコルが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]
以下に、ゼロ知識証明プロトコルとライブラリのリストと、透明性、普遍性、および妥当なポスト量子セキュリティに基づく比較を示します。透過的なプロトコルとは、信頼できるセットアップを必要とせず、公開されたランダム性を使用するプロトコルです。普遍的なプロトコルとは、各回路に個別の信頼できるセットアップを必要としないプロトコルです。最後に、妥当なポスト量子プロトコルとは、量子アルゴリズムを含む既知の攻撃の影響を受けないプロトコルです。
意味
もともと、[2]非対話型ゼロ知識証明は、単一の定理証明システムとしてのみ定義されていました。このようなシステムでは、各証明には独自の新しい共通参照文字列が必要です。共通参照文字列は一般にランダムな文字列ではありません。たとえば、すべてのプロトコル当事者が使用するランダムに選択されたグループ要素で構成される場合があります。グループ要素はランダムですが、参照文字列はランダムではありません。これは、ランダム性と区別できる特定の構造 (グループ要素など) が含まれているためです。その後、Feige、Lapidot、およびShamir [37] は、非対話型ゼロ知識証明のより汎用的な概念として、マルチ定理ゼロ知識証明を導入しました。
ペアリングベースの非対話型証明
ペアリングベースの暗号化は、いくつかの暗号化の進歩をもたらしました。これらの進歩の 1 つは、より強力で効率的な非対話型ゼロ知識証明です。独創的なアイデアは、ペアリング評価の値をコミットメントに隠すことでした。さまざまなコミットメントスキームを使用して、このアイデアは、サブグループの隠蔽[38]と決定線形仮定[39]の下でゼロ知識証明システムを構築するために使用されました。これらの証明システムは回路の充足可能性を証明し、したがってCook–Levin の定理によってNP のすべての言語のメンバーシップを証明できます。共通参照文字列と証明のサイズは比較的小さいですが、ステートメントをブール回路に変換すると、かなりのオーバーヘッドが発生します。
ペアリングベース暗号で一般的なペアリング積方程式を直接証明することを可能にする、サブグループ隠蔽、決定線形仮定、外部ディフィー・ヘルマン仮定に基づく証明システムが提案されている。[40]
強い知識仮定の下では、 NP完全言語に対して、線形長以下の計算的に健全な証明システムを作成する方法が知られています。より正確には、そのような証明システムにおける証明は、少数の双線形群の要素のみで構成されます。[41] [42]
参考文献
- ^ abc 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。
- ^ ab Manuel Blum、Paul Feldman、Silvio Micali。非対話型ゼロ知識とその応用。第20回ACMコンピューティング理論シンポジウム議事録（STOC 1988）。103–112。1988年
- ^ Oded Goldreich と Yair Oren。ゼロ知識証明システムの定義と特性。Journal of Cryptology。Vol 7(1)。1–32。1994 (PS)
- ^ Shafi Goldwasser と Yael Kalai。Fiat-Shamir パラダイムの (不) 安全性について。第 44 回 IEEE コンピュータサイエンス基礎シンポジウム (FOCS'03) の議事録。2003 年
- ^ ラファエル・パス。共通参照文字列とランダムオラクルモデルにおける否認可能性について。暗号学の進歩 - CRYPTO 2003。316-337。2003 (PS)
- ^ 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。
- ^ 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 日閲覧。
- ^ ベン＝サッソン、イーライ;キエーザ、アレッサンドロ。 「zk-SNARKsって何？」 z.現金。2022 年11 月 3 日に取得。
- ^ 「ゼロ知識ロールアップ」ethereum.org . 2023年2月25日閲覧。
- ^ Bünz, Benedikt; Bootle, Jonathan; Boneh, Dan; Poelstra, Andrew; Wuille, Pieter; Maxwell, Greg (2018 年 5 月)。「Bulletproofs: 機密トランザクションなどのための短い証明」。2018 IEEE セキュリティとプライバシーに関するシンポジウム (SP) 。pp . 315–334。doi :10.1109/ SP.2018.00020。ISBN 978-1-5386-4353-2. S2CID 3337741。
- ^ Bünz, Benedikt; Bootle, Jonathan; Boneh, Dan; Poelstra, Andrew; Wuille, Pieter; Maxwell, Greg (2018 年 5 月)。「Bulletproofs: 機密トランザクションなどのための短い証明」( PDF)。2018 IEEE セキュリティとプライバシーに関するシンポジウム (SP)。pp. 315–334。doi :10.1109/ SP.2018.00020。ISBN 978-1-5386-4353-2. S2CID 3337741 . 2022年12月2日閲覧。
- ^ Odendaal, Hansie; Sharrock, Cayle; Heerden, SW. 「Bulletproofs and Mimblewimble」. Tari Labs University. 2020年9月29日時点のオリジナルよりアーカイブ。 2020年12月3日閲覧。
- ^ http://www.cs.technion.ac.il/RESEARCH_DAY_17/POSTERS/michael_riabzev.pdf
- ^ abc Eli Ben-Sasson、Iddo Bentov、Yinon Horesh、Michael Riabzev (2018年3月6日)。「スケーラブルで透明性があり、量子コンピュータでも安全な計算の完全性」(PDF)。国際暗号研究協会。2021年10月24日閲覧。
- ^ ab Bowe, Sean; Grigg, Jack; Hopwood, Daira (2019). 「信頼できるセットアップなしの再帰的証明構成」。Cryptology ePrint Archive。
- ^ 「Pickles SNARK のご紹介: Coda Protocol でスマート コントラクトを有効にする」Mina Protocol . 2023 年 2 月 25 日閲覧。
- ^ Bonneau, Joseph; Meckler, Izaak; Rao, V.; Evan; Shapiro (2021). 「Mina: 大規模な分散型暗号通貨」(PDF) . S2CID 226280610.
- ^ パルノ、ブライアン、ハウエル、ジョン、ジェントリー、クレイグ、レイコバ、マリアナ (2013 年 5 月)。「ピノキオ: ほぼ実用的な検証可能な計算」。2013 IEEE セキュリティとプライバシーに関するシンポジウム。pp. 238–252。doi :10.1109 / SP.2013.47。ISBN 978-0-7695-4977-4. S2CID 1155080。
- ^ コステロ、クレイグ; フルネット、セドリック; ハウエル、ジョン; コールワイス、マルクルフ; クロイター、ベンジャミン; ネイリグ、マイケル; パルノ、ブライアン; ザハール、サミー (2015 年 5 月)。「ジェペット: 多用途で検証可能な計算」。2015 IEEEセキュリティおよびプライバシーシンポジウム。pp. 253–270。doi :10.1109/ SP.2015.23。ISBN 978-1-4673-6949-7. S2CID 3343426。
- ^ 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。ISBN 978-3-642-40084-1。
- ^ 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日閲覧。
- ^ Zhang, Yupeng; Genkin, Daniel; Katz, Jonathan; Papadopoulos, Dimitrios; Papamanthou, Charalampos (2018 年 5 月)。「VRAM: プログラムに依存しない前処理による高速な検証可能 RAM」。2018 IEEE セキュリティおよびプライバシー シンポジウム (SP) 。pp . 908–925。doi :10.1109/ SP.2018.00013。ISBN 978-1-5386-4353-2. S2CID 41548742。
- ^ ベン＝サッソン、イーライ;キエーザ、アレッサンドロ。トロマー、エラン。ヴィルザ、マダース (2014)。フォン・ノイマン アーキテクチャに関する簡潔な {非インタラクティブ} ゼロ知識。 781–796ページ。ISBN 978-1-931971-15-7。
- ^ Kosba, Ahmed; Papadopoulos, Dimitrios; Papamanthou, Charalampos; Song, Dawn (2020). 「MIRAGE: ランダム化アルゴリズムの簡潔な議論とユニバーサルzk-SNARKへの応用」。Cryptology ePrint Archive。
- ^ 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。
- ^ Chiesa, Alessandro; Hu, Yunceng; Maller, Mary; Mishra, Pratyush; Vesely, Noah; Ward, Nicholas (2020). 「Marlin: ユニバーサルで更新可能な SRS による zkSNARK の前処理」。Canteaut, Anne; Ishai, Yuval (編)。暗号学の進歩 – EUROCRYPT 2020。コンピューターサイエンスの講義ノート。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。
- ^ ガビゾン、アリエル; ウィリアムソン、ザカリー J.; シオボタル、オアナ (2019)。「PLONK: 知識のエキュメニカルな非対話型議論のためのラグランジュ基底上の順列」。暗号学 ePrint アーカイブ。
- ^ Bünz, Benedikt; Fisch, Ben; Szepieniec, Alan (2020). 「DARK コンパイラからの透明な SNARK」。Canteaut, Anne; Ishai, Yuval (編)。暗号学の進歩 – EUROCRYPT 2020 。コンピュータサイエンスの講義ノート。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。
- ^ Bünz, Benedikt; Bootle, Jonathan; Boneh, Dan; Poelstra, Andrew; Wuille, Pieter; Maxwell, Greg (2018 年 5 月)。「Bulletproofs: 機密トランザクションなどのための短い証明」。2018 IEEE セキュリティとプライバシーに関するシンポジウム (SP) 。pp . 315–334。doi :10.1109/ SP.2018.00020。ISBN 978-1-5386-4353-2. S2CID 3337741。
- ^ Wahby, Riad S.; Tzialla, Ioanna; Shelat, Abhi; Thaler, Justin; Walfish, Michael (2018 年 5 月)。「信頼できるセットアップなしで二重に効率的な zkSNARK」。2018 IEEEセキュリティおよびプライバシーシンポジウム (SP)。pp. 926–943。doi : 10.1109 /SP.2018.00060。ISBN 978-1-5386-4353-2. S2CID 549873。
- ^ 張 嘉恒; 謝 天成; 張 玉鵬; 宋 暁 (2020 年 5 月)。「透明な多項式委任とゼロ知識証明への応用」。2020 IEEEセキュリティとプライバシーに関するシンポジウム (SP)。pp. 859–876。doi :10.1109/ SP40000.2020.00052。ISBN 978-1-7281-3497-0. S2CID 209467198。
- ^ Ames, Scott; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (2017-10-30). 「Ligero」。2017 ACM SIGSAC コンピュータおよび通信セキュリティ会議の議事録。CCS '17。ニューヨーク、ニューヨーク州、米国: Association for Computing Machinery。pp. 2087–2104。doi : 10.1145/3133956.3134104。ISBN 978-1-4503-4946-8. S2CID 5348527。
- ^ Ben-Sasson, Eli; Chiesa, Alessandro; Riabzev, Michael; Spooner, Nicholas; Virza, Madars; Ward, Nicholas P. (2019). 「Aurora: R1CS の透明で簡潔な議論」。Ishai, Yuval; Rijmen, Vincent (編)。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。
- ^ Ben-Sasson, Eli; Bentov, Iddo; Horesh, Yinon; Riabzev, Michael (2019). 「信頼できるセットアップのないスケーラブルなゼロ知識」。 Boldyreva, Alexandra; Micciancio, Daniele (編)。暗号学の進歩 - CRYPTO 2019。 コンピュータサイエンスの講義ノート。 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。
- ^ Computing、Trustworthy (2021-08-30)。「Zilch による透明なゼロ知識証明」。Medium。2023年2 月 25 日閲覧。
- ^ Mouris, Dimitris; Tsoutsos, Nektarios Georgios (2021). 「Zilch: 透過的なゼロ知識証明を導入するためのフレームワーク」. IEEE Transactions on Information Forensics and Security . 16 : 3269–3284. doi :10.1109/TIFS.2021.3074869. ISSN 1556-6021. S2CID 222069813.
- ^ ウリエル・フェイジ、ドロール・ラピドット、アディ・シャミール：一般的な仮定の下での複数の非対話型ゼロ知識証明。SIAM J. Comput. 29(1): 1–28 (1999)
- ^ Jens Groth、Rafail Ostrovsky、Amit Sahai: NP のための完全な非対話型ゼロ知識。EUROCRYPT 2006: 339–358
- ^ Jens Groth、Rafail Ostrovsky、Amit Sahai: 非対話型 Zap と NIZK の新技術。CRYPTO 2006: 97–111
- ^ Jens Groth、Amit Sahai: 双線形群のための効率的な非対話型証明システム。 EUROCRYPT 2008: 415–432
- ^ Jens Groth. ショートペアリングベースの非対話型ゼロ知識議論。ASIACRYPT 2010: 321–340
- ^ Helger Lipmaa. 進行フリー集合とサブ線形ペアリングベースの非対話型ゼロ知識議論。TCC 2012: 169–189