やり取りなしで成り立つ証明
Fiat-Shamir 変換は、対話型の証明を非対話型に変えます。証明者は証明を1人で作り、あとで誰でも確かめられます。検証者の役は、ハッシュが受け持ちます。
Schnorr が署名になるのも、多くのゼロ知識証明が公開されて確かめられるのも、この方法によります。
このレッスンのゴール
メモ
Fiat-Shamir のチャレンジを計算し、非対話型の証明を検証できる。
キーワード
| ことば | いみ |
|---|---|
| 対話型 | メッセージを何度もやり取りする必要があること |
| 非対話型 | 誰でも確かめられる、1つのメッセージで済むこと |
| Fiat-Shamir | チャレンジをハッシュに置き換えること |
| 記録 | 証明の間に送られたもの全部 |
| 偽造 | 秘密なしで確認に通る証明 |
学生が入力するセルは、このプレビューでは空白です。
ハッシュがチャレンジを選べる
対話型の Schnorr には、その場にいる検証者が要ります。あとで大勢が確かめる証明には不便です。
Fiat-Shamir は、c を公開鍵、t、メッセージのハッシュとし、Q で割った余りにします。c は t で決まり、ハッシュは思いどおりに動かせないので、証明者は c を選べません。だから証明者は、やはり先に t を決めなければなりません。同じ c は、誰でも計算し直せます。
非対話型の証明を作って確かめる
docker exec jupyter python3 steps/fiatshamir.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
ラボの表示を読む
proof は証明、challenge はチャレンジ、checks out は確認に通るという意味です。
証明は2つの数、t = 718 と s = 501 です。ハッシュから求めたチャレンジは14でした。証明は True で確認に通ります。同じ2つの数でもメッセージが違うと False です。メッセージがハッシュの中にあり、チャレンジが変わるからです。メッセージに結びついた Schnorr の証明は、そのメッセージへの署名です。
例: 対話型と非対話型
| 対話型の Schnorr | Fiat-Shamir の Schnorr | |
|---|---|---|
| c を選ぶもの | 検証者がランダムに | y、t、メッセージのハッシュ |
| メッセージ | 3つ、行ったり来たり | 1つ、t と s をまとめて |
| 確かめられる人 | c を選んだ検証者だけ | 誰でも、いつでも |
| 納得させる相手 | 1人の検証者 | 確かめるすべての人 |
学生が入力するセルは、このプレビューでは空白です。
試そう: 弱いハッシュで偽造する
import hashlib
P = 1019
Q = 509
G = 4
y = 227 # ある人の公開鍵。その人の秘密は知りません
def weak_challenge(message):
# わざと間違えています: t をハッシュに入れていません。
return int(hashlib.sha256(message.encode()).hexdigest(), 16) % Q
message = "パットはキムに500円を借りている"
c = weak_challenge(message)
s = 123
t = pow(G, s, P) * pow(pow(y, c, P), -1, P) % P
print("c =", c, "偽造した t =", t, "s =", s)
print("確認に通る:", pow(G, s, P) == t * pow(y, c, P) % P)
# 直すには、str(t) + message をハッシュし、c が分かる前に t を決めさせます。
検証者が見るものはすべてハッシュする
上のコードは、t をハッシュに入れていません。だから偽造する人は先に c を求め、好きな s を選び、それに合う t を作れました。シミュレーターと同じやり方です。秘密がまったくなくても、確認は通りました。
決まりは、検証者が選ぶ前に見たはずの値をすべてハッシュすることです。群、公開鍵、t、メッセージです。実際のシステムがこの間違いのまま出荷されたこともあるので、目で確かめる価値があります。
よくある間違い
注意
「どんなハッシュでも Fiat-Shamir は安全だ」と考える人がいます。安全なのは、ハッシュが t と主張を含むときだけです。t を入れ忘れると、偽造する人は先にチャレンジを決め、シミュレーターと同じように証明をにせて作ります。
zk.py の関数を一覧にする
docker exec jupyter grep -n def zk.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。