BMR

Presentation: https://www.youtube.com/watch?v=8fvH4GM_A5k

Created by Beaver, Micali, and Rogaway in 1990, the BMR protocol is an multi-party computation (MPC) for boolean circuits for greater than 2 parties. It extends upon the core concept of Yao’s Garbled Circuits with its garbled tables and also carries a constant communication cost similar to Yao’s. Note that explanations online on the specifics of the protocol vary due to the more conceptual nature of the original paper, so we will focus mostly on the explanation outlined here. It is heavily recommended you read Yao's Garbled Circuits as a prerequisite.

Definitions

Let’s start with the basics: the definitions.

A wire sublabel for a given value, gate, and party:

wi,jb=(ki,jb,pi,jb)R{0,1}κ+1w^{b}_{i,j} = \left( k^{b}_{i,j}, p^{b}_{i,j} \right) \in_{\mathbb{R}} \{0,1\}^{\kappa+1}

ww = the wire bb = the true value of the wire (0 or 1) ii = the unique wire ID jj = the unique party ID kk = the key to a given value of the wire (length κ\kappa) pp = the pointer bit of the given value of the wire (length 1)

Thus, the wire sublabel for a gate by a given party is a set of κ+1\kappa + 1 random bits, κ\kappa of which are the key bits corresponding to a value and 1 of which is the pointer bit used later for shuffling the encrypted tables. Additionally note that the final wire label wib= wi,1b wi,2b wi,n1b wi,nbw_i^b = w_{i,1}^b || w_{i,2}^b || \cdots || w_{i,n-1}^b || w_{i,n}^b, where 1 to nn denote the parties.

More on Pointer Bits

Let’s expand some more on pointer bits. Each party holds a pointer bit share for a wire’s input value. Additionally, all parties’ pointer bit shares are XOR-ed together should create the final desired pointer bit for that wire input value. AKA pa0=pa,10pa,20pa,30pa,n0p_a^0 = p_{a,1}^0 \oplus p_{a,2}^0 \oplus p_{a,3}^0 \oplus \dots \oplus p_{a,n}^0 where pa0p_a^0 is the pointer bit for input value 0 on wire aa and 1 to nn are the parties. Subsequently, the pointer bit for the opposite input value should be the opposite bit (AKA pa1=1pa0p_a^1 = 1- p_a^0 or pa1pa0=1p_a^1 \oplus p_a^0 = 1)

The pointer bits for a given gate with 3 wires a, b, and c

Each party’s underlying-MPC input per wire ww:

Ii,j=(F(i,wi,j0),F(i,wi,j1),pi,j0,fi,j)I_{i,j} = \left( F(i, w_{i,j}^{0}), F(i, w_{i,j}^{1}), p_{i,j}^{0}, f_{i,j} \right)

II = the gate input FF = A pseudo-random function (PRF) defined as the following:

F:id,{0,1}κ+1{0,1}n(κ+1)F : id, \{0,1\}^{\kappa+1} \mapsto \{0,1\}^{n \cdot (\kappa+1)}

ff = the flip bit

For each gate, the input for each party will be the two PRFs of the gate index with the sublabels corresponding to input of 0 or 1, the pointer bit of the true input value, and the flip bit (more on this later).

Naively encrypted row of table:

eva,vb=wcvcj=1..n(F(i,wa,jva)F(i,wb,jvb))e_{v_a, v_b} = w^{v_c}_{c} \bigoplus\limits_{j=1..n} \left( F(i, w^{v_a}_{a,j}) \oplus F(i, w^{v_b}_{b,j}) \right)

eva,vbe_{v_a, v_b} = encrypted row on input values vav_a and vbv_b vav_a = value of input wire aa vbv_b = value of input wire bb vcv_c = value of output wire cc

Note that the first subscript of the wires ww also indicate the wire ID, where aa and bb refer to the input wires of a given gate and cc refers to the output wire. Therefore, wcvcw_c^{v_c} is the output label of wire cc of true output value vcv_c, while wa,jvaw_{a,j}^{v_a} is the sublabel for party jj of input wire aa with the true value vav_a. This encrypted row is a naive implementation not including the use of flip bits to further secure the encryption.

Creating the Garbled Table Naively

Let’s take another look at the formula to naively creating the encrypted rows of our gate tables from the previous section:

eva,vb=wcvcj=1..n(F(i,wa,jva)F(i,wb,jvb))e_{v_a, v_b} = w^{v_c}_{c} \bigoplus\limits_{j=1..n} \left( F(i, w^{v_a}_{a,j}) \oplus F(i, w^{v_b}_{b,j}) \right)

With the 4 possible permutations of vav_a and vbv_b , we get the 4 rows as follows for an AND gate:

e0,0=wc0[F(i,wa,10)F(i,wb,10)][F(i,wa,n0)F(i,wb,n0)]e0,1=wc0[F(i,wa,10)F(i,wb,11)][F(i,wa,n0)F(i,wb,n1)]e1,0=wc0[F(i,wa,11)F(i,wb,10)][F(i,wa,n1)F(i,wb,n0)]e1,1=wc1[F(i,wa,11)F(i,wb,11)][F(i,wa,n1)F(i,wb,n1)]\begin{aligned} e_{0,0} &= w_c^{0} \oplus \left[ F(i, w_{a,1}^{0}) \oplus F(i, w_{b,1}^{0}) \right] \oplus \dots \oplus \left[ F(i, w_{a,n}^{0}) \oplus F(i, w_{b,n}^{0}) \right] \\ e_{0,1} &= w_c^{0} \oplus \left[ F(i, w_{a,1}^{0}) \oplus F(i, w_{b,1}^{1}) \right] \oplus \dots \oplus \left[ F(i, w_{a,n}^{0}) \oplus F(i, w_{b,n}^{1}) \right] \\ e_{1,0} &= w_c^{0} \oplus \left[ F(i, w_{a,1}^{1}) \oplus F(i, w_{b,1}^{0}) \right] \oplus \dots \oplus \left[ F(i, w_{a,n}^{1}) \oplus F(i, w_{b,n}^{0}) \right] \\ e_{1,1} &= w_c^{1} \oplus \left[ F(i, w_{a,1}^{1}) \oplus F(i, w_{b,1}^{1}) \right] \oplus \dots \oplus \left[ F(i, w_{a,n}^{1}) \oplus F(i, w_{b,n}^{1}) \right] \end{aligned}

Note that the output labels are defined as such as well:

wc0=wc,10wc,n0pc0wc1=wc,11wc,n1pc1\begin{aligned} w_c^{0} &= w_{c,1}^{0} \parallel \dots \parallel w_{c,n}^{0} \parallel p_c^{0} \\ w_c^{1} &= w_{c,1}^{1} \parallel \dots \parallel w_{c,n}^{1} \parallel p_c^{1} \end{aligned}

Similar to Yao’s, we now “garble” the table. For example, if pa0=1p_a^0 = 1, pb1=0p_b^1 = 0 meaning pa1=0p_a^1 = 0, pb0=1p_b^0 = 1, our table is shuffled as so:

Shuffling of encrypted table

Now, this is the naive way to create a garbled encrypted table; however, a major flaw that exposes the input values to the evaluator can occur. To prevent this information from being leaked, we use “flip bits.”

TODO(ashjeong): Add explanation of a possible attack for this naive case.

Creating the Garbled Table Securely with Flip Bits

Flip bits obscure the true input values for the evaluator. Similar to pointer bits, each party creates their own flip bit share for each wire such that for a given wire, the total flip bit is or all flip bit shares XOR-ed together. Since wire labels and PRF functions result in random strings that are consistent across a binary value, switching the correlations of said labels to their opposite value is fine. Therefore, we instead encrypt rows of the encrypted table while obscuring input values with flip bits as shown below:

eva,vb=wcvcfcj=1..n(F(i,wa,jvafa)F(i,wb,jvbfb))e_{v_a, v_b} = w_c^{v_c \oplus f_c} \bigoplus\limits_{j=1..n} \left( F(i, w_{a,j}^{v_a \oplus f_a}) \oplus F(i, w_{b,j}^{v_b \oplus f_b}) \right) \\

Ex. fa=0f_a = 0, fb=1f_b = 1, fc=1f_c = 1 for an AND gate:

e0,0=wc01[F(i,wa,100)F(i,wb,101)][F(i,wa,n00)F(i,wb,n01)]e0,1=wc01[F(i,wa,100)F(i,wb,111)][F(i,wa,n00)F(i,wb,n11)]e1,0=wc01[F(i,wa,110)F(i,wb,101)][F(i,wa,n10)F(i,wb,n01)]e1,1=wc11[F(i,wa,110)F(i,wb,111)][F(i,wa,n10)F(i,wb,n11)]\begin{aligned} e_{0,0} &= w_c^{0 \oplus 1} \oplus \left[ F(i, w_{a,1}^{0 \oplus 0}) \oplus F(i, w_{b,1}^{0 \oplus 1}) \right] \oplus \dots \oplus \left[ F(i, w_{a,n}^{0 \oplus 0}) \oplus F(i, w_{b,n}^{0 \oplus 1}) \right] \\ e_{0,1} &= w_c^{0 \oplus 1} \oplus \left[ F(i, w_{a,1}^{0 \oplus 0}) \oplus F(i, w_{b,1}^{1 \oplus 1}) \right] \oplus \dots \oplus \left[ F(i, w_{a,n}^{0 \oplus 0}) \oplus F(i, w_{b,n}^{1 \oplus 1}) \right] \\ e_{1,0} &= w_c^{0 \oplus 1} \oplus \left[ F(i, w_{a,1}^{1 \oplus 0}) \oplus F(i, w_{b,1}^{0 \oplus 1}) \right] \oplus \dots \oplus \left[ F(i, w_{a,n}^{1 \oplus 0}) \oplus F(i, w_{b,n}^{0 \oplus 1}) \right] \\ e_{1,1} &= w_c^{1 \oplus 1} \oplus \left[ F(i, w_{a,1}^{1 \oplus 0}) \oplus F(i, w_{b,1}^{1 \oplus 1}) \right] \oplus \dots \oplus \left[ F(i, w_{a,n}^{1 \oplus 0}) \oplus F(i, w_{b,n}^{1 \oplus 1}) \right] \end{aligned}

If the flip bit of a wire is 0 such as for wire a shown above, the wire sublabels refer to their corresponding input value (e.g. wa,11w_{a,1}^1 refers to input value 1). Else, if the flip bit is 1 as in wire bb above, the wire sublabel refers to the opposite input value (e.g. wb,10w_{b,1}^0 refers to input value 1).

Flip bits introduce more constrained chaos to prevent values from being exposed. Only 4 possible label permutations of each wire aa, bb, and cc for its 4 possibilities of input values exist when not using flip bits, yet with its inclusion, the total number of label permutations jumps to 32. Take a look below showing off all possible label permutations for a single input case of a AND gate where the inputs are 1.

AND gate possibilities for (1,1) -> 1

BMR Protocol Summary

All Parties:

  1. Create their own keys for all possible wires values

  2. Create their own pointer bit shares for each wire value (1 for each wire since the other can be simply calculated)

  3. Create their own flip bit shares for each wire

For n-MPC:

  1. Receive parties’s private input bits

  2. Receive MPC inputs of each party Ii,jI_{i,j}

  3. For each gate

    1. Compute total flip bits ff for each wire

    2. Compute total pointer bits pp for each wire value

    3. Create the garbled table

One party who is set to be the evaluator:

  1. Receive the garbled tables and active wire labels

  2. Evaluate garbled circuit re-creating the garbled inputs themselves

References

Written by Ashley Jeong from A41

Last updated