クリーム色の背景、色付き表示、高コントラスト、大きな文字のほうが読みやすいですか?配色と文字を選ぶと、すべてのページに一度で反映されます。

無料レッスン

Fiat-Shamir: 誰でも確かめられる証明

このレッスンのあとで: Fiat-Shamir のチャレンジを計算し、非対話型の証明を検証できる。

60分のレッスンコマンド2件ゼロ知識証明ラボ:コミットメント、Schnorr、Fiat-Shamir、Merkle の証明を Python で

やり取りなしで成り立つ証明

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 の証明は、そのメッセージへの署名です。

例: 対話型と非対話型

対話型の SchnorrFiat-Shamir の Schnorr
c を選ぶもの検証者がランダムにy、t、メッセージのハッシュ
メッセージ3つ、行ったり来たり1つ、t と s をまとめて
確かめられる人c を選んだ検証者だけ誰でも、いつでも
納得させる相手1人の検証者確かめるすべての人

学生が入力するセルは、このプレビューでは空白です。

試そう: 弱いハッシュで偽造する

コード: python
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

ここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。

このラボとソースについて: ゼロ知識証明ラボ:コミットメント、Schnorr、Fiat-Shamir、Merkle の証明を Python で

授業で使いますか?このモジュールを学生に割り当てると、教員用ガイド、自動採点つきの課題、学生ごとのラボを使えます。