1  Beaver’s Triples Explained

In order to mask fixed-point multiplication inputs, we need to use a secure primitive known as Beaver’s triples. These were originally introduced by Beaver (1991) in his paper: Efficient Multiparty Protocols Using Circuit Randomization

1.1 Generating Boolean Beaver’s Triples

The first step in masking the AND operation is to generate Boolean Beaver’s Triples. These are random bits a, b, and c such that c = a \cdot b, where \cdot represents the AND operation. Throughout this tutorial we define a = a_A \oplus a_B, b = b_A \oplus b_B, c = c_A \oplus c_B, and r = r_A \oplus r_B.

1.1.1 Step 1: Generating Inputs

Suppose we have two parties, Alice and Bob. We begin by first generating a random pair (a_{i}, b_{i}) for each party where i corresponds to the party in question. We generate these from the field F_{2}^{2} which simply means that we select two random bits from \{0,1\}.

\begin{array}{ccc} \text{Alice} & {} & \text{Bob} \\ \mathbb{F}_{2}^{2} \overset{\$}{\rightarrow} (a_{A}, b_{A}) & \space & \mathbb{F}_{2}^{2} \overset{\$}{\rightarrow} (a_{B}, b_{B}) \end{array}

Next, Bob and Alice each generate random masking bits r_{A} and r_{B} respectively.

\begin{array}{ccc} \text{Alice} & {} & \text{Bob} \\ \mathbb{F}_{2} \overset{\$}{\rightarrow} r_{A} & \space & \mathbb{F}_{2} \overset{\$}{\rightarrow} r_{B} \end{array}

1.1.2 Step 2: Obtaining Shares of c

After generating the masking bits, Alice and Bob invoke an instance of 2 \choose 1-OT_2 (see Chapter 2), where Alice acts as the sender with inputs (r_{A}, r_{A} \oplus a_{A}), and Bob acts as the receiver with input b_B. Bob obtains b_{B}a_{A} \oplus r_{A}.

Now, Alice and Bob invoke another instance of 2 \choose 1-OT_2. This time, Bob serves as the sender with inputs (r_{B}, r_{B} \oplus a_{B}), and Alice serves as the receiver with input b_A. Consequently, Alice obtains b_{A}a_{B} \oplus r_{B}.

\begin{array}{ccc} \text{Alice} & {} & \text{Bob} \\ \text{Snd } = (r_{A}, r_{A}\oplus a_{A}) & \overset{{2 \choose 1}\text{-OT}_2}{\longrightarrow} & \text{Rcv } = b_{B}a_{A} \oplus r_{A} \\ \text{Rcv } = b_{A}a_{B} \oplus r_{B} & \overset{{2 \choose 1}\text{-OT}_2}{\longleftarrow} & \text{Snd } = (r_{B}, r_{B} \oplus a_{B}) \end{array}

Note that objective is for Alice and Bob to each hold shares of c, denoted as c_A and c_B, respectively, such that their combination satisfies the equation c = ab.

Alice had received b_{A}a_{B} \oplus r_{B} from Bob, and she already has b_{A}a_{A} \oplus r_{A}. She computes b_{A}a_{B} \oplus r_{B} \oplus b_{A}a_{A} \oplus r_{A}, which simplifies to b_{A}a \oplus r. Alice sets c_A = b_{A}a \oplus r.

Similarly, Bob computes b_{B}a_{A} \oplus r_{A} \oplus b_{B}a_{B} \oplus r_{B}, which simplifies to b_{B}a \oplus r. Bob sets c_B = b_{B}a \oplus r.

\begin{array}{ccc} \text{Alice} & & \text{Bob} \\ c_A = b_{A}a \oplus r & \space & c_B = b_{B}a \oplus r \end{array}

It is easy to see that c = c_A \oplus c_B = b_{A}a \oplus r \oplus b_{B}a \oplus r = ab.

Thus, we have shown how Boolean Beaver’s triples are randomly generated such that c = c_A \oplus c_B.

1.2 Application of Random Beaver’s Triples

Now that randomized triples (a_{A}, b_{A}, c_{A}) and (a_{B}, b_{B}, c_{B}) have been generated for Alice and Bob respectively, we can use them cooperatively compute the outpute of some multiplication x \cdot y.

Suppose that Alice has shares of x and y (x_{A}, y_{A}) and Bob has shares (x_{B}, y_{B}).

\begin{array}{ccc} \text{Alice} & {} & \text{Bob} \\ f_{A} = y_{A} \oplus b_{A} & {} & f_{B} = y_{B} \oplus b_{B} \\ e_{A} = x_{A} \oplus a_{A} & {} & e_{B} = x_{B} \oplus a_{B} \\ {} & f = y \oplus b & {} \\ {} & e = x \oplus a & {} \end{array}

Now that functional shares have been computed, we can use those to compute shares z_{A} and z_{B} for collectively obtaining the value of x \cdot y

\begin{array}{ccc} \text{Alice} & {} & \text{Bob} \\ z_{A} = f \cdot a_{A} \oplus e \cdot b_{A} \oplus c_{A} & {} & z_{B} = f \cdot a_{B} \oplus e \cdot b_{B} \oplus c_{B} \\ \end{array}

Note: in the computation above, we approach the binary case of multiplication. Thus, the \cdot operation is equivalent to the \cap operation

We XOR these shares z_{A} and z_{B} together to get the following

\begin{align*} z_{A} \oplus z_{B} &= [(y \oplus b) \cdot (x \oplus a) \oplus (y \oplus b) \cdot a] \oplus [(x \oplus a) \cdot b \oplus c] \\ &= (y \oplus b) (x \oplus a\ ) \oplus xb \oplus ab \oplus c \\ &= (y \oplus b) x \oplus xb \\ &= yx \oplus xb \oplus xb = yx \end{align*}

Beaver, D. 1991. “Efficient Multiparty Protocols Using Circuit Randomization.” Advances in Cryptology. https://link.springer.com/chapter/10.1007/3-540-46766-1_34.