Multi-Party Computation

Theoretical Background

This section is intended to give some theoretical background on MPC for those seeking to get a deeper understanding of the underlying technology of Sodot's products.

Understanding this section is not needed to use the products safely and provided for advanced readers who wish to better understand the foundations of the technology.

Historical Background

Communication Security

Primarily throughout history, cryptography has been focused on the goal of securing communication. That is, assuming two parties, typically referred to as Alice and Bob, cryptography sought to secure the communication between them such that no malicious party, typically referred to as Eve can:

• Infer full or even partial information about the contents of Alice and Bob’s messages. This threat is mitigated by means of Encryption. Both Alice and Bob agree¹ on some encryption keys² and subsequently encrypt all messages prior to communicating them over untrusted channels.
• Modify messages Alice (or Bob) sends to Bob (or Alice). This threat is mitigated by employing Message Authentication Codes (MACs, one commonly known example is the hash-based HMAC construction).
• Impersonate Alice or Bob. This threat is mitigated by means of Digital Signatures.

MPC Background

Since the 1980’s, cryptography has been found useful for a wide variety of other purposes, amongst which is the purpose of securing general distributed computation, typically referred to as Multi-Party Computation (MPC). Up until the early 2000's MPC research was focused primarily on theoretical aspects, with little to no practical implementations. Starting from the early 2000's, MPC research has seen a surge in practical implementations, with the first practical MPC protocols being implemented in 2008. Interest in MPC has been growing ever since, with MPC being used in a wide variety of applications, such as secure auctions, secure voting, secure cloud computing, and threshold digital signatures used for securing digital assets.

What is Multi-Party Computation (MPC)?

We start with an example, consider a set of three persons, each holding a private number representing their salary. The persons are interested in learning who has the highest salary. This comes with a few caveats:

• The persons are not interested in revealing their own salary, but only in learning the result of the comparison.
• They only wish to tell who has the highest salary, and not the actual value of the highest salary.
• They do not want to learn who has the second-highest salary and a secure protocol must not disclose this information.
• The persons cannot provide input that depends, in any way, on another person's inputs.

warning

Notice that MPC does not provide any means to verify that the parties' inputs are correct! In our example, the persons can cheat and provide false inputs that are not their actual salaries.

A secure MPC protocol must meet all these demands.

MPC Definition

We provide a (simplistic) definition of MPC in a slightly more formal manner in what follows. In the context of MPC, we consider a set of $n$ mistrusting parties, denoted $P_1,\ldots,P_n$ that wish to collaboratively compute some function $\mathcal{F}$ securely. The function $\mathcal{F}$ takes $n$ inputs, where party $P_i$ provides a private input $x_i$. The parties share pairwise secure channels. That is, each pair of parties $P_i$ and $P_j$ can communicate over a dedicated channel that is both secret (i.e. no other party can read its contents) and authenticated (i.e. no other party can impersonate one of the other parties).

In our simplified setting (as general, formal, academic definitions can be quite complex), we consider MPC protocols to work in the following way:

1. The protocols begin with each party $P_i$ holding its private input $x_i$ and computing some initial, local state.
2. The protocol proceeds in rounds. Each round starts with each party making some local computation.
3. At the end of the local computation each party $P_i$ sends a message to each other party $P_j$ over the secure channel.
4. Upon receiving all messages from all other parties, each party $P_i$ updates its local state and proceeds to the next round.
5. Once all rounds have accomplished, each party outputs some value $y_i$.

Let $\Pi$ be some protocol. We say that $\Pi$ securely computes the function $\mathcal{F}$ if it satisfies the following properties:

Correctness Property

The correctness property states that parties output correct values from the protocol. That is, let $y_i$ denote the output of each party $P_i$ and let $x_i$ be its private input. The protocol satisfies the correctness property if for each party $P_i$ it holds that $\mathcal{F}(x_1,\ldots,x_n)=y_i$.

Unfortunately, some parties may be malicious and deviate from the protocol arbitrarily. This can be done for various reasons such as trying to learn more information than they should, or trying to disrupt the computation so that it leads to incorrect or biased results. In terms of security, we consider some subset $T$ of the parties to be malicious. We also refer to these parties as corrupted and think of these parties as following some adversarial strategy to disrupt the computation. This leads us to the second property of secure MPC protocols:

Privacy Property

We say that protocol $\Pi$ is private if for every such adversarial strategy it can be shown that the corrupted parties learn nothing more than what they would have learned if they had followed the protocol honestly. In other words, corrupted parties can deviate arbitrarily from the protocol, but they should not learn more information than what they should have learned from the protocol or bias its outcome in some adversarial way.

In summary, for a protocol to be considered secure, it must satisfy both the correctness and privacy properties.

Further Reading

An interested reader can find more information about MPC in the following resources:

• Wikipedia
• A Survey on Secure Multi-Party Computation
• Oded Goldreich's Book on Foundations of Cryptography (Volume 1,Volume 2)

Footnotes

1. Agreement on encryption keys is facilitated in the modern internet via public-key infrastructure (PKI) such as the one laying the foundation for TLS. ↩

2. Encryption schemes can be either symmetric (e.g. AES) or asymmetric (e.g. RSA). ↩