I am studying the FAEST digital signature protocol (quantum-safe) which requires me to learn concepts like MPC, Zero-Knowledge, and Digital Signatures. So here are my notes and explanation for what I have studied and learnt about Multi-Party Computation (MPC).
Secure Average Computation
Let’s say that you work in a company, and you and your colleagues are curious about the average salary of your department. Now, not everyone would be comfortable sharing their salaries—sounds fair enough. But even they are curious about the average. Sounds like a Martin Gardner puzzle, right? Pretty sure there is a similar problem in his puzzle collection. Either way, how do we solve this problem? Let’s directly jump into the math.
Let’s say that there are $N$ employees. Let’s say that the $k$th employee has the salary $S_k \in \mathbb{F}_p$, where $\mathbb{F}_p$ is a prime-field. Now, the employee will sample $N - 1$ numbers from the same prime-field: $$S_k^1, \cdots S_k^{N-1}$$, then we can write: $$S_k^N = S_k - \sum_{i=1}^{N - 1} S_k^i$$. With this, we have divided the salary into $N$ shares, each uniformly sampled from the working prime field. Now the employee will share the 2nd share with the 2nd employee, the 3rd share with the third one, and so on. Yes, the $k$th share will not be shared with anyone and be kept with the employee themselves. Others will also do a similar thing. Then the $k$th employee will have the shares $$S_2^k, \cdots S_N^k$$and obviously, the share $S_k^k$ which they generated themselves. Now, they will perform a local accumulation:$$P_k = \sum_{i=1}^{N} S_i^k$$and make the value public among the interested peers. Others will do the same. Then, they can just evaluate these values in the plain, without any privacy concerns, to get the total sum:$$S = \sum_{i=1}^{N} P_i$$, then division by $N$ to get the average can again be performed in the plain.
This example should give you a pretty solid idea of the field. This and FHE, on which I have written quite a few blogs and quick posts, lie in the field of Secure Computing, where a function can be evaluated ensuring the privacy of the inputs to the function. Now, one might ask, why MPC if we already have FHE, and vice-versa? As mentioned a lot in my previous posts, FHE works well with functions that can be expressed in terms of polynomial-friendly operations, but in MPC, if the protocol is designed cleverly enough, one can, in principle, securely compute any function. But FHE has its advantages over MPC too, the major advantage being that everything is centralized in FHE, so there are no networking expenses and no problem of establishing the security of multiple nodes.
Corrupted Parties
This part is my direct interpretation of Section 2.1 of the paper “Secure Multi-Party Computation (MPC)” by Yehuda Lindell, which is a pretty standard source to learn MPC.
We obviously have to consider a setting where an adversary controls some parties and wants to extract private information out of the secure system we are trying to establish. Parties under the control of this adversary are called corrupted parties and follow the adversary’s instructions. If the designed protocol is secure, then it should be resistant to any adversarial attack.
Now, let’s look at some key properties associated with a secure MPC protocol:
Privacy: The only information that parties should learn about the function inputs is what can be derived from the output itself. For instance, in the private contact discovery problem, if the output contains a phone number, then the parties should only know the fact that the given phone number is saved in each of the devices, and nothing else. Another example: in an auction, only the highest bid is announced, which inevitably leaks the fact that all the other inputs (bids) must be smaller than the announced highest bid.
Correctness: A pretty obvious property; there is no point in computing the wrong value privately, or even in plain.
Independence of Inputs: This property implies that the parties must choose inputs before the protocol starts. This is required so that corrupted parties cannot wait and see, then pick smart inputs. Now, this will not necessarily sacrifice the privacy provided by the protocol, but can have a huge effect in win or lose situations like sealed auctions, where the bids are kept private. Now, let’s say that there exists a somewhat homomorphic scheme, which supports $\text{Enc}(x) \cdot \text{Enc}(1) = \text{Enc}(x + 1)$. Now let’s say that Alice bids a 100, so Enc(100) will be made public; now Eve can easily generate Enc(101) and win the auction without ever knowing the exact value of Alice’s bid.
Guaranteed Output Delivery: Basically, the protocol should be resistant towards a denial of service attack; in other words, corrupted parties should not be able to prevent honest parties from receiving the output.
Fairness: Corrupted parties should receive output if and only if honest parties also receive the output.
More Definitions
I am, again, directly following Section 2.2 of the paper mentioned above.
Adversary behavior
Here, we mainly deal with two parameters defining the adversary: its behavior (whether it is only passively collecting the data or instructing the corrupted parties on their actions) and its corruption strategy.
Allowed adversarial behavior
Semi-honest adversaries: In this model, the adversaries are only curious about the states and inputs received by the corrupted parties as part of the protocol. In other words, corrupted parties follow the protocol as it should be. Ensuring security only against such adversaries is often insufficient but ensures no “by accident” data leaks in the protocol. They are also called “honest-but-curious” and “passive” adversaries.
Malicious adversaries: In this model, corrupted parties can deviate from the ways of the protocol. This is nothing but an “adversarial attack.” These adversaries are also called “active.” Providing security against them ensures resistance towards adversarial attacks.
Covert adversaries: May act maliciously in order to break the protocol. But the security guarantee implies that such an attack should be detected with some specified probability (which can be tuned).
Corruption strategy
Static corruption model: The number of nodes influenced by the adversary is fixed before the execution of the protocol. So, what is honest, stays honest, and what is corrupted, stays corrupted.
Adaptive corruption model: These models give the adversary the power to corrupt new nodes during the execution of the protocol. This models attackers as an external hacker breaking into a machine during the execution, or a node which is honest initially and later changes its behavior (sus node lol). One thing to note in this model is that once a node is corrupted, it’s going to be corrupted the whole time thereon.
Proactive security model: In this model, certain nodes are corrupted only for a certain period of time. The security guarantee is that the attacker only learns what was stored on a node during the time it was compromised. Nothing before and nothing after.
Modular sequential and concurrent composition
In real-world systems, these protocols can very well be just another subroutine being called multiple times in a large system. So one critical question arises: “If I design a secure MPC protocol, can I safely plug it into a bigger system and still be sure that everything remains secure?”
For this, we have this modular decomposition theorem, which states that if a subprotocol is proven secure in isolation, then one can replace an ideal trusted party with the real protocol—and the larger system will behave exactly as if the trusted party executed it.
With this, one can view the MPC protocol as a black box. If it’s secure by itself, then it stays secure when used inside a bigger machine.
Now, another question arises: “Does an MPC protocol stay secure if it runs at the same time as other protocols?” For this, we have two settings: sequential and concurrent composition.
The sequential case is more trivial than the concurrent one. It has been shown that given a secure MPC protocol (stand-alone setting), then when used as a subroutine inside a bigger (sequential) protocol, it behaves exactly like a trusted third party. This is the sequential modular composition theorem.
So, as long as other protocols don’t run at the same time as the MPC, we are good.
Now, the more realistic case: concurrent composition. In reality, networks are asynchronous, so adversaries can delay messages, reorder messages, inject messages, and correlate different executions. So, in this case, a protocol that is perfectly secure in the stand-alone model may become insecure when run concurrently.
Let’s consider a simple example:
- An MPC protocol might rely on certain randomness.
- If an attacker interacts with two instances at the same time, they might relate messages from one instance to another, breaking privacy or correctness.
- Many ZK and MPC protocols are insecure under concurrency without modification.
To solve this concurrency problem, cryptographers (Canetti, 2001) introduced Universal Composability. A protocol proven secure under UC behaves like an ideal trusted-party execution even if arbitrary protocols are running concurrently with it.
This is extremely strong:
- Run 100 instances of the same MPC protocol in parallel: secure.
- Run zero-knowledge protocols alongside: secure.
- Run on a chaotic asynchronous network: secure.
- Run insecure garbage protocols interleaved: secure.
This is why it is universal; it composes with anything. But there are some obvious tradeoffs, like round-complexity, communication complexity, and computational expense. This universal composability is a topic for a whole other blog.
Let’s finish off this blog right here… starting with the second part right away so that I don’t delay it indefinitely.
peace. da1729