ゼロ知識証明

public.icon

暗号学において、ゼロ知識証明（ぜろちしきしょうめい、zero-knowledge proof）とは、ある人が他の人に、自分の持っている（通常、数学的な）命題が真であることを伝えるのに、真であること以外の何の知識も伝えることなく証明できるようなやりとりの手法である。

実際に実現された方式では証明者と質問者が複数回のやりとりをするのでゼロ知識対話証明（ZKIP:Zero-Knowledge Interactive Proof)とも呼ばれます。

以下の前提が整っていないと、そもそもゼロ知識証明をすることができない

作問者には正解がわかる

正解を知っていれば証明も容易

力任せに解くのは計算量が爆発するため事実上不可能

そういう問題の中で

別の形の問題への変形が容易で、正解を知っていれば変形した問題の正解もわかる

変形した問題と元の問題を見比べても変形規則は容易にはわからない

変形した問題の正解がわかっても変形規則を知らないことには元の問題の正解はわからない

むずすぎる

NP証明系は検証手順を 「証明者からもらった証拠で問題が正しいか検証する」という決定的なアルゴリズムに限っている。これを確率的なアルゴリズムに拡張することで高い表現力が得られると思われる（ここで「思われる」とあるのはNPがIPの真部分集合か明らかではないから）。

NPを自然に確率的なアルゴリズムに拡張したものをIP(対話証明)という。

https://gyazo.com/cead0906e2fdec46594bf86880c6878b

https://gyazo.com/a6afec08c71e1a0780a06b0d835c7e1a

この記事には書いていないけど、Ethereumのトランザクションを処理しきれない問題に対して（プライバシーではなく）"スケーリングのために"利用されている例もある

https://gyazo.com/dfa63ec68915eec09a7ad1c0c7e901ab

https://gyazo.com/5a3f8fb824a0063a6d2d542812d66fbe

参考文献の量すごい