ゼロ知識証明
古い技術：ゼロ知識対話証明（とてもわかりやすいのでぜひご覧ください。）でも紹介されているように、「ゼロ知識証明」は1980年代に発表された技術です。
ユーザー認証を安全に行うという目的のもと開発された技術で、RSA暗号などと並んでユーザー認証、デジタル署名などに使いどころがあります。
今回はこの「ゼロ知識証明」についてまとめてみました。
この記事の流れ
- ゼロ知識証明とは
- ゼロ知識証明の歴史
- ゼロ知識証明プロトコルが備える3つの性質
- ゼロ知識証明を簡単な例で理解する
- ゼロ知識証明の応用例
- 非対話型ゼロ知識証明
- ゼロ知識証明に関連するニュース
となっています。
ゼロ知識証明とは
ウィキペディアからの引用をすると、
暗号学において、ゼロ知識証明（ぜろちしきしょうめい、zero-knowledge proof）とは、ある人が他の人に、自分の持っている（通常、数学的な）命題が真であることを伝えるのに、真であること以外の何の知識も伝えることなく証明できるようなやりとりの手法である。
であり、少し砕いていうと、
ある知識を持っていることを、その知識に関する何の情報も明らかにすることなく証明する手法のこと。
です。
この方法を用いると、例えば、パスワード自体は明かさずに、自分がパスワードを知っているという事実を証明することが可能です。
具体的に、以下のような時に使います。
- Webサービスにログインする時
パスワードを入力する代わりに、パスワードを知っているという証拠を送る。
-本人確認する時
第三者に母親の旧姓を送る代わりに、自分が確実に本人であることの証拠を送る。（デジタル署名）
-トランザクションの立証する時
パブリックブロックチェーン上で、自分の過去のトランザクションを明かすことなく自身のトランザクションが改ざんされていないことを証明する。（たとえば二重払いしていないなどの証明）（ZCash）
ゼロ知識証明の歴史
- 1982年に論文自体がGoldwasser, Micali and Rackoffにより完成される
- 1985年３回のリジェクトを経て上記の3人がSTOCで発表「The Knowledge Complexity of Interactive Proof-Systems」
- 2002年に誕生20周年を記念してGoldwasserがチュートリアル論文を発表「A Short Tutorial of Zero-Knowledge」
ゼロ知識証明プロトコルが備える3つの性質
ゼロ知識証明のプロトコルは、以下の3つの性質を満たす必要があります。
- 完全性（completeness）
- 健全性（soundness）
- ゼロ知識性（zero knowledge）
①完全性（completeness）とは？
証明者の主張が真であるならば、検証者はその主張の正しさを高確率で検証できます。証明者と検証者の双方がゼロ知識証明のプロトコルに従っている限り、検証者は証明者の主張が正しいことを確認できるのです。
②健全性（soundness）とは？
証明者の主張が偽であれば、証明者がどのように振る舞ったとしても、検証者はその主張が偽りであることを見抜けます。つまり、健全性を備えたプロトコルにおいては、証明者は検証者を騙せないのです。
③ゼロ知識性（zero knowledge）とは？
あらゆる場合において、検証者が証明者から何らかの知識（情報）を盗もうとしても、証明者の主張が真であること以上の知識は得られません。
ゼロ知識証明を簡単な例で理解する
洞窟の問題
有名なゼロ知識証明の例として、How to Explain Zero-Knowledge Protocols to Your Childrenで紹介された洞窟の問題の例がある。ここではそれを紹介する。
洞窟の比喩の問題設定
Pはお金を貰ってVに合言葉を教えたいが、Pが先に合言葉を教えるとVはお金を払わない可能性がある。逆に、Vが先にお金を払うとPが嘘をつく可能性がある(VはPから必ず真の合言葉を教えてもらいたい）。このリスクを取らないために、Pはまず自身が合言葉を本当に知っていることだけを証明したい。そうすることでお互いに上手く取引をしたい。
つまり、Pは合言葉を教えずにVに本当の合言葉を知っていることを示したい。
証明方法
- Pはどちらかの入り口から洞窟に入る（コミットメント)
- Vはどちらかの入り口をランダムに選び、そこから出てくるようにPに指示する。
- PはVに言われた方の出口から出てくる。
- これを繰り返す。
Pが本当は合言葉を知らない場合
PがVに言われた出口から出てこれる確率は、試行回数を$n$とすると$ (\frac{1}{2})^{n} $ となり、試行回数が大きくなると漸近的に0に近づきます。
よって、本当の合言葉知っていることを確率的に証明できますが、PはVに「合言葉を知っているかいないか」という1bitの情報しか与えていません。
Pが合言葉を知っている場合
試行回数$n$に関わらず、必ずVの要求通りに洞窟から出てくることができる。
ウォーリーをさがせ
で紹介されている、「ウォーリーを探せ」の例がとても面白かったので紹介します。ぜひご覧ください。
登場人物は、「アリス」と「ボブ」です。ここで、アリスはウォーリーを探せの絵本の中からウォーリーを探し当てました。アリスはボブに彼女がウォーリーを探すのに成功したという事実を証明したいと考えています。ただし、その際にボブにウォーリーの場所を教えたくはありません。
この時に使う証明を２つ紹介します。
証明１
アリスは絵から、ウォーリーだけを切り抜いて、ボブに見せます。念のため、アリスが単にウォーリーの絵を、新しくコピーしただけでないことを証明するには、絵全体の裏面に透かしを入れておきます。
証明２
アリスはオリジナルの絵全体に、カードボードを被せて、ウォーリーの箇所だけ切り抜きます。こうするとウォーリーだけが見えます。彼の位置情報はボブには一切開示していません。アリスはカードボードを、絵に被せるだけでいつでも、ウォーリーを見つけたことを証明できます。
健全性、完全性、そしてゼロ知識
どちらの証明方法も、ゼロ知識証明を構成する３つの要素を満たしています。
ここでは３つの要素がどのように満たされているか考えてみます。
アリスは毎回同じゲームを行ったとしても、同じ方法でウォーリーを見つけたことを証明できます。
1.健全性
証明できることは全て真でなければならない：アリスが、ウォーリーの場所を知らないとして、カードボードをランダムに切り抜いたとしましょう。カードボードの穴は、ウォーリー以外のランダムなイメージを表示するだけです。要するに、アリスの証明システムでは、ズルすることはできません。
2.完全性
真であるには証拠がなければならない：アリスは、ウォーリーを探すたびに、毎回ボブに同じ方法で証明することができる。アリスの証明システムで、ボブにウォーリーを見つけたことを毎回納得させられる。
3. ゼロ知識
証明されたという事実だけが表明される：アリスが、ボブにウォーリーを見つけことを証明するには、ボブに対して「アリスがウォーリーを見つけた」以外の情報は提示されない。ウォーリーの正確な位置情報は、提示されることはありません。アリスは、自身の情報を一切開示することなく、ウォーリーを見つけたことを証明できます。
ゼロ知識証明の応用例
ゼロ知識証明の応用例には、公開鍵暗号、デジタル署名、ユーザ認証などがある。その他、マルチパーティ計算への適用など多くの応用がある。例えば、個人情報を用いてユーザ認証を行う場合、ユーザはゼロ知識証明のプロトコルに従い、個人情報を入力する。健全性があるので、ユーザは真正な入力でないと正しさを証明できず、そしてゼロ知識性があるため、個人情報そのものは漏れることはないことになる。
ユーザ認証の例
ゼロ知識証明で証明される命題には、巨大な合成数の素因子（素因数分解の解）を知っている、離散対数問題（DLP）の解を知っているなどの公開鍵暗号でよく利用されるものがある。また、任意のNP完全問題の証拠を持っていることをゼロ知識証明で示せることが知られている。
ここでは
- RSA暗号のような巨大な合成数の素因子（素因数分解の解）
- 楕円暗号を応用し離散対数問題（DLP）の解
を使い、秘密鍵を持つユーザーAが、秘密鍵を見せることなく、持っているという事実をユーザーBに伝えることで、ユーザーBに認証をしてもらう。
というシナリオの例を考えてみます。
巨大な合成数の素因子（素因数分解の解）を使う
以下の参考文献を参照ください。
楕円暗号を応用し離散対数問題（DLP）の解を使う
例えば、楕円曲線の点PとAさんの秘密鍵a、公開鍵Q=aPがあったときに、Aさんが秘密鍵aを持っていることをBさんに示すことを考えます。もちろん、aをそのままBさんに教えれば、BさんはaPがQに等しいかどうかを確認することでaが本物であることを検証できます。しかし当然、Aさんは秘密鍵aを教えたくはありません。このようなときに、相手に何も知識を与えずに、ある命題を知っていることを証明するのがゼロ知識証明です。
楕円曲線の場合の非対話ゼロ知識証明を紹介しましょう。AさんとBさんは、PとQ=aPを共有している状態です。ハッシュ関数Hを用意します。
Aさんは乱数rを作って、R=rPとb=H(P,Q,R)を計算します。それからc=r+abを求めて、(R,c)をBさんに渡します。
Bさんは、b=H(P,Q,R)を計算します。そしてX=cPとY=R+bQを計算し、両者が等しいことを確認します。もしXとYが等しければ、Aさんが秘密鍵aを持っていると納得できます（受理）。そうでない場合は、Aさんはaを持っていないと判断します（棄却）。
完全性
これでうまくいくことを確認しましょう。まず、Aさんが本当にaを知っている場合、Y=rP+baP=(r+ab)P＝cPなので、X=Yが成り立ちます。このように、Aさんがある命題を本当に知っているときに受理するため、完全性を満たしています。
健全性
逆に、Aさんが実はaを知らないのに、X=YとなるようにRやcの値を決められるでしょうか。X=YならR=cP-bQとなります。これを成立させようとすると、b=H(P,Q,R)となるように、うまくcの値を決めなくてはいけません。Hはハッシュ関数ですから、これはとても難しそうです。このように、Aさんがある命題を知らないときに受理できないため、健全性を満たしています。
ゼロ知識性
最後に、(R,c)からaの情報が漏れていないことを確認します。第2回で触れたように、「楕円離散対数問題は困難」だとすると、R=rPから、rを知ることはできません。よって、c=r+abからaを求めることはできません。厳密な証明はここでは省略しますが、このように情報が漏れていないため、ゼロ知識性を満たしています。
非対話型ゼロ知識証明
これまでは対話型のゼロ知識証明について考えましたが、これには実装上の欠点があります。これはお気付きの通り、対話型では検証者が毎回毎回チャレンジを証明者に「ランダムに」与え、結果をチェックしなければならないからです。まず対話を繰り返すのに時間がかかるということと、誰か攻撃者が間に入った場合、セキュリティがとても低くなるという欠点があります。
それを踏まえ、「非対話型」ゼロ知識証明というものが存在します。
イメージするのは難しいですが、一言で言うと、先ほどの検証者が送る「ランダムなチャレンジ」を、ハッシュ関数で置き換えるものです。このハッシュ関数の引数には、証明者の情報と、証明者のコミットの情報が入ります（コミットとは証明者がとった行動、洞窟の例だと、まずAとBのどちらに入ったか、という情報）。そのハッシュ関数の結果を、先ほどの検証者が証明者に送るチャレンジとみなします。そうすることで、証明者は検証者からランダムなチャレンジをもらうことなく、自身でチャレンジを生成し、チャレンジ結果を検証者に送ることができるのです。そうすることで、検証者と証明者の間の通信が必要にならなくなるため、実装上とても楽になります。
この説明をもう少し深掘りしたい方は、
- 2018-06-16 Schnorrの非対話型ゼロ知識証明（NIZKP）について定義しているrfc8235を読んでみた
- What is a Non-Interactive Zero Knowledge Proof?)
をご覧ください。
マルチパーティ計算への適用
光成 滋生さんがレベル2準同型暗号の平文バイナリ制約を与えるコンパクトな非対話ゼロ知識証明の中で、準同型暗号を用いた秘密計算を使う際のゼロ知識証明について言及されていました。
とても面白いのでぜひ興味がある方はご覧ください。
ゼロ知識証明に関連するニュース
現在ゼロ知識証明を使用してプライバシー強化を実現したり、ブロックチェーンシステム内に組み込むことでブロクチェーンシステムの運用をより安全、高速に行う取り組みがなされています。
- デロイト 独自ブロックチェーンに「ゼロ知識証明」を追加
コンサル「ビッグ4」の一角であるデロイトは、独自の企業用ブロックチェーンソリューション「EduScrypt」にZKP(ゼロ知識証明)を利用したプライバシー強化技術を追加した。EduScryptは、組織がスタッフの資格を追跡、共有、検証するのに役立つソリューションである。
この機能追加において、デロイトはイスラエルのスタートアップQEDITと提携したという。QEDITはゼロ知識証明（ZKP）による暗号化を活用し、企業の共有された台帳内でビジネスデータが安全に制御できるようなノウハウを提供している。
- オランダの金融大手ING、ゼロ知識証明使った新たなブロックチェーンを発表
- EYが第三世代ゼロ知識証明技術をパブリックドメインにリリース
参考文献
- 匿名通貨Zcash(ZEC)の「ゼロ知識証明」について解説してみる
- How to Explain Zero Knowledge protocol to your children
- 暗号応用技術
- いま知っておきたい「ゼロ知識証明」の基本と関連プロジェクト
- ゼロ知識証明 - 基礎から発展的内容まで(1)
- What is a Non-Interactive Zero Knowledge Proof?)
- まだまだ広く深い、暗号の世界――匿名認証や電子投票に利用される「ブラインド署名」「グループ署名」「ゼロ知識証明」
- レベル2準同型暗号の平文バイナリ制約を与えるコンパクトな非対話ゼロ知識証明
- デロイト 独自ブロックチェーンに「ゼロ知識証明」を追加
- https://jp.cointelegraph.com/news/ing-bank-releases-blockchain-privacy-tool-bulletproofs
- EYが第三世代ゼロ知識証明技術をパブリックドメインにリリース、Libra協会がロードマップ2を発表、SBIが中国平安グループと合弁会社を設立などのブロックチェーン・仮想通貨ニュース解説
- イメージで理解できる-ゼロ知識証明
- Understanding Zero-knowledge proofs through illustrated examples
- ゼロ知識証明 wiki
- 「ゼロ知識証明とzk-SNARKs」を初心者にもわかりやすく解説！
- 古い技術：ゼロ知識対話証明
- サイボウズラボ 光成 滋生さんのスライド「ElGamal型暗号文に対する任意関数演算・再暗号化の二者間秘密計算プロトコルとその応用」
- 2018-06-16 Schnorrの非対話型ゼロ知識証明（NIZKP）について定義しているrfc8235を読んでみた