秘密を言わずに、知っていると示す
ゼロ知識証明は、秘密そのものを見せずに、その秘密を知っていると相手に納得させる方法です。パスワードを送らずにログインしたり、個人のデータについての事実を示したりするのに使います。
今日は、この考え方を表すゲームで遊び、なぜうまくいくのかを数で確かめます。
このレッスンのゴール
メモ
対話型の証明を使って、完全性、健全性、ゼロ知識性を説明できる。
キーワード
| ことば | いみ |
|---|---|
| 証明者 | 秘密を知っていると主張する人 |
| 検証者 | その主張を確かめる人 |
| チャレンジ | 検証者がランダムに選ぶ問い |
| 完全性 | 正直な証明者は必ず通ること |
| 健全性 | ごまかす証明者はほぼ必ず失敗すること |
| ゼロ知識性 | 主張が正しいこと以外、検証者は何も知らないこと |
学生が入力するセルは、このプレビューでは空白です。
洞窟のゲームは対話型の証明
洞窟には A と B の2本の道があり、奥で鍵のかかった扉がつないでいます。証明者は、扉の合言葉を知っていると言います。
検証者が外で待つ間に、証明者はどちらかの道から入ります。検証者は A か B をランダムに叫び、証明者はその道から出てきます。合言葉を知っていれば必ず出られます。知らなければ、当てずっぽうが合ったときだけで、2回に1回です。
洞窟のゲームを何度も遊ぶ
docker exec jupyter python3 steps/cave.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
ラボの表示を読む
表示は英語です。passed は通った、cheaters はごまかす人、rounds はラウンドの意味です。
合言葉を知る証明者は、20回中20回通りました。これが完全性です。次に1000人のごまかす人が遊びました。1回目のあと残ったのは493人、2回目のあとは243人、10回目のあとは0人です。1回ごとに、ほぼ半分に減ります。20回なら、ごまかして通れるのは1048576回に1回です。これが健全性です。
例: ごまかして通る確率
| ラウンド数 | すべて通る確率 | 小数 |
|---|---|---|
| 1 | 2回に1回 | 0.5 |
| 2 | 4回に1回 | 0.25 |
| 3 | 8回に1回 | 0.125 |
| 10 | 1024回に1回 | 約0.001 |
| 20 | 1048576回に1回 | 約0.000001 |
学生が入力するセルは、このプレビューでは空白です。
試そう: 洞窟でごまかす人
import random
rng = random.Random(3)
def one_round(knows_password):
went_in = rng.choice("AB")
asked_for = rng.choice("AB")
if knows_password:
return True
return went_in == asked_for
passed = 0
for n in range(10):
if one_round(False):
passed = passed + 1
else:
print("捕まったラウンド:", n + 1)
break
print("通ったラウンド数:", passed)
# False を True に変えて、合言葉を知る証明者にし、もう一度実行しましょう。
検証者が何も知らない理由
外から見ると、証明者は言われた道から出てくるだけです。合言葉は一度も聞こえません。
さらに、ゲームを撮った動画は、第三者には何の証明にもなりません。2人が道を前もって決めておき、動画を編集できたからです。にせの記録が本物とまったく同じに見えるなら、本物の記録も何も漏らしていません。これがゼロ知識性の考え方です。
よくある間違い
注意
「ゼロ知識とは、検証者が何ひとつ知らないことだ」と考える人がいます。検証者は1つだけ知ります。主張が正しいということです。知らないのは秘密そのものと、秘密を見つける手がかりです。
ラボのスクリプトを一覧にする
docker exec jupyter ls stepsここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。