はじめに
この記事では、マルチパーティ版Garbled CircuitであるBMRプロトコルの解説をします。
MPC Overviewページ <- ここにMPC各記事へのリンクがあります。
BMRプロトコル
BMR（Beaver–Micali–Rogaway）は、
n人でYao型ガーブル回路を共同生成し、その後通常のガーブル回路として評価するプロトコル
です。
通常のYaoでは、
- 1人が回路をガーブル化
- もう1人が評価
しかしBMRでは、
- 誰も単独で回路をガーブル化しない
- n人全員で共同生成する
という違いがあります。つまり、n人でGarbled Tableを作る というのがこのプロトコルの目標です。
構造は次の2フェーズに分かれます。
フェーズ1：Garbling（n人でのMPC）
- 各プレイヤーがラベルの一部を生成
- n者MPCでGarbled Tableを構築
フェーズ2：Evaluation
- 入力に対応するラベルを集める
- 通常のガーブル回路評価を行う
Garbling Phase
ここではGarbled Tableを作る流れを示します。
1. ワイヤラベルの構造
各ワイヤ $w$ には2つのラベルがあります：
$$
w^0,\quad w^1
$$
BMRではこれをさらに分解します。
各プレイヤー $P_j$ が、
$$
w_{j}^0,\quad w_{j}^1
$$
を生成します。完全なラベルはその連結
$$
w^b = w_1^b | w_2^b | \dots | w_n^b \quad(b\in\{0,1\})
$$
ここで重要なのは、
- ラベルは値の秘密分散ではない
- 単なるランダムビット列
というところです。つまり、ラベル自体は元の値と何も関係ありません。
2. ポインタビットとフリップビット
各部分ラベルには：
- κビット鍵 $k$
- 1ビットのポインタ $p$
が含まれます。ポインタは後で合成されます。
$$
p^b = \bigoplus_j p_j^b
$$
ここで、$\bigoplus x_j=x_1 \oplus x_2 \oplus \dots \oplus x_n$です。
さらに各ワイヤにはフリップビット
$$
f = \bigoplus_j f_j
$$
があり、実際の論理値は
$$
v \oplus f
$$
として扱われます。
それぞれ何をしているかというと、
- ポインタ: garbled tableの対応表を作るときに使います（例えば、どれが0,0に対応する行なのか分かるようにする）
- フリップビット: どのラベルか分からないようにする処理（ラベルを見ただけでは 0用か1用か分からない）
3. Garbled Table の作成
各2入力ゲート（例：AND）について、入力組
$$
(0,0),(0,1),(1,0),(1,1)
$$
の4行を作ります。
各行は、
e_{v_a,v_b}
=
w_c^{v_c\oplus f_c}
\oplus
\bigoplus_j
(F(i,w_{a,j}^{v_a\oplus f_a}) \oplus F(i,w_{b,j}^{v_b\oplus f_b}))
ここで、$F$はPRG（Pseudo Random Generator）です。
この計算はn者MPCで行われます。つまり、お互いに$F(i,w_{a,j}^{v_a})$を秘密共有して計算できます。
最終出力：4つの固定長ビット列
見た目は単なるランダムデータです。つまり以下のようなデータが得られます。
Row 0: 100101100
Row 1: 011000011
Row 2: 110110110
Row 3: 110100110
それぞれラベルになっていて、どれが(0,0)なのかとか(1,0)なのかとかは分かりません。
Evaluation Phase
評価者が持つもの：
- ガーブルテーブル
- 各入力ワイヤのアクティブラベル
1. 入力ラベルの取得
各プレイヤーは：
- 自分の入力ビットに対応する部分ラベルのみを送る
評価者はそれらを連結して：
$$
w^x = w_1^x | w_2^x | \dots | w_n^x
$$
を得ます。ここでx=0 or 1です。
2. 行選択
ラベル内のポインタビットを取り出し、
$$
p^x = \bigoplus_j p_j^x
$$
を計算。
これにより4行のうち1行を選びます。
3. マスク除去
選択行に対して、
$$
e \oplus \bigoplus_j F(i,w_{a,j}^x) \oplus \bigoplus_j F(i,w_{b,j}^y)
$$
を計算。
PRGマスクが消え、
$$
w_c^{v_c \oplus f_c}
$$
が得られます。
4. 出力復元
最終ワイヤでは、
- 合成フリップビット $f_c$ を公開
- あるいはデコード表を使用
して$v_c$を復元します。
具体例（3人・AND）
設定
- 3人
- κ=2
- 1つのANDゲート
出力ラベル（例）
w_c^0 = 010 111 001
w_c^1 = 101 000 110
ガーブルテーブル（例）
Row 0: 100101100
Row 1: 011000011
Row 2: 110110110
Row 3: 110100110
評価
- 入力ラベルを連結
- ポインタXORで行選択
- PRG再計算
- XORでマスク除去
- 出力ラベル取得
- フリップ補正して最終値
具体例（3人・AND, κ=2, 入力1=0, 入力2=1）
ここでは n=3, κ=2（部分ラベルは $k$ が2bit＋ポインタ $p$ が1bitで計3bit）として、1ゲート（AND） を計算します。
PRG $F$ の出力長は、出力ラベル長に合わせて 9bit（= $3\times(\kappa+1)$）にします。
記号
-
入力ワイヤ：$a,b$、出力ワイヤ：$c$
-
各プレイヤー：$P_1,P_2,P_3$
-
部分ラベル：$w_{i,j}^v=(k_{i,j}^v, p_{i,j}^v)\in{0,1}^{\kappa}\times{0,1}$（ここでは3bit）
-
合成ポインタ：$p_i^v=\bigoplus_j p_{i,j}^v$
-
合成フリップ：$f_i=\bigoplus_j f_{i,j}$
-
ゲート：$g(x,y)=x\land y$
-
ガーブル行（この例では、出力側に $\oplus f_c$ を入れる形）
e_{v_a,v_b} = w_c^{g(v_a \oplus f_a,\; v_b \oplus f_b)\oplus f_c} \oplus \bigoplus_{j=1}^3 \Big( F(w_{a,j}^{v_a}) \oplus F(w_{b,j}^{v_b}) \Big)
1. Step1（各パーティのローカル生成）
1.1 フリップビット（各自のシェア）
- $f_{a,1}=1,\ f_{a,2}=0,\ f_{a,3}=1 \Rightarrow f_a=1\oplus0\oplus1=0$
- $f_{b,1}=0,\ f_{b,2}=1,\ f_{b,3}=0 \Rightarrow f_b=1$
- $f_{c,1}=1,\ f_{c,2}=1,\ f_{c,3}=0 \Rightarrow f_c=0$
1.2 部分ラベル（例として具体値を固定）
各 $w_{i,j}^v$ は3bit（最後の1bitがポインタ）とします。
-
ワイヤ $a$
- $P_1:\ w_{a,1}^0=010,\ w_{a,1}^1=101$
- $P_2:\ w_{a,2}^0=111,\ w_{a,2}^1=000$
- $P_3:\ w_{a,3}^0=001,\ w_{a,3}^1=010$
-
ワイヤ $b$
- $P_1:\ w_{b,1}^0=011,\ w_{b,1}^1=100$
- $P_2:\ w_{b,2}^0=010,\ w_{b,2}^1=101$
- $P_3:\ w_{b,3}^0=111,\ w_{b,3}^1=000$
-
ワイヤ $c$
- $P_1:\ w_{c,1}^0=011,\ w_{c,1}^1=110$
- $P_2:\ w_{c,2}^0=100,\ w_{c,2}^1=010$
- $P_3:\ w_{c,3}^0=001,\ w_{c,3}^1=111$
よって完全ラベル（連結）は：
- $w_c^0 = 011\ 100\ 001 = 011100001$
- $w_c^1 = 110\ 010\ 111 = 110010111$
1.3 ポインタ（合成値）
ここでは上の3bitの末尾をポインタとすると：
- $p_a^0 = 0\oplus1\oplus1=0,\quad p_a^1=1\oplus0\oplus0=1$
- $p_b^0 = 1\oplus0\oplus1=0,\quad p_b^1=0\oplus1\oplus0=1$
（この例だと偶然 $p_a^v=v,\ p_b^v=v$ になっていますが、一般にはそうとは限りません。）
1.4 PRG出力
例として、ゲート番号は1つだけなので $F(w)$ の出力（9bit）を次のように固定します。$F$は入力が同じなら出力も同じになるランダム関数なので出力値はテキトーです。
-
ワイヤ $a$
- $F(w_{a,1}^0)=001011010,\ F(w_{a,1}^1)=110001101$
- $F(w_{a,2}^0)=101100111,\ F(w_{a,2}^1)=011010001$
- $F(w_{a,3}^0)=000111100,\ F(w_{a,3}^1)=111000010$
-
ワイヤ $b$
- $F(w_{b,1}^0)=010010111,\ F(w_{b,1}^1)=100111000$
- $F(w_{b,2}^0)=001101011,\ F(w_{b,2}^1)=111001110$
- $F(w_{b,3}^0)=110100001,\ F(w_{b,3}^1)=011110101$
2. Step2（MPCで garbled table の4行を作る）
各 $(v_a,v_b)\in{0,1}^2$ について計算します。
2.1 出力側の指数
この例では $f_a=0,\ f_b=1,\ f_c=0$ なので
$$
v_c \oplus f_c = g(v_a\oplus f_a,\ v_b\oplus f_b)\oplus f_c
= (v_a)\land(v_b\oplus 1)
$$
になるので、以下のようなラベルになります。
- $(0,0)$: $0\land 1=0\Rightarrow w_c^0$
- $(0,1)$: $0\land 0=0\Rightarrow w_c^0$
- $(1,0)$: $1\land 1=1\Rightarrow w_c^1$
- $(1,1)$: $1\land 0=0\Rightarrow w_c^0$
2.2 マスク（PRG出力のXOR）
$$
\text{Mask}(v_a,v_b)=\bigoplus_{j=1}^3\left(F(w_{a,j}^{v_a})\oplus F(w_{b,j}^{v_b})\right)
$$
計算結果（9bit）は以下になります：
- $\text{Mask}(0,0)=001011100$
- $\text{Mask}(0,1)=100000010$
- $\text{Mask}(1,0)=111000011$
- $\text{Mask}(1,1)=010011101$
2.3 ガーブル行
上記を以下の式に代入します。
$$
e_{v_a,v_b}=w_c^{v_c \oplus f_c}\oplus \text{Mask}(v_a,v_b)
$$
結果：
- $e_{0,0}=011100001\oplus001011100=010111101$
- $e_{0,1}=011100001\oplus100000010=111100011$
- $e_{1,0}=110010111\oplus111000011=001010100$
- $e_{1,1}=011100001\oplus010011101=001111100$
2.4 テーブルへの配置（行選択用）
行は $(p_a^{v_a},p_b^{v_b})$ の位置に置きます。
この例では $p_a^0=0,p_a^1=1,p_b^0=0,p_b^1=1$ なので、そのまま4象限に対応します。
最終的な garbled table：
- 位置 $(0,0)$: $e_{0,0}=010111101$
- 位置 $(0,1)$: $e_{0,1}=111100011$
- 位置 $(1,0)$: $e_{1,0}=001010100$
- 位置 $(1,1)$: $e_{1,1}=001111100$
3. 評価（入力1=0, 入力2=1）
3.1 入力ラベルのインデックス（flipのせいで「そのまま」ではない）
意味的な入力を $x=0,\ y=1$ とすると、評価で使うラベルの添字は
$$
v_a = x\oplus f_a = 0\oplus 0=0
$$
$$
v_b = y\oplus f_b = 1\oplus 1=0
$$
つまり評価者が持つアクティブラベルは $w_a^{0}, w_b^{0}$ 側です。
3.2 行選択
評価者はラベル内のポインタをXORして
$$
p_a^{v_a}=p_a^{0}=0,\quad p_b^{v_b}=p_b^{0}=0
$$
を得て、位置 $(0,0)$ の行 $e_{0,0}$ を選びます。
3.3 マスクを再計算して打ち消す
評価者は各部分 $w_{a,j}^{0}, w_{b,j}^{0}$ を分解できる（部分ラベル$w_{i,j}^vを持っている）ので、同じように
$$
\text{Mask}(0,0)=001011100
$$
を作れます。
そして
e_{0,0}\oplus \text{Mask}(0,0)
=
010111101\oplus 001011100
=
011100001
となり、出力ラベル
$$
w_c^{0} = 011100001
$$
を得ます。
3.4 出力ビットの復元
得られたのは $w_c^{v_c\oplus f_c}$ です。それぞれのパーティから$f_{c,j}$を受け取り、$f_c$を計算します。
この例では $f_c=0$ なのでそのまま $v_c=0$ です。
実際のAND出力も $0\land 1=0$ なので一致します。
まとめ
ガーブル回路をn人で分散生成したものがBMRプロトコルの肝です。
以下はYao's GCでも同じでしたが、
- 値を計算しているのではなく「ラベルを写している」
- ビット値は最後の瞬間まで一切明示されない
このような性質を持ち計算が可能です。
ちょっと色々計算出てきて分かりづらいのですが、一回理解してしまえば比較的やってることはシンプルなので通しで読んでみると良いと思います。