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 the Sodot MPC SDK.

Understanding this section is not needed to use the SDK safely.

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 partial information about the contents of Alice and Bob’s messages. This threat is mitigated by means of Encryption.
• Modify messages Alice (or Bob) sends so that Bob (or Alice) will interpret the contents in an unintended manner. This threat is mitigated by employing Message Authentication Codes (MACs).
• Impersonate Alice or Bob. This threat is mitigated by means of Digital Signatures.

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. In this setting a set of mistrusting parties wish to collaboratively compute some function $\mathcal{F}$ securely. The previous sentence is pivotal for the rest of the section, so let’s parse it word by word in a didactic ordering,

• “Function” When we say that some function is being computed it means first and foremost that all parties know exactly what this function is. We will now give an example of such a function which will accompany us for the rest of this section. Think of an averaging function, that is, the function $\mathcal{F}$ takes some numbers and outputs these numbers’ averages. This function takes as input multiple numbers $x_1, x_2, \ldots,x_n$ and outputs their average. The parties, therefore, need not only know the function, but also know which party is assigned to provide which input. For example, if the averaging function takes ten numbers and there are ten parties, we will, in our example, assume that each party provides a single input number. In fact, to give it an even more realistic setting, think of a set of ten colleagues who wish to learn the average of their salaries. In general, the function may assign different outputs to different parties so that each party will learn only its designated output of the function $\mathcal{F}$, and hopefully as we will see later, nothing else.
• “Parties” In our setting the parties can be thought of as entities between which some secure communication channel exists through which parties can communicate. In the case where more than two parties exist, we assume that such a channel exists pairwise so that each pair of parties has its own secure dedicated channel. Typically, this can be thought of as an encrypted and authenticated communication channel over the internet. In other words, using these channels we can simply assume that whenever party $A$ sends a message to party $B$, only party $B$ will receive the message. Similarly, whenever party $B$ receives a message over its dedicated channel with party $A$, it can be assured that this message originated from party $A$ indeed, and no other middleman has impersonated party $A$.
• “Collaboratively” The parties could have, theoretically, computed this function by themselves. However, there is some reason for which they decide to take part in the computation process in a way that involves other parties which may not be trusted. Therefore, there are two possible reasons for the parties to gather up and work together. The first is that they want to work together in order to distribute the output of their computation between other parties. As we will see later in this document, the distributed key generation process matches this use case. Another trivial use case would be that simply no subset of the parties holds sufficient information from which the output of the function may be computed. As we will see later in this document, the signing process matches this use case. In any way, the parties have their own reasons to decide to work together, but they are doing so at their own discretion.
• “Compute” The parties wish to jointly evaluate the function $\mathcal{F}$, that is, each party will learn its designated output of the function $\mathcal{F}$. While $\mathcal{F}$ may be described simply within a few lines of one programming language or another, the computation which the parties will conduct refers not only to the logic of the computation, but to an overall protocol that takes place between the parties, which, in order to be accomplished successfully, must be followed by all parties. As we will see later, if some parties decide to deviate from the protocol we will be interested to detect such cases and protect against them.
• “Mistrusting” means that the parties which take part in the computation do not necessarily trust each other. They may not know each other at all! They may possibly know each other but simply are worried that some of them might turn against the rest of the parties, or are simply worried that some of the parties’ phones/computers will be hacked by some malicious hacker that will impersonate these parties. In any case, the parties want to ensure that in any of such cases, their information and results will remain safe.
• “Securely” The parties have joined the process of computing the output of some function, typically they have provided some sensitive information which only they know while, as we have seen, the other parties may not be trusted. Obviously, if the mistrusted parties could have learned some information about this sensitive information, the parties wouldn’t provide it. Therefore, there must be some guarantee about what malicious parties can learn from this interaction. Hopefully, we wish they could have learned nothing, even if they deviate from the prescribed protocol used to evaluate $\mathcal{F}$. In some cases, an MPC protocol makes assumptions about what kinds of attacks malicious parties might carry, or how many malicious parties may exist, but we will leave these intricacies out of the scope of this section.

An easy approach to solving the aforementioned goal of MPC, is to use a trusted, centralized party, to which all parties will send their sensitive inputs and information. This party will take all the inputs, perform the computation and send each party its designated output. The utopian existence of such a party is unlikely. History proves, time and time again, that such a party is well positioned to be eventually corrupted, eliminating all prior trust that was put into it. Consequently, MPC can be simply thought of as an attempt to simulate the existence of a trusted party, without trusting any party.

In our SDK, MPC will be used as a cornerstone to realize the functionality of digital signatures which can be used to sign any piece of digital information.