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

平面に点が 2 つあれば、その両方を通る直線はただ 1 本です。 逆に点が 1 つだけなら、そこを通る直線は無数にあります。

この非対称がすべてです。 2 つ集めれば決まる。1 つでは何も決まらない。 「決まらない」を「分からない」に使うのが秘密分散の発想です。

秘密の値を s とします。乱数 a を 1 つ用意して、次の直線を作ります。

f(x) = s + a·x

ここで x = 0 を入れると f(0) = s + a·0 = s。 秘密は「x = 0 のときの値」として埋め込まれています。

なぜ x = 0 に置くのか: 配るのは x = 1, 2, 3, … の値だけにするためです。 0 番の値だけは誰にも渡さない。だから直線が復元できて初めて秘密にたどり着きます。

参加者 1 には f(1)、参加者 2 には f(2)、参加者 3 には f(3) を渡す。 この値をシェアと呼びます。

計算はすべて有限体 F_p の上で行います（Week 1 と同じ世界です）。 以下では見やすさのため p = 11 を使います。

なぜ有限体なのか: 実数のままだと、シェアの大きさから秘密の大きさが推測できてしまいます （切片が大きければ値も大きい、など）。mod p で巻いてしまえば大小の手がかりが消えます。 Week 1 で見た「順序が存在しない」性質が、ここでは利点として効いています。

秘密 s = 3、乱数 a = 5、p = 11 とします。

f(x) = 3 + 5x　（mod 11）

f(1) = 3 + 5 = 8
f(2) = 3 + 10 = 13 = 11 + 2 → 2
f(3) = 3 + 15 = 18 = 11 + 7 → 7

配るのは 8, 2, 7 の 3 つ。 どれも秘密の 3 とは似ても似つかない数字です。

参加者 1（x=1, y=8）と参加者 2（x=2, y=2）が集まったとします。

傾き a = (y₂ − y₁) ÷ (x₂ − x₁) = (2 − 8) ÷ (2 − 1) = −6 ÷ 1 = −6 = 5　（mod 11）

切片 s = y₁ − a·x₁ = 8 − 5·1 = 3 ✓

−6 がなぜ 5 なのか: mod 11 の世界では −6 + 11 = 5。 Week 1 でやった「引き算は逆元を足すこと」がここでも効いています。 割り算も同じで、÷1 は 1 の逆数 1 を掛けること。 もし分母が 1 でなければ、逆数を求めてから掛けます。

参加者 1 だけが y = 8 を持っているとします。この人にとって、 秘密 s は 0 から 10 のどれでもありえます。

s = 0 なら a = 8（0 + 8·1 = 8 ✓）
s = 1 なら a = 7（1 + 7·1 = 8 ✓）
s = 2 なら a = 6（2 + 6·1 = 8 ✓）
…… 11 通りすべてに、辻褄の合う a が 1 つずつ存在する

これが「情報がゼロ」の正確な意味です。 シェアを見る前の推測（11 通りが等確率）と、見た後の推測がまったく同じ。 1 ビットも減っていない。「解読が難しい」ではなく「原理的に不可能」です。 下のラボで実際に 11 通り全部を並べて確認できます。

直線（次数 1）なら 2 点で決まりました。放物線（次数 2）なら 3 点必要です。 一般に次数 t の多項式は t+1 点で決まる。

f(x) = s + a₁x + a₂x² + … + a_t x^t　→　復元に必要な人数は t + 1

設計の自由度がここにあります。 「5 人中 3 人集まれば復元できる」なら次数 2 を使う。 t 人以下では、さっきと同じ理屈で情報がゼロのままです。

参加者 i が手元で f(i) · g(i) を計算します。

f(i)·g(i) = (s + a·i)(s' + b·i)
= s·s' + (s·b + s'·a)·i + (a·b)·i²

これを h(x) = s·s' + (sb + s'a)·x + (ab)·x² と置けば、 確かに h(i) です。そして h(0) = s·s' —— 欲しかった積が切片に入っています。

h(x) には x² の項があります。直線ではなく放物線です。

何が困るのか: 次数 1 なら 2 人で復元できました。次数 2 は 3 人必要です。 掛け算するたびに必要人数が増えていく。 2 回掛ければ次数 4、3 回で次数 8 —— すぐに参加者の人数を超え、誰も復元できなくなります。

h(x) の係数を見ると、x の係数は s·b + s'·a、 x² の係数は a·b です。

元の乱数 a, b から作られていて、独立ではありません。 本来なら 2 つの係数はそれぞれ独立な乱数であってほしいのに、 a·b は a と b に縛られている。 ここから情報が漏れる余地が生まれます。

次数 2 になった多項式を、秘密は同じまま次数 1 に作り直す必要があります （degree reduction）。そしてこの作業は 1 人ではできません—— 自分のシェアしか持っていないからです。

これが通信の正体です。 加算は各自の手元で閉じるのに、乗算は参加者どうしのやりとりが要る。 MPC のコストが乗算の数で決まるのは、この 1 点に尽きます。

まだ何を計算するか決まっていない暇な時間に、次を満たす 3 つの乱数を作ります。

a, b はランダム　　c = a · b

そして a, b, c をそれぞれ秘密分散して配ります。 値そのものは誰も知りません。知っているのは「c = a·b という関係があること」だけ。

ここがポイント: 掛け算という重い作業を、入力が来る前に済ませてしまう。 この 3 つ組を Beaver 三つ組 と呼びます。

秘密 x と y の積を計算したくなりました。まず次の 2 つを計算して公開します。

d = x − a　　e = y − b

引き算はさっき見たとおり無料なので、シェアのまま計算できます。

公開して大丈夫なのか: 大丈夫です。a は誰も知らない乱数なので、 d = x − a はランダムな値にしか見えません。 Week 1 の言葉で言えば、乱数で撹乱されている状態。x は漏れません。

d = x − a を移項すると x = d + a、同様に y = e + b。 これを掛けて展開します。

x · y = (d + a)(e + b)
= d·e + d·b + a·e + a·b
= d·e + d·b + a·e + c　　（a·b = c だった）

右辺を見てください。d と e は公開済みの普通の数。 a, b, c はシェアとして持っている。

つまり右辺は「公開された定数」×「シェア」の足し算だけです。 d·b は b のシェアを d 倍するだけ、a·e は a のシェアを e 倍するだけ。 定数倍と加算は無料でした。 秘密どうしの掛け算が、1 つも残っていません。

乗算 1 回に必要だった「次数を戻す通信」が、d と e を公開する 1 往復に置き換わりました。 重い前処理は、入力が来る前に終わっています。

これが MPC の実装で最初に出てくる工夫です。 前処理と本番を分ける設計はこの分野の定石で、 Week 6 の co-snark-prove は、まさにこの Beaver 乗算を実装する課題です。

x·y = c + d·b + e·a + d·e のうち、c, b, a は シェアとして分散されています。でも d·e は公開値どうしの積、ただの数です。 全員が自分のシェアに足すと、復元時に人数分カウントされます。

# d·e を全 party に足した壊れ版（3 party, p = 67）
AssertionError: 57 != 41   # (n−1)·d·e = 2·d·e だけ余る

シェアと公開値は「足し方」が違う。シェアは全員が成分ごとに、 公開値は代表 1 人（party 0）だけが足す。この区別が曖昧なままだと、 復元して初めて壊れていたと分かります。

いちばん面白い壊れ方です。d = x − a を「x を開いて、a を開いて、引く」と実装しても、 積の値のテストは全部通ります。落ちるのはこれだけ。

test_fixed_share_vector ................. ok
test_products_for_two_and_three_parties . ok
test_opens_exactly_the_two_masked_differences ... FAIL
AssertionError: 4 != 2   # 開示回数が 2 回ではない

「答えが正しい」と「開きすぎていない」は別の性質。採点器は reconstruct の呼び出しを数えて、 マスク済みの d, e 以外を開いたら落とします。MPC の正しさは出力だけでは測れない—— 実行中に何を公開したかまで含めてプロトコルです。

同じ a で 2 つの秘密を隠すと、攻撃者はネットワーク上の公開値だけから 差を復元できます。実測（p = 67, x₁ = 12, x₂ = 55, 同じ a = 29）:

公開値: d₁ = 50, d₂ = 26
攻撃者: d₁ − d₂ = 24 (mod 67)
真の値: x₁ − x₂ = 12 − 55 = −43 = 24 (mod 67)  ← 一致

d = x − a が安全なのは、a がワンタイムパッドだから。2 回使えば d₁ − d₂ = x₁ − x₂ で a が消え、秘密どうしの関係が丸見えになります。 前処理で三つ組を「乗算の回数分」用意する理由がこれです。

sender は 2 通のメッセージ m₀, m₁ を差し出す。 receiver は選択ビット choice で 1 通だけ受け取る。

普通の通信では両立しません。どちらが欲しいか言えば sender に選択が漏れ、 両方もらえば receiver が読みすぎる。暗号で「開けられない封筒」を作って初めて両立します。

sender は秘密 a から A = g^a を公開。 receiver は秘密 b を引いて、request B の作り方を choice で変えます。

choice = 0 → B = g^b
choice = 1 → B = A·g^b

sender は 2 つの鍵を K₀ = B^a, K₁ = (B/A)^a と導出して それぞれのメッセージを暗号化。receiver の鍵は常に A^b = g^{ab} です。

choice = 0 なら K₀ = (g^b)^a = g^{ab} が一致し、choice = 1 なら K₁ = (A·g^b/A)^a = g^{ab} が一致する。 選んだ側の封筒だけが開き、もう一方の鍵を得るには離散対数を解く必要があります。

課題の仕様に「receiver secret b は 0..q−1 から選ぶ」とあります。 0 を除いて 1..q−1 にすると何が起きるか、request の分布を全部数えました。

request = 8 を見たら choice = 0 と確定、request = 1 なら choice = 1 と確定。 「一様分布が choice によらず同じ」という性質は、範囲が 1 点欠けるだけで壊れます。 仕様の端の値には、たいてい理由があります。

request を常に B = g^b にした壊れ版では、choice = 0 の復号は全部成功し、 choice = 1 だけがゴミを返します。

choice=0 ... ok（全部成功）
choice=1: AssertionError: b'\xc2\x97\xc1W\xb7' != b'right'

B に A を織り込むのは receiver の仕事で、それをして初めて sender 側の K₁ = (B/A)^a と鍵が揃う。「どちらの封筒が開くか」は request の作り方が決めています。

P0 は乱数マスク r₀₁ を引き、2 通のメッセージを用意します。

m₀ = r₀₁　　m₁ = r₀₁ ⊕ x₀

P1 が y₁ を choice にして OT すると、受け取る値は t₀₁ = r₀₁ ⊕ x₀·y₁（y₁ = 0 なら m₀、1 なら m₁——ちょうどこの式になります）。

クロス項 x₀y₁ が「r₀₁ で焼き付けられた形」で P1 に渡りました。 P1 が見るのはマスク済みの 1 ビットだけなので x₀ は漏れない。 P0 は OT の約束で y₁ を知らない。誰も何も知らないまま、項だけが移動しています。

P1 が sender: m₀ = r₁₀, m₁ = r₁₀ ⊕ x₁　　P0 が y₀ で選ぶ → t₁₀ = r₁₀ ⊕ x₁·y₀

採点器は OT の実行回数も数えています（2 回でなければ落ちる）。 クロス項は 2 つ、OT も 2 つ。1 回で済ませる近道はここにはありません。

z₀ = x₀y₀ ⊕ r₀₁ ⊕ t₁₀　　（P0 の手元にある材料だけ）
z₁ = x₁y₁ ⊕ r₁₀ ⊕ t₀₁　　（P1 の手元にある材料だけ）

XOR すると、マスクがペアで消えます。

z₀ ⊕ z₁ = x₀y₀ ⊕ x₁y₁ ⊕ r₀₁ ⊕ (r₀₁ ⊕ x₀y₁) ⊕ r₁₀ ⊕ (r₁₀ ⊕ x₁y₀)
= x₀y₀ ⊕ x₀y₁ ⊕ x₁y₀ ⊕ x₁y₁ = x·y ✓

Beaver の d·e と同じく、マスクは「入れた人が自分の側で打ち消す」設計です。 r₀₁ は P0 が入れて P0 の z₀ で消える。打ち消しの場所を間違えると、 復元して初めて壊れていたと分かる——数の世界とまったく同じ教訓です。