🐣

ゼロ知識証明はいいぞ

2020/10/30に公開

math

この記事では、暗号技術の一つであるゼロ知識証明と、その応用について簡単に解説します！

ゼロ知識証明

ゼロ知識証明というのは

「秘密を所持している」という証明者の主張が正しいこと以外の情報が、検証者に漏れない

ようなプロトコルのことです。ゼロ知識証明で知識を証明したい人を証明者（Prover）、証明を検証する人を検証者(Verifier)といいます。

秘密を漏らさない（ゼロ知識）
所持していることを伝える（証明）

のような特徴から、ゼロ知識証明と呼ばれます。例えば本人確認のためにパスワード使う場合は、パスワードが相手が伝わってしまうと危険そうです。ここで、ゼロ知識証明を使えば、パスワードそのものの情報を漏らさずに本人確認が出来ます。

証明者の主張は「秘密を所持している」と書きましたが、実はこれは厳密ではありません。ゼロ知識証明で証明できる主張には、種類が存在します。例えば

言語への所属
知識の所持
能力の所持

です。言語への所属の証明というのは、例えば「ある数 $x$ が素数であること」の証明です。言語とは「ある特徴を持った集合」のことで、ここでは「素数の全部の集合に $x$ が含まれている」ことの証明になります。今回は主に言語の所属ではなく、知識の所持について説明します。

もっとゼロ知識証明の定義について詳しく知りたい方は、有田先生のゼロ知識証明入門がとても参考になります！

知識とは何か

ゼロ知識証明の「ゼロ知識」の表す「知識」とは何でしょうか？ゼロ知識証明の文脈において、証明者の持つ知識とは

「証明者が現実的な時間で計算できるもの」

を表します。現実的な時間は多項式時間で計算できるとも言い換えられます。現実的な時間で計算が出来なければ、それは知識とは言えないということになります。「現実的な時間で暗号を破ることができないこと」を安全性の根拠にしている現代暗号学的には自然な定義と言えます。なぜ暗号が破れないのかはここで解説してます。

ここで、具体的に数式を使ってどうやってゼロ知識が実現されるのか解説します。まず、離散対数仮定というものを導入します。

y=g^s

$y$ と $g$ が与えられた時、 $s$ を計算することは現実的な時間では、不可能であるという仮定です（正確に言えば法 $p$ も与えられる）。この仮定が成立するとして、証明者が持っている秘密情報 $s$ をゼロ知識証明するプロトコルを考えます。次のようになります。

プロトコルは以下のように展開します。

証明者はコミット $x$ を送る。
検証者はチャレンジ $e$ を送る。
証明者はレスポンス $z$ を送る。
検証者は等式 $g^z=xh^e$ が成立するなら受理、しなければ拒否する。

このプロトコルの数式は簡略化しており、厳密に言えば安全ではありません。厳密な定義は、上で紹介したゼロ知識証明入門に書いてあります。プロトコルの最後の等式は

xh^e=g^r (g^s)^e=g^r g^{se}=g^{r+se}

より成立します。これにより、 $s$ を証明者が持っていることを検証者は確認できます。ここで秘密情報 $s$ を検証者が持っている情報である $x,e,z$ と公開鍵の $h,g$ から計算できるか考えてみます。

\begin{aligned} x&=g^r\\ z&=r+se\\ h&=g^s \end{aligned}

離散対数仮定により、 $h=g^s$ と $h,g$ から $s$ を計算できないので秘密は漏れていません。同様に $x=g^r$ と $h,g$ から $r$ を計算することができないので、 $r+se$ はただの乱数になります。よって、
検証者は $s$ を計算することができませんのでこれはゼロ知識です。

結局、検証者からすれば、通信で得られた情報はただの乱数でしかないのです。

知識のゼロ知識証明

ここは専門的な話になります。「知識の所持」を証明するゼロ知識証明のことを、正確には知識の証明(proof of knowledge) といいます。ここでは知識の証明に関する正確な定義はしません。

この知識の証明の一種に、Σプロトコルというものが存在します。これは、特定の目的によく使われているプロトコルです。（後で目的については説明します。）

Σプロトコルは、簡単に言えば「3moveかつ検証者が正直なゼロ知識証明」です。3moveというのは

証明者はコミットを検証者に送る。
検証者はチャレンジを証明者に送る。
証明者はレスポンスを検証者に送る。

のような３回通信することです。Σプロトコルという名前の由来もこの３回通信から来ているようです。確かに下の図を見るとΣって形に見えなくもないかも？

正直というのは英語だとhonestといいますが、意味はゼロ知識証明のプロトコルに従うということです。検証者はプロトコルに従ってチャレンジを送ります。悪意を持って証明を妨害するような検証者に対して、Σプロトコルはゼロ知識ではありません。

ゼロ知識証明の応用

ここまでゼロ知識証明の話をしましたが、概念的な話であまり身近に感じられなかったかもしれません。しかし、ゼロ知識証明を応用されたものが実際に利用されています。それは認証と電子署名です。

認証

認証はゼロ知識証明の応用の一つでΣプロトコルです。Σプロトコルは正直な検証者を仮定していましたが、認証というユースケースを考えると自然ですね。Σプロトコルが知識の証明であったように、認証プロトコルも知識の証明です。

Bさん（検証者）がAさん（証明者）の本人確認をしたいとしましょう。AさんはAさんしか持っていない秘密情報 $s$ を使って、Bさんに本人であることを伝えます。認証プロトコルは秘密情報を使ってAさんであることを確認できるプロトコルですが言い換えると

「Aさんは秘密情報sを持っている」という知識の所持に対するゼロ知識証明（知識の証明）

になります。秘密情報 $s$ を持っているのはAさんだけですので、証明ができるのはAさんだけです。証明ができたという事実は、そのまま本人確認に繋がります。

電子署名

ここで歴史の話を少し挟みます。フィアットとシャミアという人は特定条件下でゼロ知識証明^[1]を非対話ゼロ知識証明に変換する手法を考案しました。これをフィアットシャミア変換とかフィアットシャミアヒューリスティックと呼びます。この変換は、簡単にいえば検証者が送ってくるチャレンジを証明者のハッシュ関数に置き換えてしまうのです。

すると、証明者が一方的に送りつけるだけでゼロ知識証明できます。これは非対話ゼロ知識証明（NIZK） と呼ばれます。
これを認証に使うとどうなるでしょうか？非対話で本人確認ができるので、電子署名として活用できます。

電子署名は、秘密情報 $s$ で署名することで確かに本人が作成した文書であること（かつ改ざんがないこと）を保証するプロトコルでした。これは言い換えると

「署名した人が秘密情報 $s$ を所持している」という知識の所持に対する非対話ゼロ知識証明（知識の証明）

になります。署名は秘密情報を知らなければ作ることが出来ません。つまりAさんが署名していれば、

「Aさんが秘密情報 $s$ を持っていたこと」をゼロ知識証明する

ことになりますね。

これ以外には公開鍵に応用されていたりします。^[2]

まとめ

ゼロ知識証明とその応用について解説しました。詳しい数式や性質については述べませんでしたが、ゼロ知識証明のモチベーションだけでも伝わっていれば嬉しいです！

ゼロ知識証明と関係の深い対話証明については以下で解説しています。

脚注

例えば、Σプロトコルは理想的なハッシュ関数が存在する仮定のもと条件を満たしています。正直な検証者でなければチャレンジを送ってくるとは限らないので置き換えられません。 ↩︎
IND-CCA1とかIND-CCA2安全な公開鍵暗号の実現に利用されます。 ↩︎