Susumu Tomita

Advanced Cryptography Program 2026 / Week 6 自習ノート

隠す・分ける・示すを組み合わせる — 予習ノート

Week 6(Application — 理論を応用設計へ)の予習ノートです。 対話ドリル 3 本・38 行(mod 97 の整数・16 ビットの足し算・sha256 の先頭 6 桁だけ。python3 と打てば始められる)で 「秘密を分けたまま証明を組む」「実行を表にして 1 行ずつ確かめる」「預けたことは示すが、どれかは言わない」を自分の手で通し、 そのあと講義スライド 41 枚と同じ順番のカードで言葉を埋めます。

この週の全体像は 1 文で言えます。ZK は「示す」、MPC は「分ける」、FHE は「隠す」— 3 つは競合ではなく、足りない保証を補い合う部品で、要件から逆算して組む。 グループワーク①(暗号文のまま AI 診断)の模範解 Verifiable FHE = 隠す + 示す は、その典型です。

対話ドリル 3 本・38 行 スライド 41 枚追従 宿題 2 問への地図 前提は Week 2 の秘密分散と Week 4 の制約 外部通信なし

出発点 — Week 6 の予習

5 週かけて手に入れた 3 つの道具は、「どれを使うか」ではなく「何が足りないか」で選ぶ

Week 1〜4 で証明(ZK)と秘密分散(MPC)を、Week 5 で暗号文のままの計算(FHE)を、それぞれ別々に学びました。 今週はそれらが合流します。講義の言い方では「信頼する第三者を、検証できる数学に置き換える」。 ただし 3 つは万能薬ではありません。ZK は正しさを示すが秘密を持ち寄れない。MPC は秘密を分けて計算できるが、計算が正しかったかは参加者の信頼に乗る。 FHE はデータを隠して計算を任せられるが、サーバが正しく計算したかは分からない。 だから「FHE で隠したい、かつ正しさも確かめたい」なら FHE + ZK、「秘密を持ち寄ったまま 1 つの証明にしたい」なら MPC + ZK。足りない保証を、別の道具で埋める — それがこの週の設計法です。

読み方

ドリル A(分ける + 示す = co-SNARK)→ B(実行そのものを示す = zkVM)→ C(示す、そして壊す = Tornado Cash と抜けた制約 1 行)の順に、1 行打って出た値を貼って 1 文読む。準備は python3 と打って >>> が出るだけ(ドリル C だけ import hashlib を最初の行で打つ)。そのあとカードを上から。宿題 2 問(co-snark-prove / zkvm-exploit)は、ドリル A と B の数そのままです。

前の週とのつながり

ドリル A の「share」「Beaver triple」は Week 2 の秘密分散です(p = 97 の余りだけ)。ドリル B の「制約が全部 0 なら正しい実行」は Week 4 の PLONK・AIR の制約と同じ考え方で、ここでは 16 ビットの足し算 1 種類しか制約がありません。ドリル C の「commitment」「Merkle 木」は Week 3・4 のコミットメントの最小版で、ハッシュは sha256 の先頭 6 桁で済ませます。Week 5 の FHE は数式では出ませんが、Verifiable FHE のカード(25〜27)で「Week 5 に足りなかったもの」として戻ってきます。

この頁の構成

    対話ドリル — 1 行打って、出た値を貼って、1 文読む

    3 つの合成を、mod 97 の整数・16 ビットの足し算・sha256 の先頭 6 桁だけで手で回す

    python3 を開いて >>> が出たら始められます。 各行に「この行の意味」、出た値を貼ると、その値を指す解説が開きます。Python を開けないときは「ここで実行」。 ドリル A と B は宿題の README とテストの数値そのままなので、宿題を書くときにそのまま突き合わせられます。

    ドリル A — 分けたまま、証明を組む(co-SNARK。宿題 co-snark-prove の p = 97, w = [3, 5])

    秘密を 2 つに分ける。足し算と定数倍は分けたまま手元でできる。掛け算だけは、前もって配った「乱数の積」で 1 往復。

    14 行。まず share 1 つを見ても秘密が分からないことを 3 通りで確かめ、線形結合が「share ごとに同じ計算」で済むことを見てから、share 同士を掛けても積の share にならないことを実際に失敗させ、Beaver triple で直します。最後に、公開した差 d からも秘密が絞れないことを見ます。

    ドリル A — 分けたまま、証明を組む

    0 / 0

    ドリル B — 実行そのものを表にして、1 行ずつ確かめる(zkVM。宿題 zkvm-exploit の CAP = 1000, 16 ビット)

    クーポン検証プログラムは 16 ビットで足し算する。65535 + 1001 は 1000 に化ける。この「あふれ」が攻撃で、実行の表と制約が、それを 1 行の 0 でない数として捕まえる。

    14 行。正しいクーポンで検証器が通ることを見てから、真の合計は 66536 なのに 16 ビットでは 1000 になって通ってしまう入力を作ります。実行を表(trace)にして隣接する 2 行の制約が全部 0 になることを見て、表を 1 か所書き換えると 0 でなくなることを見ます。最後にプログラムの識別子(program_id)を出し、「どの攻撃かは言わずに、攻撃が存在する」だけを公開する claim を組みます。

    ドリル B — 実行を表にして、1 行ずつ確かめる

    0 / 0

    ドリル C — 預けたことは示す、どれかは言わない(Tornado Cash。スライド 12〜13 と 33)

    預かり証 C = h(k, r) を木に入れる。引き出すときは「木のどれかの葉の k, r を知っている」と nullifier h(r) だけを見せる。そして、制約が 1 行抜けると何が起きるかを見る。

    10 行。ハッシュは sha256 の先頭 6 桁で、4 枚の葉の Merkle 木を手で作ります。根の検証・使用済み札・二重引き出しの拒否まで通したあと、偽造者が別の r2 を持ってきたときにどの検査が止めるのか、そして回路がその検査を「要求していなかったら」どうなるかを見ます。スライド 33(Zcash Orchard)が 1 行で再現できます。

    ドリル C — 預けたことは示す、どれかは言わない

    0 / 0

    スライド 2〜9 / 暗号プリミティブを組み合わせる

    「信頼する誰か」を「検証できる数学」に置き換える — 3 つの道具は競合ではなく部品

    ここからのカード列は講義スライド 41 枚を同じ順番で追いかけます(目次だけのスライド 3・10・28・35 は飛ばします)。1 カード = 主張 1 つ。カード末尾の Q. は講義が問いとして置いたもの、緑の帯は宿題・ドリルとの対応です。

    2/41本日の流れ

    講義は 4 部構成。① ZK / MPC / FHE を整理して目的指向で合成する → ② アプリケーション紹介(zkVM / zkTLS / zkML / zkEmail / PIR / World ID)→ ③ 要件定義(設計フロー・ライブラリ・性能・プライバシー・法律)→ ④ ホワイトボードセッション。

    これまでの週は「1 つの道具の中身」でした。今週は「道具を選んで組む」側に立ちます。実装時の注意点(性能・セキュリティ・プライバシー・法律)は第 3 部(カード 31〜34)でまとめて扱います。

    4/41信頼できる第三者を、数学で置き換える

    Trusted Third Party(各人が秘密を「信頼する誰か」に預ける)→ Mathematically Trustworthy Protocol(信頼を暗号プロトコルに置き換える)。Programmable Cryptography が目指すのはこの置換。

    Nick Szabo の「The God Protocols」(1997)が出発点です。全員が秘密を預けられる神様がいれば、秘密入札も匿名投票も一瞬で済む。その神様の役を、誰も信頼せずに数学で果たすのが ZK・MPC・FHE です。

    ドリルで見る形: ドリル A の 2 人は、どちらも w の全体を持たないまま証明を組みます(誰も神様にならない)。ドリル C は「預かり所」に何を見せずに済むかを追います。

    5/41任意のデータ形式を相互変換する汎用アダプタ

    HTTPS / DKIM などで既に署名済みのデータを、zkSNARK で検証しながら任意の宛先形式へ変換できる。既存サービスの移行を待たずに相互運用が成り立つ。

    ここが「応用」の入口です。世の中のデータは、すでに誰かが署名しています(Web サーバの TLS、メールの DKIM、パスポートの IC チップ)。その署名を回路の中で検証すれば、「Google がこのメールを送ったと保証している内容のうち、この 1 項目だけを示す」ができる。zkEmail・zkTLS・POD2(補遺)は全部この形です。

    6/41special-purpose から programmable cryptography へ

    special-purpose = 1 つの操作だけを暗号的に保証(署名 / range proof / group signature)。programmable = 暗号の中で汎用計算ができる(ZK / MPC / FHE / Witness Encryption / iO)。

    Week 1 の署名や Week 2 の秘密分散は「1 つの操作」でした。汎用計算ができるようになると、「何を保証するか」を回路(プログラム)で自由に書ける。だから今週は数式ではなく設計が主題になります。

    7/41ZK / MPC / FHE のおさらいと比較

    3 つは位相(誰が誰と何をやり取りするか)で覚える。各セルの保証は「無料ではない」対価で、組み合わせれば全部解決、は誤り。

    ZK — 事実を証明するMPC — 秘密を持ち寄って計算FHE — データを見せずに計算させる
    π : ∃w. C(x, w) = 1f(x₁, x₂, x₃)、各 xᵢ は各自の手元E(x) → blind eval → E(f(x))
    隠す対象証明者の witness w各参加者の入力計算データと中間状態
    信頼前提証明者を信頼しなくてよい(数学が保証)k-of-n の party を信頼(t 未満が corrupt)Server を信頼(正しく計算するか)
    敵対モデル証明者(偽証)/ 検証者(witness 窃取)Party(最大 t 名が逸脱: semi-honest / malicious)盗聴者(復号・改ざん)/ Server(復号試行)
    主な用途年齢証明 — 生年月日を出さず「18 以上」秘密入札 — 入札額を漏らさず最高値暗号文 AI 診断 — 医療データを暗号化のまま分析

    信頼前提の行が設計の要です。FHE は「Server を信頼」と書いてある — 中身は見えないが、正しく計算したかは分からない。MPC は「t 未満の共謀」までしか守れない。この 2 つの穴が、カード 8 の合成パターン②(Verifiable FHE)と⑥(co-SNARK)を生みます。

    8/41プリミティブは組み合わせられる — 6 つの代表的合成パターン

    各アプリは、暗号プリミティブどうし、または既存システムとの合成として現れる。

    #名前合成何をしたか
    LongfellowZK ∘ ECDSA (mDOC)既存 ID 標準(mDOC / JWT)を ZK 化
    Verifiable FHEZK + FHEFHE の計算の正しさを ZK で保証(カード 25〜27)
    threshold FHEMPC + FHEFHE の鍵を MPC で分散管理
    POD2ZK + 署名データ署名済みデータを証明して組み合わせる(補遺 39〜40)
    leanVMZK + XMSS耐量子署名を再帰集約して 1 proof に(カード 18〜20)
    co-SNARKZK + MPC入力を秘匿したまま協調証明(World ID、カード 22〜24)

    この週のドリルと宿題は ⑥ と ②、それに zkVM: ドリル A / 宿題 co-snark-prove が ⑥(分ける + 示す)、ドリル B / 宿題 zkvm-exploit が zkVM(実行を示す)、GW① の模範解が ②(隠す + 示す)。3 つの合成の「+」の部分を、それぞれ 1 行の Python で通します。

    9/41暗号プリミティブは 1 つの計算機に統合される

    ZK = 検証可能な配線(wire)、FHE-MPC = 秘匿計算 CPU、ORAM = 高速な暗号 state、Ethereum = 社会規模のハードディスク。「zkSNARK 単体で何ができるか」ではなく、統合スタックとして何が作れるかを問う。

    コンピュータの部品に見立てた図です。配線(結果を運ぶ = 正しさの証明)、CPU(秘密のまま計算)、記憶(アクセスパターンも隠す)、ディスク(誰でも読める公開台帳)。この見立てが、カード 29 の「欲しい成果物から選ぶ」決定木の土台になります。

    スライド 11〜14 / Tornado Cash と Solidity verifier

    預けたことは示す、どれかは言わない — commitment・nullifier・Merkle 所属の 3 点セット

    ドリル C がこの節の数値版です。C = h(k, r)、4 枚の葉の木、根 b712a6、nullifier 790269

    11/41ゼロ知識証明を用いたアプリケーション

    Tornado Cash(匿名ミキサー)/ zkVM(任意プログラムの実行を、回路を手書きせず証明)/ zkEVM(EVM 実行を証明して L1 を圧縮)/ leanVM(耐量子署名 leanXMSS を zkVM で再帰集約)/ zkEmail(DKIM 署名を ZK 検証)/ zkML(モデル推論の正しさを ZK 証明)。

    6 つのうち、この節で Tornado Cash を、次の節で zkVM と leanVM を深掘りします。zkEVM・zkEmail・zkML は「zkVM の上に作られた用途特化」として、カード 15 で位置づけられます。

    12/41Tornado Cash のユーザーフロー:預入 → 匿名集合 → 別アドレスで引出

    User A が 1 ETH と commitment C を預入アドレス(公開)から送る。同じ固定額の預入が 1 本の Merkle 木に集まり、どれが誰の C か埋もれる。無関係な新アドレス A′ が証明 π を出して 1 ETH を受け取る。

    預入:  A ──(1 ETH + C)──▶ プール(Merkle 木: root ← C₁, C, C₃, C₄)
           note (k, r) は手元だけ・秘密
    引出:  A′ ──(π)──▶ プール ──(1 ETH)──▶ A′
           A ↔ A′ のリンクを暗号的に断ち切る

    匿名集合(anonymity set)は「自分と見分けがつかない人の集まり」です。木に葉が n 枚あれば、引き出した人は n 人のうちの誰か。預入者が増えるほど大きく育ちます。

    ドリル C の 2〜4 行目: C = h(k, r)leaves.index(C)root。「木に入っている」を根 1 つで表せることが、この 3 行で見えます。

    13/41Tornado Cash:リンクを断つ仕組みと、使い方で漏れる匿名性

    commitment + nullifier + Merkle membership で預入と引出のリンクを暗号的に断つ。ただし匿名性は暗号の外 = 使い方で決まる。

    ① 預入   乱数を 2 つ: secret k(秘密)、nullifier r(後で二重引出を防ぐ)
             commitment C = H(k, r) を提出、1 ETH を送金。k, r はチェーンに出さない
    ② 匿名集合  commitments の Merkle 木。預入者が増えるほど大きい
    ③ 引出   新アドレス A′ から zk-SNARK で証明:
               ▸ k, r を知る葉 C が木に存在(membership)
               ▸ nullifierHash = H(r) を公開
             nullifierHash 既出なら拒否 = 二重引出を防止。リレイヤーがガス代を肩代わり

    暗号が保証すること: 預入 C と引出は数学的に連結不可(zero-knowledge)。漏れるのは「木のどれかの葉」まで。nullifierHash で二重引出を阻止(soundness)。

    運用次第で漏れる情報: タイミング相関、関連アドレスの再利用、金額・ガス・リレイヤーの痕跡、過疎なプールで匿名集合が実質縮む。使用パターンのクラスタ分析で、Tornado Cash 取引のうち $2.3B 相当が身元特定可能と報告されています(arXiv 2510.09433)。暗号保証 ≠ 実用プライバシー

    ドリル C の 6〜8 行目: nh = h(r) を公開し、spent に入れ、2 回目は nh in spent が True で拒否。k は最後まで一度も出てきません — それが「どれかは言わない」の中身です。

    14/41ZK 証明をブロックチェーンで公開検証する:Solidity Verifier

    Solidity verifier = ZK 証明システムの検証アルゴリズムを Solidity コントラクトとして実装したもの。π と public inputs を渡すと on-chain で検証し、結果に応じて状態遷移をトリガーする。Tornado Cash のコントラクトがまさにこれ。

    ① Prover   witness を使って計算を実行し π を生成。witness は誰にも見せない
    ② Verifier コントラクトが π と public inputs を受け取り verify ✓/✗
               $ snarkjs zkey export solidityverifier circuit.zkey Verifier.sol
               人は回路(circom)だけ書き、verifier は機械生成
    ③ Chain    verify ✓ なら状態遷移(払出・認証・集約)。全ノードが同じ検証を独立に再実行

    Public Verifiability: ブロックチェーンは誰でも検証できる公開台帳なので、中央の信頼者が要りません。ZK の「正しさ」が、数学的事実から合意形成の基盤へ変わる。

    設計の含意: 「proof を誰が・どこで検証するか」は primitive 選択と同じくらい重要。オンチェーン検証 = gas cost という実コストが伴います(カード 32 の「0.93 KB の Groth16 が今も優位」に直結)。

    スライド 15〜20 / zkVM と LeanVM

    回路を手書きせず、実行の表そのものを証明する — trace・AIR・境界制約

    ドリル B がこの節の数値版です。trace [0, 65535, 1000]、遷移の残差 [0, 0]、1 か所書き換えると [0, 65535]。宿題 zkvm-exploit の guest プログラムは、この表の「中で走る側」を書く問題です。

    15〜16/41zkVM:任意プログラムの実行を証明する

    Rust / C の普通のプログラム → RISC-V などの VM ISA にコンパイル → 実行トレース(1 命令ずつ記録)→ 算術化して STARK/SNARK で prove → 小さな proof を再実行せず検証。on-chain でも安価。

    Week 4 までの ZK は「回路を手で書く」でした。zkVM は「CPU の 1 ステップが正しい」という制約を 1 回だけ書いておき、どんなプログラムもその CPU の上で走らせれば証明できる、という発想です。zkEVM・zkEmail・zkML はいずれもこの上に作られた用途特化(スライド 15)。

    宿題 zkvm-exploit の立ち位置: zkVM 本体は動かしません。書くのは「zkVM の中で走る guest プログラム」(guest_main)と、「何を公開し、何を witness に残すか」(public_claim)。Proof of Exploit = 「このプログラムには攻撃が存在する」を、攻撃入力そのものは見せずに示す。

    17/41zkVM の仕組み:実行トレースを算術化して証明する

    trace T ∈ Fⁿˣʷ(n ステップ × w 列: pc・レジスタ・メモリ操作・フラグ)。∀i: C(T[i], T[i+1]) = 0(隣接行が ISA 規則に従う)と、T[0] = init・out(T[n−1]) = y(境界)。正しい実行 ⟷ 全行で制約多項式が 0

    ① 実行 → トレース表   エミュレータが 1 命令ずつ実行し、各ステップの VM 状態を 1 行に記録
    ② 算術化(AIR)        各列を有限体上の多項式とみなし、「正しい実行」を多項式の恒等式に帰着
                            隣接行制約 + 境界制約が、評価領域の全点で 0 になるか
    ③ 証明(STARK/SNARK)  多項式コミット + 検査で恒等式を簡潔に証明。verify は数点の評価のみ
       単変数系: 商多項式 + FRI(Week 4)   多変数系: hypercube 上の sumcheck(Jolt / WHIR → LeanVM)

    要点: 証明者はネイティブ実行の 10³〜10⁶ 倍重い。continuations / precompiles / recursion / GPU proving で実用化が進む。検証側は一貫して軽い。

    ドリル B の 6〜9 行目がこのスライドの最小版です。trace は「16 ビットの合計」1 列だけ、隣接行制約は (trace[i] + c[i]) % M − trace[i+1] の 1 種類、境界制約は「先頭は 0」「末尾 ≤ CAP」。表を 1 か所書き換えると残差が 65535 になって捕まる。制約が全部 0 であることが、証明の中身です。

    18/41LeanVM:Ethereum の PQC 移行のための zkVM

    各 validator は毎スロット、ブロックに署名する。量子計算機が BLS 署名(楕円曲線)を破るため、ハッシュベースの耐量子署名 leanXMSS への置換が必須。leanXMSS は 1 個 ~3,000 B(BLS は 96 B)で単純加算で集約できない → zkVM が全署名の検証を 1 つの小さな proof に再帰集約(約 250 倍圧縮)。

    なぜ zkEVM ではないのか: ① 対象が違う — zkEVM は実行層、要るのは合意層の署名集約。② zkEVM は楕円曲線依存で量子脆弱。PQC 移行の VM がそれでは本末転倒。③ 速度と形式検証のため ISA は最小。

    : 「verify ∘ verify ∘ …」の再帰集約は、Week 4 の「証明の証明」(recursion)そのものです。1 つの proof が「4 つの署名検証がすべて通った」を表す。

    19/41LeanVM の構成

    レジスタは FP / PC のみ(AP なし)、メモリは read-only、ISA は ADD / MUL / DEREF / JUMP の 4 命令だけ。無駄をそぎ落とした設計。

    命令が 4 つしかない理由は、カード 17 の「隣接行制約」の数がそのまま証明コストになるからです。命令が少ないほど制約も少なく、形式検証もしやすい。ドリル B の VM は命令 1 つ(16 ビット加算)で、その極端な例です。

    20/41LeanVM の証明システム

    実行を複数のテーブルに分け、lookup で Memory に束ね、GKR で結合して証明する。1 サイクルわずか 5 要素のみコミット。多項式コミットは WHIR。

    Week 4 の PLONK では 1 つの大きな表に全部を入れました。LeanVM は表を役割ごとに分けて(4 テーブル)、表どうしの整合を lookup(Logup*)で取ります。コミットする量が減るので証明者が軽くなる。

    スライド 21〜24 / zkTLS・PIR・World ID・co-SNARK

    秘密を持ち寄ったまま、1 つの証明にまとめる — 線形は手元、掛け算だけ通信

    ドリル A がこの節の数値版です。p = 97、w = [3, 5] を 2 人に分け、A = 13・B = 17 の積 27 の share を Beaver triple で組みます。宿題 co-snark-prove の linear_combination_sharesmpc_prove がそのまま対応します。

    21/41その他のアプリケーション

    zkTLS(ZK + MPC)= Web2 の API レスポンスを第三者検証可能に(TLSNotary / vlayer / Reclaim)。PIR(FHE)= どのインデックスを引いたか隠して取得。World ID(co-SNARK)= 虹彩コードの一意性を秘匿したまま検証。Verifiable FHE(FHE + ZK)= 暗号文のまま計算を委託し、結果の正当性も検証。

    PIR(Private Information Retrieval)は「図書館で何を借りたか司書にも知られずに本を借りる」です。RPC やライトクライアントが「どのアカウントの残高を見たか」を隠すのに使います。zkTLS は、TLS 通信の中身を MPC で秘密分散したまま処理して「このサーバがこう返した」を証明する — カード 5 の「署名済みデータのアダプタ」の TLS 版です。

    22/41World ID:AI 時代の Proof of Personhood

    Orb スキャン → iris code 化 → 一意性を判定し、検証済み人間の集合(Merkle 木)へ登録。

    問題は「一意性判定」です。新しい虹彩コードを、既登録の数百万件と照合しなければならない。しかし虹彩コードは究極の個人情報で、平文で持ちたくない。ここで MPC と co-SNARK が要ります。

    23/41World ID の構成:秘匿照合・検証可能性・匿名性の合成

    World ID は単一プリミティブではなく、秘匿照合(MPC)・検証可能性(co-SNARK)・匿名性(Semaphore)の合成。

    ① Orb スキャン(専用 HW)  虹彩から人間性と一意性を読み取る
    ② iris code 化              生画像は破棄。一意性判定用のコードのみ残す
    ③ 一意性チェック(MPC)      iris code を秘密分散し、平文を誰も見ずに既登録と照合
    ④ 計算の検証可能性(co-SNARK) 照合が正しく行われたことを公開検証可能に(TACEO:Proof, 2025)
    ⑤ 匿名クレデンシャル(Semaphore) 身元を隠して「検証済み人間」を証明し、二重使用を防止

    発行後のプライバシー(⑤): Semaphore は検証済み人間の Merkle 木に「匿名で」所属を証明する — Tornado Cash と同じ commitment + nullifier + membership です。nullifier は (user × app × action) ごとに決定的だが紐付け不可なので、本人を特定せずに「1 人 1 アクション」を強制し、アプリ横断トラッキングを防ぐ。World ID 4.0 は分散 OPRF で nullifier を計算し one-time-use 等で強化(生体情報の規制議論は継続)。

    ドリル C とのつながり: ⑤ はドリル C の 10 行がそのまま当てはまります。葉が「預かり証」から「検証済み人間の commitment」に変わるだけ。

    24/41co-SNARK:複数者の秘密入力を 1 つの証明にまとめる

    witness を秘密分散して配る(各 party は自分の share だけ、誰も w 全体を知らない)→ MPC で協調 prove(線形な MSM・FFT はローカル = 無料、乗算だけ通信ラウンド)→ open で π を得る。single-prover と byte-identical な 1 proof。検証者・vk・proof サイズは無変更。

    分散  [w] ← Share(w)          誰も w 全体を持たない(N 者へ秘密分散)
    MPC   Prove(pk, x; [w])        線形(MSM・FFT)= ローカル / 乗算のみ通信
    open  π ← Open(A, B, C)        single-prover と byte-identical
    verify Verify(vk, x, π)        検証側は何も変えなくてよい

    「線形はローカル、乗算だけ通信」の理由: share の足し算・定数倍は、各自が自分の share に同じ計算をするだけで、結果の share になります。掛け算はそうならない(share 同士の積は積の share ではない)。だから掛け算のときだけ Beaver triple で 1 往復する。証明生成の大半(MSM・FFT)は線形なので、通信は少なくて済みます。

    ドリル A の 5〜12 行目がこの 3 段です。A_sh = [5, 8](線形 = 手元)→ share 同士の積は (21, 27) で不一致(掛け算は手元では無理)→ Beaver で (d, e) = (8, 8) を公開 → z = [27, 0] → open 27。宿題では linear_combination_shares(5〜7 行目)と mpc_prove(9〜12 行目)。

    スライド 25〜27 / Verifiable FHE

    FHE が守るのは機密だけ — 「正しく計算したか」は証明で足す

    Week 5 の FHE に足りなかったものが、ここで名前を得ます。サーバが暗号文のまま f を計算して E(f(x)) を返しても、それが本当に f だったかは分からない。garbage を返されてもユーザは気づけない。

    25〜26/41Verifiable FHE:FHE に「計算の正しさ」を足す(ZK + FHE)

    FHE が守るのはデータ機密だけ。「正しく計算したか」は別問題。そこに ZK で計算の正しさを足すのが Verifiable FHE。

    ユーザが秘密データ x を E(x) にしてサーバへ。サーバは中身を見ずに f を評価して E(f(x)) を返す。ここまでが Week 5。問題は、サーバが f ではなく g を計算していても、ユーザは復号するまで分からず、復号しても「これが f(x) か」を確かめる手段がないことです。

    27/41Verifiable FHE の構成:暗号文評価に「正しさの証明」を添える

    enc → eval → prove₁(ユーザ: 暗号文が正しく作られている)→ prove₂(サーバ: c′ = Eval(f, c))→ verify。証明者が違う点が要。

    enc:    c ← Enc(pk, x)                             ユーザが暗号化(中身は秘匿)
    eval:   c′ ← Eval(f, c)                            サーバが暗号文のまま f を評価(FHE)
    prove₁: π_wf ← ZKProve{ ∃x, r : c = Enc(pk, x; r) ∧ noise 範囲内 }   ユーザ。x を隠す → ZK 必須
    prove₂: π_eval ← Prove{ c′ = Eval(f, c) }         サーバ。秘密なし → succinct で十分
    verify: Dec(sk, c′) = f(x) かつ Verify(π_wf, π_eval) = ⊤   機密性 + 正しさ を同時に

    注(講義が強調した点): π_eval に zero-knowledge 性は必須ではありません。c, c′, f は公開で、隠す witness が無い。本質は succinctness — 再実行より安く検証できること。SNARK / STARK で十分。ZK が要るのは π_wf(平文 x を隠す)と、サーバがモデル重み等を秘匿する場合。

    コスト: FHE の bootstrapping と ZK 証明生成が支配的で重い。回路バグは soundness を壊すので検証が要る(カード 33)。

    Week 5 との橋: π_wf の「noise 範囲内」は、Week 5 ドリル A の「ノイズが Δ/2 を超えると復号が壊れる」そのものです。ユーザが正しい範囲のノイズで暗号化したことを、ノイズの値を見せずに証明する。GW①(カード 36・41)の模範解がこれ。

    スライド 29〜30 / 決め方と実装

    欲しい成果物から逆算する — 5 つの問いで primitive が決まる

    29/41欲しい成果物からプリミティブを選ぶ

    問いは 5 つ。欲しい成果物は「証明」か「計算結果」か? witness(秘密)は誰が持つ(単独 / 複数者)? 証明対象は回路か任意プログラムか? 誰が計算する(複数者で共同 / 第三者に委託)? その計算の正しさも証明したいか?

    欲しいのは証明
      witness は単独 ── 回路      → 回路 DSL(Circom / Noir / halo2)
                     └ 任意プログラム → zkVM(RISC0 / SP1 / Jolt)
      witness は複数者(分散)      → co-SNARK
    欲しいのは計算結果
      複数者で共同計算              → MPC
      第三者に委託 ── 正しさは不要  → FHE
                 └ 正しさも証明したい → Verifiable FHE

    使い方: 上から順に答えるだけで 1 つに決まります。GW①「医療データを見せずに AI 診断、正しさも確認したい」→ 計算結果 → 第三者に委託 → 正しさも → Verifiable FHE。宿題 co-snark-prove → 証明 → 複数者 → co-SNARK。宿題 zkvm-exploit → 証明 → 単独 → 任意プログラム → zkVM。

    30/41実装の紹介

    ZK: Circom + snarkjs(回路 DSL + Groth16 / Plonk、最も普及)。zkVM: RISC0(RISC-V トレースを STARK で証明、Groth16 に変換してオンチェーン検証)。co-SNARK: co-snarks(TACEO、Circom 回路を coSNARK 化、World ID の基盤)。Threshold FHE: threshold-fhe(Zama、TFHE の復号鍵を MPC で分散管理、FHEVM の KMS 基盤)。Verifiable FHE: EagleEye(FHE 演算トレースを Plonk 系制約に変換して証明)。

    選定基準: trusted setup の要否 / 言語エコシステム / 想定用途で選ぶ。Groth16 は回路ごとに trusted setup が要るが proof が最小(0.93 KB)。Plonk・STARK 系は setup 不要か汎用だが proof が大きい。カード 32 の実測に続きます。

    スライド 31〜34 / 動くだけでは不十分

    性能・安全性・プライバシー・法律 — 4 つの落とし穴を設計段階で織り込む

    ドリル C の 9 行目(抜けた制約 1 行)がスライド 33 の再現です。

    31/41動くだけでは不十分

    4 つの観点。パフォーマンス(ZK: prover 重い・verify 軽い/ MPC: 通信ラウンドが支配的/ FHE: bootstrapping が支配的)、セキュリティ(ZK: soundness と zero-knowledge は別物/ MPC: 閾値超の共謀で漏れる/ FHE: 機密性のみ)、プライバシー(メタデータ・タイミング・利用パターン、MPC の出力そのもの、FHE のアクセスパターン)、法律・規制(OFAC 制裁・マネロン規制・GDPR・年齢確認義務)。

    soundness と zero-knowledge は別物、がこの節の鍵です。soundness = 偽の主張が通らない。zero-knowledge = 秘密が漏れない。片方だけ壊れることがあり、Zcash(カード 33)で壊れたのは soundness でした。

    32/41パフォーマンス:ZK はモバイルで実用段階に入った

    同じ 3 つの主張(パスポート検証・WebAuthn・OPRF)を、同じ端末で Circom + Groth16 / Noir + Barretenberg / ProveKit v1 の 3 方式に証明させた実測。手元の端末で証明を作ることが現実的なコストに収まりつつある。

    指標(Moto E15, 2 GB RAM)Groth16ProveKit v1読み方
    証明生成時間 Passport P1241.6 s22.0 s約 11 倍速い。WebAuthn は Groth16 が OOM で完走せず
    必要ダウンロード量 WebAuthn1,753 MB2.4 MB回路ごとの巨大な鍵配布が消える
    proof サイズ Passport P10.93 KB716 KBここだけ逆転。約 770 倍に膨らむ

    教訓: 速くなった代わりに proof が重くなった。手元での証明生成は実用域に入ったが、その proof をオンチェーンで検証するなら 0.93 KB の Groth16 が今も優位。「一番速い方式」は存在せず、証明を誰がどこで検証するかで方式が決まる(カード 14 の設計の含意)。出典は ProveKit チーム自身の計測で、第三者の追試ではない点は講義も注記しています。

    33/41セキュリティ:Zcash Orchard の偽造脆弱性

    halo2 回路の制約漏れ 1 行が soundness を破り、無制限・検出不能な偽造を可能にした(2026 年発覚)。壊れたのは soundness で、zero-knowledge ではない。

    - let base = assign_advice(cs, || g_d)?;              // witness するだけ、g_d との一致を制約しない
    + let base = copy_advice(cs, || g_d, g_d_upstream)?;  // g_d と一致することを制約(copy constraint)

    何が起きたか: base point が制約なし → 任意の値を witness 可能 → nk を偽造者が自由選択 → ivk = Commit(ak, nk, rivk) を偽造 → 同一 note に複数 nullifier → 無制限偽造 / 二重支払いが検知不能(秘匿取引)。05-29 に Taylor Hornby が AI 支援監査(Claude Opus 4.8)で発見。人手監査は 4 年間見逃していた。06-02 緊急ソフトフォーク、06-03 NU6.2 で回路を修正。

    教訓: 回路の制約漏れは 1 行でも致命的。秘匿性ゆえ過去の悪用有無は暗号学的に検証不能。

    ドリル C の 9 行目: 偽造者が r2 を持ってきたとき (h(r2) in spent, h(k, r2) == C)(False, False)。左が False なので使用済み検査は素通り。右が False なのは当然で、偽造者は r2 と C を結ぶつもりがない。回路が「C = h(k, r) を満たす r で nullifier を作った」を要求していればここで止まり、要求していなければ左の False だけで 2 回目が通る。Orchard の assign_advice は「witness を置くだけで結びつきを制約しない」— 同じ形です。

    34/41法律・規制:Tornado Cash 事件

    プライバシー技術は、設計・デプロイ・運用する人が規制の対象になりうる。プロトコルと開発者は別々に裁かれている。

    2022-08  米 OFAC が Tornado Cash を制裁指定(コントラクトアドレスを SDN リスト化)。蘭で開発者 Pertsev 逮捕
    2023-08  米 DOJ が Storm / Semenov を訴追(マネロン共謀・制裁違反・無登録送金業)
    2024-05  蘭裁判所が Pertsev をマネロン幇助で有罪、禁錮 5 年 4 か月
    2024-11  米第 5 巡回区 Van Loon v. Treasury: 不変のスマートコントラクトは「財産」でなく OFAC は越権 → 2025-03 制裁解除
    2025-08  Storm に無登録送金業で有罪評決。マネロン・制裁違反は評決不一致で一部 mistrial
    2026-09  Storm は未量刑、不一致の 2 罪状は 2026-10 に再審理予定。Pertsev は条件付き釈放で控訴審係属中

    設計上の論点: プロトコルへの制裁は解除され、Tornado Cash の利用自体は違法ではなくなった。一方で開発者個人の刑事責任は今も係争中。コードは中立でも運用主体は問われうる。送金業ライセンス・制裁コンプライアンス・不変コントラクトの法的扱いを、設計段階で織り込む必要がある(2026-09 時点、流動的)。

    スライド 36・41(+ 補遺 37〜40)/ グループワーク①

    暗号文のまま AI 診断 — 要件から Verifiable FHE に辿り着く

    講義中のホワイトボードセッションです。回答例(スライド 41)は先に見ずに、まずスライド 36 の 4 段階を自分でやってから開くのを勧めます。

    36/41グループワーク①:暗号文のまま AI 診断を設計する

    お題: ユーザが自分の医療データをクラウドの AI に診断させたい。クラウドにも第三者にも生データを見せたくない。さらに「診断が正しく計算された」ことを本人が確認したい。この要件を満たすスタックを設計せよ。

    1. 要件を言語化(アクター / 秘匿入力 / 公開出力 / 信頼境界)
    2. 各 primitive が何を保証するかを思い出し、要件を満たす組み合わせを自分で選ぶ
    3. ユーザーフローを書き出す(誰が → 何を → どの primitive を通り → 境界を越えるのは何か、時系列で)
    4. 落とし穴を 1 つ(性能 / soundness / メタデータ / 規制)

    Q. 発表(各 1 分): ユーザーフローを見比べ、「なぜ Verifiable FHE / なぜ MPC / なぜ TEE」を 1 文で説明できるか。

    予習でやっておくこと: カード 29 の決定木を上から答える。「欲しいのは計算結果 → 第三者に委託 → 正しさも証明したい」で 1 つに決まります。次に「MPC だとなぜ不利か」「TEE だとなぜ不利か」を、カード 7 の信頼前提の行から 1 文ずつ。

    補遺(スライド 37〜40)— Cryptomata と POD2
    38/41Cryptomata:数学が正しさと秘匿を保証する自律システム

    止められず・覗けず・改竄できない自己実行プログラム。obfuscation + ZK + MPC(+ 量子暗号)で、ID registry や医療・遺伝データなど社会基盤を暗号ネイティブに動かす将来像。

    39〜40/41POD2:署名データを証明し、組み合わせる汎用アダプタ

    SignedPOD(発行者が EdDSA 署名した key-value ストア、エントリを Merkle 木化して個別の値だけ選択開示)を入力に、演繹規則(Statement × Operation)で新しい主張を導き、再帰的に証明(MainPOD)を積み上げる。MainPOD 自体も POD なので次の証明へ合成できる。

    実装スタックはコンパイラ構造: Frontend(人間可読な型)→ Middleware(型付き中間表現)→ Backend(証明系 Plonky2、trusted setup 不要・再帰向き。on-chain 検証時は Groth16 で wrap)。カード 5 の「署名済みデータのアダプタ」の一般形です。

    41/41グループワーク① 回答例:暗号文のまま AI 診断

    生データを渡さず、診断の正しさまで確認する。Verifiable FHE = FHE + ZK が両方の要件を同時に満たす。

    ① ユーザ(患者)  医療データ D を FHE 公開鍵で暗号化し Enc(D) だけをクラウドへ。D はローカル
    ② クラウド AI     暗号文のまま推論 f を評価し Enc(f(D)) を返す。同時に「c に正しく f を評価した」証明 π を生成
    ③ ユーザ(検証)  Enc(f(D)) を復号して診断結果 + π を検証。データ機密(FHE)と計算の正しさ(ZK)を同時に確認
    信頼境界          クラウドは信頼しない。境界を越えるのは Enc(D) と Enc(f(D)) + π だけ

    なぜこの組み合わせ: FHE 単体はデータ機密のみで「正しく計算したか」は保証しない → ZK を重ねた Verifiable FHE で埋める。MPC / TEE は信頼前提とコストで不利。

    落とし穴: 性能(FHE の bootstrapping が支配的)/ soundness(Verifiable FHE の回路バグ、カード 33)/ メタデータ(誰がいつ診断したかは隠れない、カード 13)/ 規制(医療データ = GDPR・HIPAA、カード 34)。

    宿題の地図

    宿題 2 問の関数は、ドリルのどの行か

    宿題はどちらも「primitive の中で/上で走る計算」を書きます。zkVM 本体や SNARK 本体は動かしません。数はドリルと同じなので、書いた関数にドリルの入力を渡せば、ドリルの出力がそのまま期待値です。

    宿題 / 関数ドリルの行何を確かめるか
    co-snark-prove
    linear_combination_shares
    A の 5〜7 行目係数 × share を share ごとに足すだけで、線形結合の share になる。open すると平文で計算した A = 13、B = 17 と一致。add_sharesscale_shares は支給済み
    co-snark-prove
    mpc_prove
    A の 8〜12 行目share 同士の積は積の share にならない(8 行目で失敗させる)。Beaver triple (a, b, c) を使い、d = A − a と e = B − b を open して z = c + d·[b] + e·[a] + d·e(d·e は片方だけ)。open すると 27 = 13 × 17 mod 97。beaver_multiply は支給済みで、それを呼ぶ形
    zkvm-exploit
    is_exploit
    B の 2〜5 行目「プログラムは受理する(16 ビットの合計 ≤ CAP)」かつ「真の合計は CAP を超える」の両方が成り立つとき True。legit / honest は False、[65535, 1001] と [65535, 65535, 1002] は True
    zkvm-exploit
    public_claim / program_hash
    B の 10〜11 行目公開するのはプログラムの識別子と「攻撃が存在する」だけ。攻撃入力は witness に残す。v2 のプログラムは別の識別子になる
    zkvm-exploit
    guest_main
    B の 12〜14 行目攻撃でない入力には Err("rejected")、攻撃なら PublicClaim。2 つの違う攻撃入力が同じ公開出力を返す(13 行目 True)— これが「どの攻撃かは言わない」の中身

    Python のドリルと Rust の宿題の対応

    % 65536wrapping_add(u16 のあふれ)。真の合計はドリルでは普通の int、Rust では u64 で取る(u16 で足すとまた化ける)。hashlib.sha256(...)[:8]DefaultHasher — ただし DefaultHasher は暗号学的ハッシュではなく、Rust のバージョンが変わると値も変わる。テストが「同じビルドの中で決定的」しか要らないから済んでいるだけで、本物の zkVM は SHA-256 のような衝突耐性のあるハッシュでプログラムに束縛します。Beaver triple はドリルでも宿題でも引数で渡される(実運用では試合前の offline phase で配っておく)。

    予習チェック

    講義の前に、自分の言葉で言えるか 7 問

    (1) ZK・MPC・FHE を「誰が誰と何をやり取りするか」で 1 行ずつ言えるか。それぞれの信頼前提はどこに残るか。 (2) Tornado Cash の引き出しで、証明者が示す 2 つのことは何か。k と r のどちらを、どの形で見せるか。 (3) zkVM の「正しい実行」は、表(trace)のどんな性質に置き換わるか。表を 1 か所書き換えると何が起きるか。 (4) co-SNARK で「線形はローカル、掛け算だけ通信」なのはなぜか。share 同士を掛けると何がまずいか。 (5) FHE だけでは何が保証されないか。Verifiable FHE の 2 つの証明は、誰が何を証明するか。π_eval に zero-knowledge は要るか。 (6) soundness と zero-knowledge はどう違うか。Zcash Orchard で壊れたのはどちらか、原因は何行か。 (7) 「医療データを見せずに AI 診断、正しさも確認したい」を、カード 29 の決定木で上から答えると何に着くか。MPC・TEE はなぜ不利か。

    言えなかった番号だけカードに戻る: 1 → 7/41、2 → 13/41 とドリル C、3 → 17/41 とドリル B、4 → 24/41 とドリル A、5 → 27/41、6 → 31・33/41、7 → 29・41/41。

    用語カード

    用語の意味と、なぜその言葉なのか — 中学・高校の数学から橋を架ける

    用語からではなく、知っている数学から入る。「余り」から mod へ、「2 人で持つ半券」から share へ、「答え合わせが全部 0」から制約へ。

    用語意味なぜその言葉かどこで
    share(シェア)秘密 w を 2 つの数に分けて、足すと w に戻るようにしたもの(w = s₁ + s₂ mod p)。片方だけ見ても w は分からない — ドリル A の 4 行目で、同じ share 1 から 3 通りの秘密が出るshare = 分け前。秘密の「分け前」を 1 人 1 つ持つドリル A、スライド 24
    Beaver triple秘密と無関係な乱数 a, b とその積 c = ab の 3 つ組。share 同士は掛けられないので、前もって配った (a, b, c) の share を使い、d = A − a と e = B − b だけ公開して積の share を作るDonald Beaver(1991)の手法。3 つ組なので tripleドリル A 9〜12 行目、スライド 24
    co-SNARKwitness を秘密分散したまま、複数の証明者が協力して 1 つの SNARK を作る。出来上がる proof は 1 人で作ったものと byte 単位で同じcollaborative(協調)SNARKスライド 24、宿題 co-snark-prove
    witness / public inputwitness = 証明者だけが知る秘密の入力。public input = 検証者にも見せる入力。「∃w. C(x, w) = 1」の w と xwitness = 証人。「私はこれを知っている」の「これ」スライド 7、ドリル B 10〜13 行目
    zkVM回路を手で書く代わりに、「CPU の 1 ステップが正しい」制約を 1 回だけ書いた仮想計算機。上で走らせたどんなプログラムの実行も証明できるzero-knowledge Virtual Machineスライド 16〜17、宿題 zkvm-exploit
    guest プログラムzkVM の中で走るプログラム。宿題の guest_main。外側(host)が証明を作るhost(主人)の家に泊まる guest(客)。実行環境の内と外宿題 zkvm-exploit
    trace(実行トレース)プログラムの実行を、1 ステップ = 1 行で並べた表。列は pc・レジスタ・メモリ操作など。ドリル B では「16 ビットの合計」1 列だけtrace = 足跡。実行が残した足跡の一覧スライド 17、ドリル B 6 行目
    AIR / 隣接行制約「i 行目と i+1 行目の関係はこうでなければならない」を式にしたもの。全行で 0 なら正しい実行。表を 1 か所いじると 0 でなくなるAlgebraic Intermediate Representation。代数(式)で書いた中間表現スライド 17、ドリル B 7〜8 行目
    境界制約表の最初と最後の行に課す条件。「最初は 0 から始まる」「最後の値が出力 y に等しい」boundary(境界)= 表の端スライド 17、ドリル B 9 行目
    soundness / zero-knowledgesoundness = 偽の主張が通らないこと。zero-knowledge = 証明から秘密が漏れないこと。別々の性質で、片方だけ壊れることがある(Zcash で壊れたのは soundness)sound = 健全。「健全性」と「零知識性」スライド 31・33、ドリル C 9 行目
    commitment(預かり証)秘密を決めた、という証拠を先に出しておく値。C = H(k, r)。後で k, r を明かせば「あのとき決めていた」が示せるが、C から k, r は逆算できないcommit = 約束する。値を約束しておくスライド 13、ドリル C 2 行目
    nullifier(使用済み札)引き出すときに公開する H(r)。同じ r からは同じ値が出るので、2 回目は「既出」で拒否される。しかし C = H(k, r) とは結びつけられないので、どの預入かは漏れないnullify = 無効にする。使った札を無効化するスライド 13・23、ドリル C 6〜8 行目
    Merkle membershipハッシュを 2 つずつ束ねて木にし、根 1 つで全部の葉を代表させる。「私の葉は木にある」を、根と兄弟ハッシュの列(path)だけで示せるRalph Merkle の木。membership = 所属スライド 12〜13、ドリル C 3〜5 行目
    Verifiable FHEFHE(暗号文のまま計算)に、「本当にその関数を計算した」証明を添えたもの。ユーザは暗号文の well-formedness を ZK で、サーバは評価の正しさを succinct な証明で示すverifiable = 検証できる FHEスライド 25〜27・41
    threshold FHEFHE の復号鍵を 1 人が持たず、MPC で分散して持つ。t 人以上が集まらないと復号できないthreshold = しきい値。t 人というしきい値スライド 8・30
    PIRデータベースから「何番目を読んだか」をサーバに知られずに読む。FHE で「何番目か」を暗号化したまま取り出すPrivate Information Retrieval(秘匿情報検索)スライド 21
    zkTLSWeb サーバとの TLS 通信の中身を、MPC で分散したまま処理して「このサーバがこう返した」を第三者に証明するzero-knowledge + TLS(HTTPS の暗号層)スライド 21
    Semaphore「検証済みの集合に所属している」を匿名で証明し、nullifier で二重使用を防ぐ zk-SNARK の仕組み。Tornado Cash と同じ 3 点セットsemaphore = 手旗信号。身元を言わずに合図だけ送るスライド 12・23
    program binding(プログラム束縛)証明を「どのプログラムの実行か」に結びつけること。プログラムのハッシュを公開入力に入れる。ドリル B の program_idbind = 結びつけるドリル B 10〜11 行目
    succinct(簡潔)証明の検証が、計算をやり直すよりずっと安いこと。π_eval に要るのはこれで、zero-knowledge は要らないsuccinct = 簡潔な。短くて速いスライド 27