2
$\begingroup$

For a lot of cryptographic applications, multi-party protocols are used. The idea is to create shares of a key/secret and give them to multiple parties. My question is: Do all parties have to participate in the multi-party protocol or do protocols exist, that only need e.g. >51% of the shares to compute correctly?

$\endgroup$

2 Answers 2

3
$\begingroup$

Sure, if for example, we use $k$ of $n$ Shamir secret sharing then only k participants are needed to reconstruct the secret or do something with the secret(even without revealing it).

If a missing participant has crucial information then you may need that information regardless if you are doing Secure Multi-party computation or if everyone is honest and all information is shared.

$\endgroup$
4
$\begingroup$

Generally, MPC protocols have two main parameters: the number of participants $n$, and the amount of corrupt parties you wish to tolerate, $t$. It is typically the case that, as you mention, protocols work by secret-sharing data in a way that at most $t$ participants cannot recover it, but $t+1$ parties can. As a minimum, you will need $t+1$ parties for your computation, since otherwise a set of $t$ corrupted parties could finish the computation on their own and learn the results/secrets.

Some protocols (known as dishonest majority protocols) are designed with $t=n-1$ in mind, which means that you cannot do any better than having all parties at all times. However, some other protocols (in the honest majority setting) consider lower thresholds such as $t<n/2$ or $t<n/3$. This is useful since this can lead to more efficient protocols and stronger notions of indistinguishability (e.g. information-theoretic vs computational security), at the expense of tolerating less corruptions. In these cases you can consider optimizations where, for example, all $n$ parties actively participate in the protocol for some time (for instance, in a preprocessing phase, generating multiplication triples—in case you're familiar with the concept), and then only $t+1$ can remain for the rest of the execution.

$\endgroup$

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.