# SPDZ protocol: how expensive is it to generate the multiplicative triples?

I am currently reading the full version of the SPDZ protocol. I understand that the online phase does multiplication with computational and communication complexity $O(n)$ by using Beaver's multiplicative triples as explained $\Pi_{Online}$ (Fig 1, page 5). These triples are numbers $a$,$b$ and $c$ such that $ab=c$, where $a$ and $b$ are random. These triples are generated in the preprocessing phase, as explained in protocol $\Pi_{Prep}$ (Fig 7, page 13) which depends on protocol $\Pi_{Reshare}$ (Fig 4, page 12), to decrypt the value of $c$ and distribute its shares among the players.

$\Pi_{Reshare}$ uses $F_{KeyGenDec}$ to decrypt $e_{m+f}$ to obtain $m+f$. $F_x$ in the paper represents some ideal functionality $x$, and typically there is a protocol, $\Pi_x$ that implements that functionality. In Definition 1, on page 10, they mention that such an implementation $\Pi_{KeyGenDec}$ is required for the cryptosystem. However, I was not able to find the implementation of this KeyGenDec functionality in the paper (including appendices).

Where could I find an implementation of KeyGenDec? How long does this protocol take to run? Is this the bottleneck in the time required to generate the triples?

• Note that KeygenDec consists of two parts: (1) distributed decryption (used when creating triples), which is described on p15 of the original paper, and (2) distributed key generation, which is used only in the setup phase and described in the follow-up paper. – pscholl Jul 10 '16 at 16:01