9
$\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$

1 Answer 1

14
$\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$
3
  • 3
    $\begingroup$ "Nowadays, the most standard method is to use oblivious transfers." Just curious: Is this still true in 2023? $\endgroup$
    – mti
    Nov 10, 2023 at 13:06
  • 3
    $\begingroup$ Good question! This depends on the setting. In the two-party setting yes (unless perhaps if the field is extremely large), but in a setting with a large number of parties, over a large-ish field, then the overhead of OT-based methods becomes too significant, and solutions based on somewhat homomorphic encryption (a la SPDZ) start to dominate again. The exact cutting point depends heavily on the network setting and computational power, of course. $\endgroup$ Nov 13, 2023 at 9:44
  • $\begingroup$ Do you have any references for protocols that generate beaver triples for multiple parties in a larger field? Are they information theoretically secure? $\endgroup$
    – Kolja
    Jan 16 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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