答えが正しくても、開きすぎたら落ちる――MPC・Beaver triple・紛失通信

zk-tokyo のAdvanced Cryptography Program 2026を受講しています。Week 2 のテーマは MPC（秘密計算）で、課題toy-mpcでは有限体上の秘密分散と Beaver triple による乗算、そして紛失通信（OT）を使った GMW 方式の AND ゲートを実装しました。

今回いちばん印象に残ったのは、積の値がすべて正しいのに採点器に落ちる実装が作れることです。MPC の正しさは出力だけでは測れない、というのが今週の持ち帰りでした。

自習ノート: 秘密を分けて、集めずに計算する
週ごとの目次: Advanced Cryptography 2026 自習ノート
リポジトリ: susumutomita/advanced-cryptography-note

線形はタダ、非線形だけが高い

秘密sを 3 人に分けるには、乱数を 2 個引いてそのままシェアにし、最後の 1 人が帳尻を合わせます。復元は全員の合計です。

share = [r1, r2, s - (r1 + r2) mod p]

この分け方は線形なので、加算は各自が手元で足すだけで終わります。通信はゼロです。ビットの世界の XOR シェアでもまったく同じことが成り立ちます。

壁は乗算（ビットなら AND）です。シェアどうしを掛けても積のシェアにはならず、参加者どうしの通信が必要になります。Week 1 で「コストは乗算の数で決まる」と学びましたが、MPC では理由が別で、乗算だけが通信を要求するからでした。

公開してよいのは「マスク済みの差分」だけ

Beaver triple は、この通信を前処理に追い出す技法です。事前にc = a * bを満たす乱数の組をシェアとして配っておき、本番では次の 2 つだけを公開します。

d = x - a,  e = y - b

aとbの値は誰の手元にも存在しない（シェアされたままの）乱数なので、dとeはランダムにしか見えません。積はx * y = c + d*b + e*a + d*eと、公開値とシェアの線形結合だけで書けます。

ここで課題の採点器が面白い仕掛けを持っていました。わざと「xとaをそのまま復元してからdを手元で計算する」実装に差し替えてみると、こうなります。

test_fixed_share_vector ................. ok
test_products_for_two_and_three_parties . ok
test_opens_exactly_the_two_masked_differences ... FAIL
AssertionError: 4 != 2

積の値を確かめるテストは全部通ります。落ちるのは開示回数を数えるテストだけです。「答えが正しい」と「開きすぎていない」は独立した性質で、採点器は後者を復元関数の呼び出し回数で監査していました。MPC のコードレビューで見るべきは出力ではなく、実行中に何が公開されたかだと体で覚えられます。

同じ triple を 2 回使うと、公開値だけで差が漏れる

もう 1 つ、問題文の警告どおりに壊してみました。同じaで 2 つの秘密を隠すと、ネットワーク上の公開値だけから差が復元できます。

公開値: d1 = 50, d2 = 26（p = 67, x1 = 12, x2 = 55, 同じ a = 29）
攻撃者: d1 - d2 = 24 (mod 67)
真の値: x1 - x2 = -43 = 24 (mod 67)  ← 一致

d = x - aが安全なのはaがワンタイムパッドの役割を果たすからで、2 回使えば引き算でaが消えます。前処理で triple を乗算の回数分だけ用意する理由がこれでした。

ビットの世界では OT が同じ役を担う

課題の後半は XOR シェアの AND です。展開するとx0*y1とx1*y0というクロス項が現れますが、この 2 つはどちらの手元にも材料がそろいません。「P1 の選択ビットに応じて、P0 の持つ 2 つの値のどちらかを渡す。ただし P0 に選択を知られず、P1 に両方渡さない」という綱渡りが必要で、これを実現するのが 1-out-of-2 紛失通信（OT）です。

課題の仕様に「receiver の乱数bは 0 を含む0..q-1から選ぶ」という一文があり、なぜ 0 を含むのかを分布で数えてみました。bを1..q-1に狭めると、choice = 0 では出ない request と choice = 1 では出ない request が 1 つずつ生まれ、request を見ただけで選択が確定するケースができます。仕様の端の値には理由がある、という良い教材でした。

持ち帰った問い

Week 1 の問いは「この信号を縛っている式はどれか」でした。Week 2 ではそれが「この値を隠している乱数は何か」に姿を変えます。d = x - aを守るのはaが使い捨てであることで、OT の request を守るのはbの一様性です。隠している乱数の条件が 1 つ欠けた瞬間に、どちらも音を立てずに壊れます。

自習ノートを更新しました

秘密を分けて、集めずに計算する

Week 1 と同じ構成で、単一の HTML ファイル・外部通信なしです。壊した実装の採点出力はすべて実測を載せました。GMW の AND を OT の鍵導出まで 1 ステップずつ確かめられるラボと、シェア計算・Beaver 検算・開示監査・OT 検問・GMW 検算・原理の 6 分野から出題される検問クイズ（ライフ 3・10 問・S/A/B/F ランク）が付いています。判定はラボと同じ計算器が行うので、答えの暗記では通れません。