Advanced Cryptography Program 2026 / Week 3 自習ノート
Week 3 は、有限体の逆元から始めて楕円曲線の群を作り、その上に
シグマプロトコルと Fiat–Shamir 変換を積んで
Schnorr 署名まで一気に登ります。課題 schnorr-from-scratch は、
その全段を自分で書く構成でした。
このノートの山場は 2 つの実測です。秘密鍵を一度も使わずに作った会話が検証に通ること。 そして nonce を 1 回使い回しただけで、本物の secp256k1 の秘密鍵が復元できること。 この 2 つが、ゼロ知識と知識健全性の正体です。
出発点
Week 3 の週 README が言うテーマは楕円曲線と Schnorrで、課題も
schnorr-from-scratch です。ところが配られた講義スライドの表題は
「zkSNARK part 1」で、中身は有限体・多項式・commitment・arithmetization。
一見すると別の話に見えます。
別の話ではありません。同じ 1 枚の絵の、違う場所を指しているだけです。 スライドは zkSNARK 全体のパイプラインを見せ、課題はそのうち 「楕円曲線とコミット」の柱を、実際に手で組ませています。
だからこのノートも 2 段構えにします。前半は課題の道（有限体 → 楕円曲線 → Schnorr）を、実際に壊した採点結果つきで登ります。後半はスライドの道 （多項式 → commitment → arithmetization）を地図として置きます。 後半は Week 4 以降で手を動かす場所です。
前提について
今週から、土台の数学がそのまま実装に出てきます。
mod 演算・群・体・逆元・離散対数に不安があれば、先に 土台編（有限体と楕円曲線） を読んでください。Week 1 の回路も Week 2 のシェアも、この土台の上に乗っています。
特に今週は 「割り算＝逆元の掛け算」が楕円曲線の傾きの計算で、 「0 に逆元はない」が垂直な接線の場合分けで、それぞれ実装として現れます。
この頁の地図
全体像
スライドが最初に出す 1 枚がこれです。左から右へ、証明したい計算がだんだん形を変えていきます。
下段は、上段を支える道具。色が付いているのが今週やる場所です （有限体と楕円曲線、そして一番右の「短い証明」を対話から作る部分）。 多項式とフーリエ変換は Week 4 以降の担当になります。
証明したいのは「ある秘密を知っている」という主張です。スライドの例で言えば、
公開値 y = 15 に対して w³ + w + 5 = y を満たす
秘密の w を知っている、という主張（答えは w = 2）。
statement（公開）: ∃w. w³ + w + 5 = 15
witness（秘密）: w = 2
この「条件」の部分を、公開入力 y と秘密候補 w を受け取って
合否を返す関係 R(y, w) と書くと、zkSNARK が扱うのは
「R(y, w) = 1 となる w が存在する」という形の主張だけになります。
Week 1 の回路は、まさにこの R を書く言語でした。
zkSNARK の頭文字は、そのまま性質の一覧
zk（Zero-Knowledge）: proof から witness 由来の情報が漏れない。
S（Succinct）: proof が短く、検証が速い。
N（Non-interactive）: 1 通で完結する。何往復もしない。
ARK（ARgument of Knowledge）: 有効な proof を作れる prover は、対応する witness を 本当に知っている（知識健全性）。正しい witness を持つ prover の proof は必ず通る（完全性）。
今週の Schnorr は、この 4 つを最小構成で全部持っている「いちばん小さい実例」です。
積み上げ 1 段目
課題は Part 1 から Part 3 まで一本につながっていて、 下の Part が間違っていると上の Part は動きません。 その一番下が、逆元です。
有限体で割り算をするとは、逆元を掛けることでした。
a⁻¹ は a·a⁻¹ ≡ 1 (mod p) を満たす値です。
求め方は拡張ユークリッドの互除法。ax + bp = 1 を
満たす整数 x, b を見つける操作で、両辺を mod p で見ると
bp ≡ 0 なので ax ≡ 1。つまり x が a の逆元です。
F₁₃ で 5⁻¹ を求める
13 = 2·5 + 3 5 = 1·3 + 2 3 = 1·2 + 1
↓ 1 まで下りたら、逆に書き戻す
1 = 3 − 1·2 = 2·13 − 5·5
mod 13 で見ると −5·5 ≡ 1、よって 5⁻¹ = −5 = 8
検算: 5·8 = 40 = 39 + 1 ≡ 1 (mod 13) ✓
実測 — 正規化を忘れると、ここで止まる
拡張ユークリッドが返す x は、負の数のことがあります。
上の例でも、素直に出てくるのは 8 ではなく −5 でした。
そのまま返す実装を採点器に通すと、こうなります。
FAIL: test_inv_small (a=10, p=17) FAIL: test_inv_small (a=2, p=1009) FAIL: test_inv_small (a=966, p=1009) AssertionError: False is not true : 逆元は 0..p-1 に正規化して返してください
値としては正しいのに、表現がそろっていないと落ちる。
Week 2 の share でもまったく同じ理由で落ちました
（[70, -2, -71] vs 正解 [3, 65, 63]）。
「体の元は 0..p−1 の代表で持つ」は、週をまたいで効いてくる約束事です。
0 だけは逆元を持たない — これが後で効く
0 に何を掛けても 1 にはならないので、0 の逆元は存在しません。課題では
field_inv(0, p) で ValueError を投げることが要求されます。
この「0 で割れない」が、楕円曲線の場合分けにそのまま姿を変えて現れます。
2 倍算の傾きは λ = (3x² + a) / 2y。y = 0 の点では分母が 0 になり、
傾きが計算できません。幾何的には接線が垂直になる場所で、そのときの
2P は無限遠点 O と定めます。
「割れないから例外」ではなく、「割れない場所には別の答えがある」という形になっています。
積み上げ 2 段目
有限体は「+ と ×」の世界でした。その上に、まったく別の演算を持つ群をもう 1 つ作ります。
曲線 y² = x³ + ax + b は 3 次式なので、直線と最大 3 点で交わります。
そこで 2 点 P, Q を通る直線が曲線と交わる 3 点目を R′ とし、その x 軸反転を
P + Q と定めます。
なぜ反転するのか: 素直に「3 点目」を和にすると、単位元と逆元がうまく定義できません。 反転を入れると、一直線上の 3 点の和が O（無限遠点）という美しい規則になり、 O が単位元、x 軸対称の点どうしが逆元、という群の形が完成します。
直線の傾き λ を求め、交点の座標を解くと、次の式になります。
弦（P ≠ Q）: λ = (y_Q − y_P) / (x_Q − x_P)
接線（P = Q）: λ = (3x_P² + a) / (2y_P)
x_R = λ² − x_P − x_Q
y_R = λ(x_P − x_R) − y_P
「/」は全部、前段の field_inv です。実数の幾何の絵はあくまで直感で、 計算は最初から最後まで F_p の中で行います。 絵に描ける曲線と、実際に計算している集合は別物だと割り切るのが早道でした。
曲線 y² = x³ + x + 6 over F₁₁、点 P = (2, 7) の 2 倍。
λ = (3·2² + 1) / (2·7) = 13 / 14 ≡ 2 / 3 (mod 11)
3⁻¹ = 4（3·4 = 12 ≡ 1）なので λ = 2·4 = 8
x_R = 8² − 2 − 2 = 60 ≡ 5 （60 = 55 + 5）
y_R = 8·(2 − 5) − 7 = −31 ≡ 2 （−31 + 33 = 2）
2P = (5, 2) 検算: 2² = 4、5³ + 5 + 6 = 136 ≡ 4 (mod 11) ✓
検算の癖をつけると、デバッグが一瞬で終わります。
課題には is_on_curve が用意されていて、
計算結果が曲線に乗っていなければ、公式のどこかが間違っていると即座に分かります。
y_R = λ(x_P − x_R) − y_P の引き算の向きを逆にした実装を、
採点器に通した結果です。
FAIL: test_doubling AssertionError: 2G = (818, 622) が曲線上にありません。 y_R = lam * (x_P - x_R) - y_P の符号や mod の取り忘れを確認してください FAIL: test_scalar_mul_is_homomorphic (k1=3, k2=5) AssertionError: Tuples differ: (951, 492) != (755, 55)
正解は (818, 800)。x 座標は合っていて、y だけがずれます
（800 + 622 = 1422、1009 を引くと 413…と、
単純な符号反転にもなっていない）。
「曲線上にあるか」というたった 1 つの検査が、この種のミスを全部捕まえます。
準同型性 (k₁+k₂)G = k₁G + k₂G のテストも同時に落ちるのは、
群の構造そのものが壊れているからです。
kP を定義どおり k 回足すと、k に比例した時間がかかります。
k を 2 進展開して、倍にしながら必要なビットのところだけ足すと
log₂k に比例します。
13P（13 = 1101₂）: P →2P →4P →8P と 3 回倍にして、8P + 4P + P で 2 回足す = 5 回
定義どおりなら 12 回
実測（secp256k1、この課題の実装）:
k = 13 ec_add 6 回 / 0.2 ms k = 123 ec_add 12 回 / 0.4 ms k ≈ 2^64 ec_add 100 回 / 3.1 ms k ≈ 2^256 ec_add 446 回 / 12.9 ms 素朴な加算の実測速度: 約 1,231,505 回/秒 → nG（n ≈ 2^256）を素朴に足すと 約 3.0×10^63 年 double-and-add なら 512 回未満で終わる
課題のテストには nG = O（n は位数、約 2²⁵⁶）を確かめるケースがあるので、
素朴な実装だとテストが永遠に返ってきません。
「落ちる」のではなく「終わらない」という失敗の仕方をするのが、この間違いの特徴です。
土台の要
double-and-add のおかげで x から xP は一瞬で計算できます。
では逆に、P と xP から x を求めるには?
効率の良い方法が知られていません。これが楕円曲線上の離散対数問題で、 暗号の一方向性はここから来ています。
見方はハッシュとまったく同じです。m → Hash(m) は速く、
Hash(m) → m は難しい。楕円曲線では、入力がスカラー x、
出力が点 xP という構造でこれを作ります。
資料では乗法記法（g, gˣ）と加法記法（P, xP）が混ざりますが、
同じことの書き方違いです。スライドの Schnorr は乗法記法、
課題の実装は楕円曲線なので加法記法でした。
| 問題 | 乗法記法 | 加法記法 |
|---|---|---|
| 離散対数 | g, gᵃ から a | P, aP から a |
| 計算 Diffie–Hellman | gᵃ, gᵇ から gᵃᵇ | aP, bP から abP |
| 判定 Diffie–Hellman | T = gᵃᵇ か判定 | T = abP か判定 |
なぜ「難しさ」に頼れるのか
小さい群なら総当たりで解けます。位数 967 の曲線なら、最悪 967 回試せば当たります。 実用の曲線 secp256k1 は位数が約 2²⁵⁶ で、 総当たりの手数が宇宙の年齢を桁で超えるから安全とみなせる、という話です。
「解けない」ではなく「割に合わない」。暗号の安全性は、たいていこの形をしています。
積み上げ 3 段目
公開鍵 P = xG について「x を知っている」ことを、x を見せずに納得させます。
証明者 検証者
r をランダムに選ぶ
R = rG ── R ──▶
◀── e ── e をランダムに選ぶ
s = r + e·x ── s ──▶ sG = R + eP を確認
完全性は 1 行で確かめられます。
sG = (r + e·x)G = rG + e·(xG) = R + eP。
正直に計算した s なら、検証式は必ず成り立ちます。
検証者が受け取る s = r + e·x には秘密 x が入っていますが、
ランダムな r が足されているので、s 単体からは何も分かりません。
Week 2 とまったく同じ構図です。Beaver 乗算で公開した
d = x − a が安全だったのは、a が誰も知らない乱数だったから。
ここでも r がワンタイムパッドの役をしています。
そして Week 2 と同じく、使い回した瞬間に壊れます（後述）。
座標の計算は mod p、スカラー（指数）の計算は mod n（G の位数）。
1 つのコードに 2 つの法が同居します。
s = r + e·x の mod を p にした実装の採点結果です。
FAIL: test_honest_transcript_accepts (r=456, e=77) FAIL: test_honest_transcript_accepts (r=966, e=966) FAIL: test_honest_transcript_accepts (r=500, e=123) FAIL: test_nonce_reuse_leaks_secret AssertionError: 786 != 123
面白いのは、4 つのうち (r=1, e=0) のケースだけが通ることです。
e = 0 なら s = r = 1 で、どちらの法で丸めても 1 のまま。
法を間違えていても、値が法より小さければ表面化しません。
そして最後の 1 行——nonce 再利用の「攻撃」までもが失敗しています。
攻撃の式 x = (s₁−s₂)(e₁−e₂)⁻¹ も mod n の世界の話なので、
土台がずれると攻撃側も成立しなくなる。
正しい代数の上でしか、正しい壊し方もできない。
ラボ 1
課題と同じトイ曲線（y² = x³ + 11 over F₁₀₀₉、位数 967、G = (1, 298)）で
3 手を実際に走らせます。モードを切り替えると、秘密鍵を使わずに同じ形の会話を作ります。
どちらも検証に通ることを確かめてください。
—
—
やりとりと検証の中身
—
3 つの性質
ラボで見たとおり、秘密を知らなくても受理される会話は作れます。 では何が「知っている」の証明になっているのか。3 つの性質を分けて考えます。
完全性 — completeness
正しい witness を持つ証明者は、必ず受理される。
sG = R + eP が代数的に恒等式になることで保証されます。
これが崩れると、正直な人が弾かれる（使いものにならない）。
知識健全性 — knowledge soundness
受理される proof を作れる者は、本当に witness を知っている。
証明の道具が抽出器（extractor）です。 証明者を巻き戻して同じ R のまま別のチャレンジ e′ を投げ、 2 つの応答 c, c′ を得られたなら、そこから x を計算して取り出せる—— 取り出せた以上、x は最初から証明者の中にあった、という論法です。
ゼロ知識 — zero-knowledge
記録を見ても、公開情報から説明できる範囲しか分からない。
道具は simulator。秘密を持たない simulator が、本物と見分けのつかない 会話を作れるなら、その会話に秘密由来の情報は入っていない、と言えます。 ラボの simulator モードがまさにこれです。
実測 — simulator の会話は本当に受理される
秘密 x を一度も使わず、順番を逆にして作った会話です
（先に e, s をランダムに選び、R := sG − eP と逆算する）。
x を使わずに作った会話: (R, e, s) = ((146, 214), 190, 284) 検証者はこれを受理するか: True
つまり「受理された会話が 1 本ある」ことは、何の証明にもなっていません。 本物と偽物の違いは中身ではなく順番だけ—— 本物は R を先に出し、そのあとでチャレンジを受け取る。 simulator はチャレンジを知ってから R を作る。
「証明者が先にコミットする」という順番が、健全性の全部を担いでいます。
抽出器と攻撃は、同じ 1 本の式
同じ r（同じ R）で 2 つのチャレンジに答えると:
s₁ = r + e₁·x s₂ = r + e₂·x
s₁ − s₂ = (e₁ − e₂)·x ← r が消える
x = (s₁ − s₂)·(e₁ − e₂)⁻¹ (mod n)
これが抽出器の中身であり、そのまま nonce 再利用攻撃の中身でもあります。
ラボ 2
攻撃者が持っているのは公開鍵と 2 本の署名だけという設定です。 r を共通にしたまま 2 つのチャレンジを選んで、秘密鍵が復元される瞬間を見てください。
秘密鍵 x = 123 は攻撃者に見えていません。使うのは R, e, s の公開値だけです。
—
攻撃者の計算
—
実測 — 本物の secp256k1 でも同じことが起きる
トイ曲線だからではありません。課題の実装で、Bitcoin と同じ曲線・256 ビットの秘密鍵に対して 同じ攻撃を走らせた結果です。
署名1: R.x = 0xb44cf0c87f8f960c... s1 = 0x28807ada8ee210bd...
署名2: R.x = 0xb44cf0c87f8f960c... s2 = 0x24da65e7523016c0...
R が一致している: True ← 公開情報だけで再利用が見抜ける
復元した x = 0x1b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b
本物の x = 0x1b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b
一致: True
署名を 2 本公開しただけで、秘密鍵が完全に失われます。
実際に、PlayStation 3 の ECDSA 署名鍵や、初期の Bitcoin ウォレットの一部が、 この形（乱数生成の不備で nonce が重複）で鍵を失っています。 「乱数を毎回変える」は運用上の注意ではなく、安全性の前提そのものです。
仕上げ
ここまでは対話でした。最後の 1 手で、対話を消して署名にします。
検証者の仕事はランダムなチャレンジ e を選ぶことだけでした。 ならば、ここまでの会話のハッシュで e を作ってしまえばよい。
e := H(ctx, G, P, R)
R は公開されるので、検証者も同じ e を自分で計算できます。往復が消え、 proof は 1 通（R, s）で完結します。
さらにハッシュの入力にメッセージ m を混ぜると、
e = H(ctx, G, P, R, m) となり、
(R, s) はそのまま m への署名になります。これが Schnorr 署名で、
Bitcoin の BIP-340 や Ed25519 がこの系統です。
課題では challenge_hash(R, pubkey, message, n) が与えられ、
署名側と検証側の両方が、同じ引数で e を計算し直す作りになっていました。
実測 — ハッシュの引数の順番を入れ替えただけ
challenge_hash(R, pubkey, ...) を
challenge_hash(pubkey, R, ...) と取り違えた実装です。
FAIL: test_sign_vector AssertionError: 7765...5734 != 9434...3357 : s = nonce + e*x mod n のはずです。e は challenge_hash(R, pubkey, message, curve.n) で計算します。 引数の順番(R が先、pubkey が後)も確認してください FAIL: test_roundtrip
面白いのは、これが「動く」ことです。署名側と検証側が同じ順番で間違えていれば、 自分の署名は自分で検証できてしまう（roundtrip が落ちたのは、 テストが用意した正しい公開鍵と噛み合わなかったため）。 ハッシュへの入力の並びは、相互運用の仕様そのもので、 自己検証だけでは正しさを確認できません。
ctx に何を入れるか
プロトコル名・曲線の種類・証明したい statement といった文脈情報を入れます。
同じ形の署名が、別の文脈で使い回されるのを防ぐためです。
「何をハッシュに入れ忘れたか」が、そのまま脆弱性になります。 メッセージを入れ忘れれば署名は付け替え放題、 公開鍵を入れ忘れれば別人の鍵で通る余地が生まれます。
地図
課題で登ったのはパイプラインの右端（proof を短くする部分）でした。 残りの箱は Week 4 以降で手を動かします。今週は地図として置いておくだけにします。
f(X) = 3X² + 2X + 5 は、係数の並び (5, 2, 3) としても、
いくつかの点での値の並び (f(x₀), f(x₁), f(x₂)) としても持てます。
次数 d の多項式は、異なる d+1 点での値が決まれば一意に決まるので、
この 2 つは同じ情報です。
なぜ多項式にするのか: 制約が何万本あっても、まとめて 1 本の多項式の等式にできるから。 そしてランダムな 1 点で値を比べるだけで、全体が一致しているかをほぼ確実に判定できる。 検証が「短く」なる仕掛けの中心がこれです。
評価する点を 1 の n 乗根の冪 {1, ω, ω², …} に揃えておくと、
係数表現と評価表現の変換が規則的になります。これが有限体上のフーリエ変換で、
素朴には O(n²)、FFT なら O(n log n)。
Week 3 の土台がここにも効きます。逆変換に出てくる 1/n は
n の逆元、ω は位数 n の元——どちらも土台編の言葉そのままです。
大きな対象（多項式や実行トレース）を短い値 c に固定して先に渡し、
後から中身を見せて開く。封をした封筒と同じで、性質は 2 つ。
binding: 開けるのは最初に入れたものだけ
hiding: 開くまで、相手が持っているのは c だけ
ハッシュなら c = Hash(r, m)（乱数 r を混ぜないと、候補が少ないとき総当たりで中身が割れる）。
Week 1 のノートで出てきた「箱」が、ここで正式な道具として戻ってきます。
秘密のスカラー τ に対する SRS = (P, τP, τ²P, …, τᵈP; Q, τQ) を公開しておくと、
係数を掛けて足すだけで C = f(τ)P が作れます（τ を誰も知らないまま）。
f(z) = y を示す → q(X) = (f(X) − y)/(X − z) を作り、π = q(τ)P を出す
検証: e(C − yP, Q) = e(π, τQ − zQ)
割り切れることが、f(z) = y と同値。そして「積の関係」を点だけで確かめるために
ペアリングが要ります。aP と bP から足し算で作れるのは
(a+b)P まで——積 abP には手が届かないので、
スカラーを指数へ移せる双線形写像を持ち込む、という筋道です。
Week 1 でやったことが、ここに戻ってきます。 制約は「0 になる式」に揃え、掛け算 1 個ずつに分解する（R1CS）。
w³ + w + 5 = y を分解する
t₁ ← w·w t₂ ← t₁·w y ← t₂ + w + 5
↓ 制約として読む
t₁ − w² = 0 t₂ − t₁w = 0 t₂ + w + 5 − y = 0
R1CS は (Az) ∘ (Bz) = Cz の形にまとまります。
並べ方は他にもあって、AIR は実行トレースの表を「隣り合う行の規則」で縛る方式
（行が増えても制約の記述量は変わらない）。
見た目は違っても、どれも計算の正しさを有限体上の制約として扱っている点は同じです。
一文でまとめると
zkSNARK は、公開 statement に対して秘密 witness が存在することを、 計算を制約と多項式へ翻訳し、commitment で短く固定して、 短い proof として検証できるようにする仕組み。
今週作った Schnorr は、この文の「短い proof」と「対話を消す」部分を、 いちばん小さい形で全部持っている実例でした。
検問クイズ
読んだだけでは定着しない。ここではあなたが検証者の席に座り、 有限体の計算・曲線上の点・トランスクリプトの受理を審査する。問題は毎回その場で生成され、 判定は上のラボと同じ計算器が行う。3 回誤判定したら、その回は終了。
検問モードを選ぶ
誤答するとその場で解説が出る。分野を絞って弱点だけ潰すこともできる。
持ち帰り
① 「受理された」は、それ単体では何の証拠でもない。 simulator が秘密なしで受理される会話を作れました。効いているのは中身ではなく、 証明者が先にコミットし、チャレンジを後から受け取るという順番です。
② 抽出器と攻撃は、同じ 1 本の式。
x = (s₁−s₂)(e₁−e₂)⁻¹ は、
「知っていることの証明」でもあり「nonce 再利用で鍵が漏れる理由」でもあります。
安全性の根拠と攻撃手順が表裏一体なのは、この分野でよく出てくる形です。
③ 乱数の条件が 1 つ欠けると壊れる。 Week 2 の Beaver triple は使い回した瞬間に、Week 2 の OT は 範囲から 0 を除いた瞬間に、Week 3 の nonce は再利用した瞬間に壊れました。 3 週連続で同じ教訓です。
④ 2 つの法を混ぜない。 座標は mod p、スカラーは mod n。取り違えても小さい値のケースだけは通ってしまうので、 テストが弱いと気づけません。
⑤ 検算できる不変量を 1 つ持つ。
楕円曲線なら is_on_curve。
「結果が必ず満たすはずの性質」を 1 つ決めておくと、デバッグが探索から確認に変わります。
そして Week 1 からの問いは、今週こう言い換わります —— 「この値を隠しているのは何で、その条件は何本あるか」。 r がランダムであること、毎回違うこと、ハッシュに正しい文脈が入っていること。 1 本でも欠ければ、静かに壊れます。