Definition

Multi-party computation (MPC) is a process where multiple parties compute a function together without revealing anything but the output. 🥸

Motivation

We increasingly have high-value information to protect - crypto wallet private keys and data encryption keys (e.g. for sensitive health data) top my list. We need to to be able to compute things with that information without revealing it to anyone.

Traditionally, we protect it by giving it to big companies. We assume they follow rigorous standards such as FIPS 140-2 and spend buckets on special hardware like HSMs. 💵

Even if they do, storing any high-value information in one place introduces a single point of failure. HSMs have known exploits and can fail. Attackers can target upstream code to do damage even without accessing the secrets directly. In many cases, they only need to succeed once to do real damage.

MPC allows us to split high-value information into multiple shares and compute using those shares instead of the original. This mitigates the single-point-of-failure problem and lets us do more distributed computation, securely.

Math

MPC relies on simple properties of polynomials:

$$ \text{Given polynomials } \textbf{g} \text{ and } \textbf{h} \text{ of degree }\textbf{k} \text{, define } \textbf{f} = \textbf{g} + \textbf{h} \text{. Then:} \\ \text{ a) f is also of degree k } \\

\text{ b) } f(x) = g(x) + h(x)

$$

MPC determines polynomials that represent each party’s secret (g and h above), a polynomial f that is their sum, and provides methods to do interesting computation using f.

<aside> 💡 Note: “Interesting computation” can mean a few things, including encryption and signing. I will focus on signing for much of this lesson. MPC encryption is also known as Homomorphic Encryption and worth its own deep dive!

</aside>

For example, if 2 parties want to share an ECDSA key, an MPC library would represent those 2 key shares as g and h with sum f. Commonly the “sign” operation is the value at x=0, so signature by the first key share is g(0), and a signature by the full secret is f(0).

I explain this with an example:

https://excalidraw.com/#room=f291b09632b9120f7461,qb2cRJ84UWk7XOB2FZWkhQ

See Further Reading below for more detail.

Comparisons

<aside> 💡 Note: Shamir secret sharing is technically a specific form of MPC! But its only possible function f is “derive a single secret key”. Often when people refer to “modern MPC” they mean threshold signing schemes (TSS), where f can be “sign”, “encrypt”, “refresh share”, or any operation that can be reduced to a polynomial.

</aside>