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

Question

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?

Answer 1

The answer to your question can be found in a SPDZ follow up paper; it is described as contribution (2) in the intro (top of page 2).

There is a new version of SPDZ called MASCOT that uses OT instead of somewhat homomorphic encryption, and is supposed to be about 200 times faster. So, I would recommend looking at that as well.