Table of Contents

はじめに

知識証明に関する論文の証明[2]を読んでいると、証明の健全性を示すために「知識抽出機」(Knowledge Extractor)なるアルゴリズムの存在を示そうとすることがあります。
知識抽出機が存在するか、すなわち知識抽出可能であるかどうか(Knowledge Extractability; KE; 知識抽出可能性)と、証明の健全性というのはあまり関連がないトピックのように思えます。
[1] の回答で、この関係について明快に説明しているものがあったため紹介します。

定義

統計的健全性を示すための知識抽出機は以下のような文脈で登場する。[1]より引用。
具体的には、証明者アルゴリズムを固定して様々な入力を与え、その出力を用いて知識抽出を行う構成になっている。
（なお、ゼロ知識証明の場合には検証者アルゴリズムとやりとりする際に知識抽出ができてしまっては困るので、実行のたびに異なる乱数を使ったり、複数回の実行を行わないように注意することになるだろう。複数回の証明者との対話を、検証者がextractorアルゴリズムを用いて行えてしまうと、本来漏れてはいけない情報が検証者に漏れてしまうので、検証者がextractorアルゴリズムを用いることはできないはず。困るのはゼロ知識証明の場合だけで、universal argumentsなど一般の知識証明の場合では知識が知られても困らない）

先に述べたシミュレータと同様に、特別なアルゴリズムの存在を証明する必要がある。このアルゴリズムは知識抽出機と呼ばれ、まさにその名の通り知識抽出を行う。知識抽出機（略して「抽出機」）は、証明者と対話する特殊な検証器であり、証明者が証明の完了に成功すれば、抽出機は証明者の元の秘密を抽出できるはずである。そして、これが上記の質問の答えである。知識の証明の健全性を証明するためには、すべての可能な証明者に対して抽出機が存在することを示す必要がある。

証明の統計的健全性(Soundness)は以下のとおりである。

ステートメントが正しくない場合、悪意のある証明者が受理可能な証明を生成する確率は無視できる

また、証明の計算量的健全性(Computational Soundness)は以下のとおりである。

ステートメントが正しくない場合、悪意のある確率的多項式時間チューリングマシンである証明者が受理可能な証明を生成する確率は無視できる

詳細

統計的KEと統計的健全性の関係

「証明者アルゴリズムに対して知識抽出機が存在するならば、知識証明アルゴリズムは統計的に健全である」ということを示す。

下記が統計的KEの仮定である。

無視できない確率で「受理される証明」を生成する、任意の（悪意があるかもしれない）証明者アルゴリズムを考える。この証明者と対話し、そのステートメントが真であるという証拠wを回復する（多項式時間）抽出機が存在する。 ... (統計的KE)

(統計的KE)が成り立つならば、以下が成り立つ。

無視できない確率で「受理される証明」を生成する（悪意があるかもしれない）証明者アルゴリズムが存在するならば、ステートメントは必ず真である（＝証拠wがそのステートメントの確実な答えである）。

この対偶を取ると以下のようになる。

もしもステートメントが真でないならば、「受理される証明」を生成する（悪意があるかもしれない）証明者アルゴリズムは無視できる確率でしか存在しない。 ... (統計的健全性)

よって (統計的KE) => (統計的健全性) が示された。

計算量的KEと計算量的健全性の関係

下記が統計的KEの仮定である。

多項式時間チューリングマシン証明者が「受理される証明」を生成できるとき、証明者から証拠wを抽出できる知識抽出機が存在するか、もしくは難しい問題を破るために証明者のアルゴリズムを利用できる。 ... (計算量的KE)

ここで難しい問題を破れないという仮定（例えば、離散対数問題など）と組み合わせると、以下が推論できる。すなわち、証拠を抽出できるならばステートメントが必ず真とわかる。

無視できない確率で「受理される証明」を生成する（悪意があるかもしれない）多項式時間チューリングマシン証明者アルゴリズムが存在するならば、ステートメントは必ず真である（＝証拠wがそのステートメントの確実な答えである）。

この対偶を取ると以下のようになる。

もしもステートメントが真でないならば、「受理される証明」を生成する（悪意があるかもしれない）多項式時間チューリングマシン証明者アルゴリズムは無視できる確率でしか存在しない。 ... (計算量的健全性)

よって (計算量的KE) => (計算量的健全性) が示された。

まとめ

知識抽出可能性とは、結局の所「正直者は確実に答えを知っており、嘘つきはとても運が良い場合にしか正しく答えられない（＝だから、証明が正しいならほとんどの場合は正直者だ）」という説明の中の「正直者が確実に答えを知っている」部分を定式化するためにバックドア的に用意されたツールだと理解しました。

ゼロ知識証明の場合には、知識抽出可能性を仮定するゼロ知識の証明者側のアルゴリズムは、検証者から見て「知識が抽出できてはならない」という制約があるにもかかわらず、知識抽出アルゴリズムの存在が健全性の条件から要求されているというのは興味深いです。ゼロ知識証明でない一般の知識証明の場合には素直に理解できると思います。

実際に知識抽出アルゴリズムが証明中誰かによって実行されることはゼロ知識証明の場合には普通はなく、使わないものを用意するという点がなかなか理解し難いと感じました。