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:
= the wire = the true value of the wire (0 or 1) = the unique wire ID = the unique party ID = the key to a given value of the wire (length ) = 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 random bits, 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 , where 1 to 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 where is the pointer bit for input value 0 on wire and 1 to are the parties. Subsequently, the pointer bit for the opposite input value should be the opposite bit (AKA or )
Each party’s underlying-MPC input per wire :
= the gate input = A pseudo-random function (PRF) defined as the following:
= 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:
= encrypted row on input values and = value of input wire = value of input wire = value of output wire
Note that the first subscript of the wires also indicate the wire ID, where and refer to the input wires of a given gate and refers to the output wire. Therefore, is the output label of wire of true output value , while is the sublabel for party of input wire with the true value . 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:
With the 4 possible permutations of and , we get the 4 rows as follows for an AND gate:
Note that the output labels are defined as such as well:
Similar to Yao’s, we now “garble” the table. For example, if , meaning , , our table is shuffled as so:
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:
Ex. , , for an AND gate:
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. refers to input value 1). Else, if the flip bit is 1 as in wire above, the wire sublabel refers to the opposite input value (e.g. 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 , , and 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.

BMR Protocol Summary
All Parties:
Create their own keys for all possible wires values
Create their own pointer bit shares for each wire value (1 for each wire since the other can be simply calculated)
Create their own flip bit shares for each wire
For n-MPC:
Receive parties’s private input bits
Receive MPC inputs of each party
For each gate
Compute total flip bits for each wire
Compute total pointer bits for each wire value
Create the garbled table
One party who is set to be the evaluator:
Receive the garbled tables and active wire labels
Evaluate garbled circuit re-creating the garbled inputs themselves
References
Written by Ashley Jeong from A41
Last updated