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?

  • 2
    $\begingroup$ 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. $\endgroup$
    – pscholl
    Commented Jul 10, 2016 at 16:01

1 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.


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.