How to multiply a boolean share with an arithmetic share

Question

The problem is to multiply a boolean share with an arithmetic share, a commonly used technique in functions such as multiplexing. In my opinion, a straightforward approach would be to convert the boolean share to an arithmetic share and then proceed with the multiplication of the two arithmetic shares, followed by a truncation step (although I can't recall where I read this idea). However, I am curious if there might be a more efficient method available, as I question the necessity of the truncation step.

Answer 1

In the honest-but-curious setting, you can do that using a single oblivious transfer.

Since you indicated in the comments that you're interested in the two-party setting, here is a solution: let Alice and Bob be two parties with binary shares $(b_A, b_B)$ of a bit $b \in \mathbb{F}_2$ and arithmetic shares $(x_A, x_B)$ of a value $x\in \mathbb{F}$. Their goal is to get additive shares of $y = b\cdot x$ over $\mathbb{F}$.

There is a folklore simple way to do that using oblivious transfer. Here is the idea: you can "arithmetize" $b_A \oplus b_B$ as $b_A + b_B - 2\cdot b_Ab_B$ over an arbitrary larger field (in fact, it works over the integers). Written this way, the equation becomes

$y = (b_A + b_B + 2b_Ab_B)\cdot (x_A+x_B) = b_Ax_A + b_Bx_B + b_A\cdot (1 + 2b_B)x_B$

In this equation, $b_Ax_A$ is known to Alice, and $b_Bx_B$ is know to Bob, so it's easy for the parties to just add these quantities to their share locally. Therefore, the problem reduces to letting Alice and Bob get additive shares of $b_A\cdot (1+2b_B)x_B$. This is easily achieved using a single oblivious transfer:

• Bob samples a random element $r\gets \mathbb{F}$.
• Bob plays the role of the sender in an oblivious transfer protocol, with inputs $(-r, (1+2b_B)x_B-r)$.
• Alice plays the role of the receiver, with selection bit $b_A$.
• At the end of the OT, Alice gets an output $z_A$. Bob sets his output $z_B$ to be $r$.

In the above protocol, if $b_A = 0$, Alice gets $z_A = -r$, hence $z_A + z_B = r-r = 0 = 0\cdot (1+2b_B)x_B$. If $b_A = 1$, Alice gets $z_A = (1+2b_B)x_B-r$, hence $z_A+z_B = (1+2b_B)x_B-r + r = 1\cdot(1+2b_B)x_B$.

In the end, Alice outputs $z_A + b_Ax_A$ and Bob outputs $z_B + b_Bx_B$; they form additive shares over $\mathbb{F}$ of $y = b\cdot x$, as intended.