5
$\begingroup$

So to speed up the function evaluation we use beaver trick, to generate raw data in the offline phase and use them in the online phase to get the output share for the multiplication gate. So what are the methods to generate these raw data i.e. multiplication triples ?

$\endgroup$
6
$\begingroup$

Nowadays, the most standard method is to use oblivious transfers. Oblivious transfer involve a sender with two messages $(m_0,m_1)$ and a receiver with a selection bit $b$. At the end of the protocol, the receiver learns $m_b$ (and gets no information about $m_{1-b}$) while the sender gets no information about $b$.

Suppose Alice and Bob want to generate a random Beaver triple over $\mathbb{F}_2$ (that is, a Beaver triple of shared bits). Alice picks $(x_A,y_A)$ at random from $(\mathbb{F}_2)^2$ and Bob picks $(x_B,y_B)$ at random from $(\mathbb{F}_2)^2$. Alice now picks a random bit $r_A$ and acts as sender in an oblivious transfer with the following pair of inputs: $(r_A, x_A \oplus r_A)$ ($\oplus$ denotes the xor). Bob uses $y_B$ as selection bit. If $y_B$ is $0$, Bob learns $r_A$; else, he learns $ x_A \oplus r_A$. Therefore, Bob learns $x_Ay_B \oplus r_A$.

The players now do the same thing in the other direction with a random bit $r_B$ and the bits $(x_B, y_A)$, so that Alice learns $x_By_A \oplus r_B$. Alice computes $z_A \gets r_A \oplus x_Ay_A \oplus x_By_A \oplus r_B$ and Bob computes $z_B \gets r_B \oplus x_By_B \oplus x_Ay_B \oplus r_A$. You can easily check that $z_A \oplus z_B = (x_A \oplus x_B)\cdot(y_A\oplus y_B)$, therefore $(x_A,x_B), (y_A,y_B)$, and $(z_A,z_B)$ form shares of a Beaver triple over $\mathbb{F}_2$.

Oblivious transfers require (expensive) public key primitives; the most common construction are based on the Decisional Diffie-Hellman assumption (like the ElGamal cryptosystem). However, it was shown some years ago that one can generate an arbitrary number of oblivious transfers, starting from a constant number of OT (say, 80) and "extending" them using only very cheap primitives. Therefore, players can generate arbitrarily many Beaver triples while using only a constant number of public key operations, and then only cheap primitives (hash functions). This is the reason why OT is nowadays seen as the best choice to construct Beaver triples. Other classical primitives used to generate Beaver triples include homomorphic encryption. The advantage, which might make it relevant in some cases, is that it allows to generate Beaver triples over large order fields without having to rely on the bit decomposition of one of the inputs (generating a single Beaver triple on a large order field $\mathbb{F}$ requires $O(\log |\mathbb{F}|)$ oblivious transfers in general, although there are methods to improve that).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.