ゼロ知識証明

ゼロ知識証明とは

ゼロ知識証明（Zero-Knowledge Proof、ZKP）とは、暗号学における重要な概念の一つで、ある人が特定の命題（通常は数学的なもの）が真であることを、その命題が真であること以外の情報を一切開示せずに、第三者に証明する手法です。この技術は、ゼロ知識対話証明（Zero-Knowledge Interactive Proof、ZKIP）とも呼ばれます。

ゼロ知識証明の概要

ゼロ知識証明の対象となる命題には、例えば、巨大な合成数の素因数を知っていることや、離散対数問題の解を知っていることなど、公開鍵[[暗号]]でよく用いられるものが含まれます。また、任意のNP完全問題の解を持っていることを示すことも可能です。

応用例は多岐にわたり、公開鍵[[暗号]]、デジタル署名、ユーザー認証などに利用されています。特に、ユーザー認証においては、個人情報を入力する際に、その情報自体を公開することなく認証を完了させることができます。ゼロ知識証明の健全性により、不正な入力では証明が失敗し、ゼロ知識性により個人情報が漏洩する心配はありません。

重要な点として、ゼロ知識証明における「証明」は数学的な厳密な証明とは異なり、確率的なものです。つまり、証明者が偽の命題を主張した場合、検証者が誤ってそれを真と判定してしまう可能性（健全性のエラー）がわずかに存在します。しかし、このエラーの発生確率は、実用上無視できるほど小さくすることができます。

ゼロ知識証明の研究は、確率的検査可能証明（Probabilistically Checkable Proof、PCP）という概念を生み出しました。

ゼロ知識対話証明は、1985年にGoldwasser、Micali、Rackoffらによって初めて定式化され、その後の暗号理論の発展に大きく貢献しました。

ゼロ知識証明の3つの条件

実用的なゼロ知識証明は、以下の3つの条件を満たす必要があります。

1. 完全性（Completeness）: 証明者が真の命題を持っている場合、検証者は必ずそれを真であると認識できること。
2. 健全性（Soundness）: 証明者が偽の命題を持っている場合、検証者は高い確率でそれを偽であると見抜けること。
3. ゼロ知識性（Zero-Knowledge）: 証明者が真の命題を持っている場合、検証者が証明の過程で命題が真であること以外の情報を一切得られないこと。これは、知識を持たない検証者でも、正しい証明者との対話記録をシミュレーションできることと同義です。

最初の二つの条件は、対話型証明システム全般に共通するものです。ゼロ知識証明を特徴づけるのは、最後のゼロ知識性です。

場合によっては、健全性よりも強い知識健全性（Knowledge Soundness）が用いられることもあります。知識健全性は、検証者が証明を受け入れた場合、証明者の秘密情報を取り出すことができる効率的なアルゴリズムが存在することを保証します。健全性を知識健全性に置き換えた場合、それは知識のゼロ知識証明（Zero-Knowledge Proof of Knowledge）と呼ばれます。

ゼロ知識証明の具体例：洞窟のたとえ

ゼロ知識証明の概念を理解するための有名な例として、ジャン＝ジャック・キスケータらの論文で紹介された「洞窟の問題」があります。この例では、証明者をP（Prover）、検証者をV（Verifier）とします。

Pは、魔法の扉を開ける合言葉を知っています。その扉は洞窟の奥にあり、入り口からAとBの二つの道を通って到達できます。合言葉を使うと、AからBへ、またはBからAへ移動できます。

Vは、合言葉を知りたいのですが、Pが本当に合言葉を知っているか確認できるまではお金を払いたくありません。一方Pは、お金を受け取るまでは合言葉を教えたくありません。そこで、二人は合言葉そのものを明かすことなく、Pが合言葉を知っていることをVに証明する必要があります。

具体的な手順は次の通りです。

1. まず、Vは洞窟の外で待機し、Pだけが洞窟に入ります。Pは、AまたはBのどちらかの道を選んで奥へ進みます。
2. 次に、Vは洞窟の入り口まで行き、AかBのどちらかの道をランダムに選びます。
3. そして、VはPに対して、選んだ道から出てくるように大声で指示します。この時、VはPがどちらの道から入ったかを知りません。

もしPが合言葉を知っている場合、Vが選んだ道から出てくるのは簡単です。自分が選んだ道と同じ道が選ばれた場合はそのまま戻り、反対の道が選ばれた場合は合言葉を使って扉を開けて反対側から出てきます。しかし、Pが合言葉を知らない場合は、自分が進んだ道からしか出てくることができません。Vが道をランダムに選ぶため、Pが要求に応えられる確率は50％です。この試行を複数回繰り返すことで、Pが全ての要求に応えることはほぼ不可能になります。例えば、20回繰り返すと、全ての要求に応えられる確率は約0.000001%です。したがって、Pが複数回の要求全てに応えられた場合、VはPが本当に合言葉を知っていると納得できます。

この例では、VがPに「片方の道から入って反対の道から出てこい」と要求して証明することも可能に思えます。しかし、この方法ではVがPの動きを追跡し、合言葉を盗み聞くことができます。重要な点は、Vが洞窟の入り口で待機し、Pを追跡できない状態で証明を完了できることです。

ハミルトン閉路問題を用いた具体例

別の具体例として、Pが巨大なグラフGのハミルトン閉路を知っているというケースを考えてみましょう。ハミルトン閉路とは、グラフの全ての点を一度ずつ通り、出発点に戻る経路のことです。巨大なグラフでハミルトン閉路を探すのは非常に難しく、NP完全問題に分類されます。

Pは、ハミルトン閉路そのものをVに教えることなく、自分がハミルトン閉路を知っていることを証明したいと考えています。

証明の手順は以下の通りです。

1. Pは、Gと同型な別のグラフHを用意します。この操作は比較的簡単で、Hのハミルトン閉路がわかれば、Gのハミルトン閉路もわかります。
2. Pは、グラフHの情報をコミットメント方式（または物理的に、各枝の両端の節点番号を紙に書いて鍵付きの箱に入れる）でVに渡します。この時点では、鍵は渡しません。
3. Vは、次の二つの質問のうちどちらかをランダムに選び、Pに回答を求めます。
質問1：「GとHの対応表を示してください。」
質問2：「Hのハミルトン閉路を示してください。」
4. もしVが質問1を選んだ場合、PはHのコミットメントを公開し、GとHの対応表を示します。VはHがGと同型であることを確認できます。
5. もしVが質問2を選んだ場合、PはGのハミルトン閉路を対応表に従って変換し、Hのハミルトン閉路を示します。VはPがHのハミルトン閉路を知っていることを確認できます。

各問答で、VはPがどちらの質問に答えるかを事前に知ることができないため、PがGのハミルトン閉路を知らない限り、両方の質問に答えることはできません。Gのハミルトン閉路を知っている場合のみ、どちらの質問にも対応できるため、この問答を繰り返すことで、VはPがハミルトン閉路を知っていると確信できます。

一方、Pの回答からハミルトン閉路そのものが漏洩することはありません。各問答でVが得られるのは、HがGとどう対応しているか、またはHのハミルトン閉路の経路だけです。各問答で同時に両方の情報を得ることができれば、Gのハミルトン閉路も求まりますが、Vは常にどちらか片方の情報しか得ることができません。このため、Vは各問答で得た情報を積み重ねても、Gのハミルトン閉路についての情報を得ることはできません。

Pがもしハミルトン閉路を知らない場合、どちらか片方の質問には答えることができます。例えば、Gと同型なHを生成して提示するか、適当に閉路を作って枝を追加したHを提示し、最初に用意した閉路をハミルトン閉路として示すことができます。しかし、両方の質問に同時に答えることはできません。問答をn回繰り返す場合、Vの質問に全て答えられる確率は1/2^nとなります。ゼロ知識証明では、この確率を実用的な回数の繰り返しでほぼ0にすることができます。

非対話ゼロ知識証明（NIZK）

GoldreichとOrenの研究により、対話なしでゼロ知識証明を行うことは一般的には不可能であることが示されています。つまり、証明者が一方的に証明を送信するだけで完了するような証明は、通常は作成できません。しかし、特定の条件下では、対話が不要なゼロ知識証明が可能です。これを非対話ゼロ知識証明（Non-Interactive Zero-Knowledge Proof、NIZK）と呼びます。

NIZKは、デジタル署名やプライバシーを重視した暗号通貨などの応用があります。例えば、暗号通貨の取引において、取引者のアドレスや取引量を隠したまま、取引が正当であることを証明する際にNIZKが利用されます。

まとめ

ゼロ知識証明は、情報を開示せずに特定の事実を証明するための強力なツールです。その応用範囲は広く、暗号技術、認証システム、プライバシー保護など、さまざまな分野で活用されています。その理論的な背景や具体的な例を理解することで、現代のデジタル社会における情報セキュリティの重要性をより深く理解することができるでしょう。

もう一度検索