ガーブルド回路（Yaoの2者間計算）

解きたい問題：二者が「見せずに」同じ答えを得る

二人が、それぞれの秘密の入力について、ある関数の値だけを一緒に求めたい。ただし互いの入力そのものは決して見せたくない――これが二者間安全計算（Secure Two-Party Computation, 2PC）の設定です。古典的な例が百万長者問題で、二人がどちらの資産が多いかを、正確な金額を明かさずに判定します。

素朴には「信頼できる第三者に両方の入力を渡し、答えだけ返してもらう」ことで解けます。**ガーブルド回路（Garbled Circuit, Yao のプロトコル）**が実現するのは、まさにこの理想的第三者を、当事者二人だけで暗号的に模倣することです。1986 年に Andrew Yao が示したこの構成は、任意の計算可能な関数を秘密計算に落とせる汎用手法であり、複数者向けの秘密分散系（BGW/GMW）と並ぶ MPC の二大系統の一つです（全体像は 準同型暗号と秘密計算（MPC）の原理 を参照）。土台となる公開鍵・共通鍵の考え方は 暗号の基礎 を前提とします。

登場人物は二人。関数を暗号化する側を Garbler（回路作成者）、暗号化された回路を受け取って評価する側を Evaluator（評価者） と呼びます。核心の発想は一言で言える――論理回路の真理値表を暗号化して相手に渡し、相手にはラベルの意味を伏せたまま計算させる。

ブール回路とワイヤラベル

まず計算対象の関数を、AND・XOR・NOT などのブール論理ゲートだけからなる回路に変換します。加算・比較・条件分岐といったどんな計算も、原理的にはゲートの組み合わせで表せます。

Garbler は回路の各ワイヤ（ゲートの入出力線）に対し、0 と 1 の二つの真理値それぞれへランダムに選んだラベル（対称鍵）を割り当てます。あるワイヤ w について、W0（真理値 0 を表す鍵）と W1（真理値 1 を表す鍵）を用意する、という具合です。ここが本質で、ラベルは十分に長いランダムなビット列（例 128 ビット）であり、ラベルだけを見ても、それが 0 を表すのか 1 を表すのかはまったく判別できません。

各ワイヤ w に 2 本のラベルを割り当てる:
  W0 = ランダム 128bit 鍵   （真理値 0 を表す）
  W1 = ランダム 128bit 鍵   （真理値 1 を表す）

ラベル単体からは真理値が読み取れない
→ Evaluator が鍵を握っても「どちらのビットか」を知り得ない

Evaluator は回路を評価する間、各ワイヤについて片方のラベルだけを手にします。しかしそれが 0 側か 1 側かを知らないため、計算の途中経過（中間値）を一切学習できません。これが「見せずに計算する」の仕掛けの根っこです。

ガーブルドテーブル：真理値表を暗号化する

次に各ゲートの真理値表を暗号化します。2 入力ゲートを例にとります。入力ワイヤを a・b、出力ワイヤを c とし、それぞれにラベル対 {A0,A1}、{B0,B1}、{C0,C1} が割り当て済みとします。ゲートの各行は「入力の組み合わせに対する出力」を表しますが、Garbler はこれを入力ラベルを鍵にして出力ラベルを暗号化した形に置き換えます。

AND ゲート（0 AND 0 = 0, 0 AND 1 = 0, 1 AND 0 = 0, 1 AND 1 = 1）なら、暗号化された各行は次のようになります。

AND ゲートのガーブルド行（Enc は入力2ラベルを鍵とする対称暗号）:
  Enc(A0, B0) -> C0      # 0 AND 0 = 0 → 出力ラベルは C0
  Enc(A0, B1) -> C0      # 0 AND 1 = 0
  Enc(A1, B0) -> C0      # 1 AND 0 = 0
  Enc(A1, B1) -> C1      # 1 AND 1 = 1 → 出力ラベルは C1

その後、4 行の順番をランダムにシャッフルして送る

各行は「対応する二つの入力ラベルの両方を鍵として持っているときだけ、正しい出力ラベルへ復号できる」暗号文です。Evaluator が入力ワイヤ a・b について片方ずつのラベル（例えば A1 と B0）を持っていれば、4 行のうち Enc(A1, B0) の行だけが復号に成功し、出力ラベル C0 が得られます。他の 3 行は鍵が揃わないため復号できません。

Evaluator は暗号化された全ゲートの表（ガーブルドテーブル）を受け取り、入力側から出力側へ一段ずつ復号していきます。あるゲートで得た出力ラベルは、次段のゲートの入力ラベルとしてそのまま使えます。こうして回路全体を評価し切ると、最終出力ワイヤのラベルが手に入ります。最後に Garbler が「出力ラベルと真理値の対応表（C0→0, C1→1）」だけを開示すれば、Evaluator は答えのビットを知れます。表の暗号化には、ラベルを鍵とした復号成功を検証可能な形にするため、認証付きの対称暗号が使われます（設計思想は AEAD（認証付き暗号）の設計原理 が参考になります）。

忘却通信：Evaluator の入力をどう供給するか

ここで一つ問題が残ります。Evaluator が回路を評価するには、自分の入力ビットに対応するラベルを Garbler から受け取らねばなりません。ところが素朴に渡そうとすると矛盾が起きます。

• Garbler が両方のラベル（0 用と 1 用）を渡してしまえば、Evaluator は両方の真理値で回路を試せてしまい秘密計算にならない。
• Evaluator が「自分は 1 が欲しい」と伝えて片方だけ渡してもらう方式では、Garbler に Evaluator の入力ビットが漏れてしまう。

この綱引きを解くのが 忘却通信（Oblivious Transfer, OT） です。OT は「送信者が持つ二つの値のうち、受信者が選んだ片方だけを、受信者はもう片方を得られず、かつ送信者は受信者がどちらを選んだか分からない」まま転送する二者間プリミティブです（1-out-of-2 OT）。

1-out-of-2 OT:
  送信者(Garbler)  が 2 値 (m0, m1) を持つ
  受信者(Evaluator)が選択ビット s ∈ {0,1} を持つ

  結果:
    Evaluator は m_s だけを得る（m_(1-s) は得られない）
    Garbler は s を知らない（どちらが選ばれたか分からない）

Garbler は各入力ワイヤについて m0 = W0, m1 = W1（両ラベル）を OT の送信側に置き、Evaluator は自分の入力ビット s を選択ビットにして Ws だけを引き出します。これで Evaluator は自分の入力に対応するラベルだけを、選んだ内容を Garbler に知られずに入手できます。一方、Garbler 自身の入力ラベルは OT を使わず単純に自分で選んで送るだけで済みます（自分のビットは自分が知っているので秘匿の必要がない）。OT は Diffie-Hellman のような公開鍵プリミティブから構成でき、さらに少数の「基点 OT」を対称暗号で大量に増幅する OT extension により実用速度が得られます。

半正直モデル：どこまでの攻撃者を想定するか

Yao の基本プロトコルが安全性を保証するのは、半正直（semi-honest, honest-but-curious）モデルの攻撃者に対してです。半正直な参加者はプロトコルの手順には正しく従うが、そのやり取りの記録（受け取ったメッセージ）から相手の秘密を可能な限り推測しようとします。この設定では、Garbler は回路と OT の送信側を規定どおり作り、Evaluator は復号を規定どおり行いつつ、盗み見できる情報がないかを探る、という想定です。

これに対し、悪意ある（malicious）モデルの攻撃者は手順から逸脱できます。典型的な脅威が、Garbler が約束した関数とは違う回路をこっそり作ってガーブルする「回路のすり替え」です。Evaluator はラベルの意味を知らないため、渡された回路が正しい関数を計算しているか自力では確かめられません。半正直モデルはこの逸脱を想定から除外することで成立しています。

悪意ある攻撃者に耐えるには追加の仕掛けが要ります。代表が cut-and-choose で、Garbler に回路を多数個ガーブルさせ、Evaluator がそのうちランダムに選んだ一部を開かせて正しさを検査し、残りを実際の評価に使います。不正な回路を混ぜても検査で高確率に露見するため逸脱が割に合わなくなります。ただし回路を何十倍も作るため通信・計算コストが跳ね上がります。半正直モデルは、この重い対策を省ける分だけ軽量で高速だ、という位置づけです。

通信量を削る最適化

ガーブルド回路の主要コストは、ゲートごとのガーブルドテーブル（素朴には 2 入力ゲートで 4 行）の通信量です。実用化はこれを削る一連の最適化に支えられています。

• Row reduction（行削減）：point-and-permute と組み合わせ、4 行のうち 1 行を送らずに済ませる（3 行に削減）。
• Free-XOR：全ワイヤのラベル対を共通のランダム値 R で W1 = W0 XOR R と関係づけると、XOR ゲートはテーブルも暗号化も一切不要でラベルの XOR だけで評価できる。XOR が実質ゼロコストになるため、回路を XOR 主体に設計する動機が生まれる。
• Half-gates：Free-XOR と両立しつつ、AND ゲートを 2 行だけで表現する。提案時に「線形なガーブリング方式」という広いクラスの中では 2 行が下限と示され、長らく実用上の到達点とされてきた。

これらの積み重ねで、AND ゲートあたりの通信は暗号文 2 個まで縮み、XOR は無料になります。なお 2021 年には half-gates の前提を外れる手法（slicing and dicing）で 1 AND あたり 1.5 暗号文ほどまで削る研究も出ており、最適化はなお進行中です。回路サイズが直接コストを決めるため、秘密計算に載せる関数はゲート数、とりわけ AND ゲート数（乗算段数に相当）を減らすよう最適化されます。ここは、加算がローカルで無料・乗算に対話が要る秘密分散系 MPC と、コスト構造が対をなす特徴です。ラベルの暗号化・導出には固定鍵ブロック暗号（AES-NI）や、鍵付きハッシュ的な構成（MAC と HMAC の設計原理 の考え方に近い擬似ランダム関数）が使われ、ハードウェア支援が実効速度を大きく左右します。

まとめ

ガーブルド回路は、二者が互いの入力を明かさずに関数の値だけを得るという 2PC の目標を、論理回路を暗号化することで達成します。Garbler は関数をブール回路に直し、各ワイヤの 0/1 にランダムなラベルを割り当て、各ゲートの真理値表を入力ラベルで出力ラベルを暗号化し行をシャッフルしたガーブルドテーブルに変えます。Evaluator はラベルの真理値を知らないまま表を復号して回路を評価するため、中間値も相手の入力も学習しません。

Evaluator が自分の入力ラベルを、選んだ内容を隠しつつ片方だけ受け取るために 忘却通信（Oblivious Transfer） が不可欠で、これが入力供給の要になります。標準的な安全性は手順を守りつつ盗み見る半正直モデルに対して成立し、逸脱する悪意ある攻撃者には cut-and-choose などの重い追加対策が要ります。Free-XOR で XOR ゲートを無料化し、half-gate で AND を 2 行に削る最適化が実用性を支えています。MPC 全体での位置づけと秘密分散系との対比は 準同型暗号と秘密計算（MPC）の原理、OT の土台となる公開鍵プリミティブは Diffie-Hellman と併せて押さえると、秘密計算の設計判断がつかめます。