Is there any relation between secure multiparty computation and threshold cryptosystem ?


2 Answers 2


Yes and no.

A threshold cryptosystem means the decryption key can be split into $n$ shares such that only $t\leq n$ are required to recover it. That property in isolation is not useful for multiparty computation.

However when you combine a threshold cryptosystem with one that is at least partially homomorphic (meaning you can do some operation, like addition or multiplication, under encryption), then the two properties combined can make a useful basis for multiparty computation.

The model is that each party encrypts their inputs, you use the homomorphic property to do some computation on the ciphertexts while they are still encrypted, and the threshold property enforces that only the final value is decrypted assuming less than $t$ dishonest key share holders. Without the threshold (or at least a distributed $n$-out-of-$n$ key), the keyholder could simply decrypt the inputs and learn everyone's value.

The most famous paper on this is "Multiparty Computation from Threshold Homomorphic Encryption." This approach is used in lots of papers. A different approach in the same model is "Mix and Match: Secure Function Evaluation via Ciphertexts." It is less used (I think maybe a bit overlooked) but you can do interesting things with it.


Yes. Threshold cryptosystems come under the secure multiparty computation branch of cryptography.

Essentially, threshold cryptosystems require multiple parties to cooperate in order to decrypt a ciphertext.

Secure multiparty computation is a field of study involving cryptosystems that require more than one party to compute an operation. As such, threshold cryptosystems fall into this field.

  • $\begingroup$ but any formal study of the relation is made ? any references? $\endgroup$
    – sashank
    Jul 20, 2012 at 14:56
  • $\begingroup$ There's no formal study of the relation, because that's like asking for a study on the relationship between basketball and sports. Threshold cryptosystems are a type of secure multiparty computation. $\endgroup$
    – Polynomial
    Jul 20, 2012 at 15:30

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.