Introduction to Multiparty Computation

What is MPC?

MPC, often referred to as Secured Multiparty Computation, stands for Multi-Party Computation. The topic was introduced by Andrew Yao in 1982, by describing a dilemma of two millionaires, Bob and Alice, who wanted to know which was richer without revealing their actual wealth.

The MPC method allows multiple parties to define a mathematical formula that computes desired output without requiring all parties to know each of the inputs. For example: Bob, Alice, and Carol would like to compute their average salary. However, none of them would like to share their details. The solution using the MPC method would look like as follow:

• Bob makes $55K, Alice makes $75K, and Carol makes $50K. Their average salary would be the sum of their individual salaries divided by 3, which is ($55K + $75K + $50K) / 3 = $60K.

• Next, Bob, Alice and Carol, each comes up with 3 numbers which sum up to their salaries. None of the numbers fully reveal their salaries, unless their numbers are summed up.

• Next, Bob, Alice, and Carol randomly share their numbers, so that every one of them has a number from another participant. For example: see how Alice’s numbers where distributed to Bob and Carol. The number 29 in orange color was moved to Bob, and the number 21 was moved to Carol. In a similar fashion, Bob shared his numbers with Alice and Carol, and Carol shared her numbers with Bob and Alice.

• At the end, the average salary can be computed based on shared numbers even though the salaries for Bob, Alice, and Carol have not been disclosed amongst themselves. The formula that was used in this example was to calculate an average, which is, the sum of the shared numbers divided by 3:

  Î¼ = (154 – 255 + 281) / 3

  Î¼ = 180 / 3

  Î¼ = 60

 In the above example, parties jointly agreed on the mathematical formula to calculate their average salary. They shared partial information which did not reveal their salary, yet the formula yielded the desired outcome: learning about the average salary without revealing individual salaries.

This method enables privacy for each party, yet still achieves the desired result: parties learn about the formula’s outcome, without revealing the input.

Role of MPC in Modern Cryptography

Modern cryptography involves the study of mathematical techniques for securing digital information, systems, and distributed computations against adversarial attacks 1.

Most of the secured information that is saved on disks is protected through an encryption process. For example, symmetric encryption protects confidential information that is stored somewhere in the PC or cloud. In symmetric encryption, to encrypt text messages we need an encryption algorithm and a symmetric Key. Out of the three elements (encrypted text, encryption Key, and encryption algorithm) only the encryption Key requires special care and protection. Here is why:

1. There is less concern about access to the encrypted message: the assumption is that the encrypted message is difficult to decrypt, or in other words, an effort to decrypt a protected message would take a long time. The time taken to decrypt could possibly exceed the confidentiality period, aka the amount of time that information needs to be kept confidential. For example: if a negotiation about the merger of two companies cannot be disclosed within the next 60 days, we need to ensure that the privacy of any materials related to the merger stays confidential for the next 60 days. Since decryption of the encrypted message will take much longer than 60 days, then the encryption method exceeded its confidentiality period. 
2. There is no need to care about the encryption algorithm: according to Kerckhoff’s Principle, the encryption algorithm should not be a secret. Reliance on confidentiality should be based on the strength of the algorithm, not the knowledge of how the algorithm works. 

The encrypted message via symmetric encryption Key is only safe, as long as bad actors do not have access to the encryption Key. Therefore, keeping the encryption Key safe is of upmost importance in preserving the confidentiality of the saved messages.

MPC plays an extremely important role in keeping Keys safe. An MPC divides symmetric Keys into random shares and distributes the shares among multiple computers, much like in the Bob, Alice and Carol example. In our above example, we used personas. However, in real life, the personas are represented as Computers. That way, none of the computers have the encryption Key in its entirety but rather possess random shares which do not yield information about the original encryption Key. Whenever we need to assemble the encryption Key, the previously negotiated function is applied to each of the shares and the Key is computed to its original form. In the Bob, Alice, and Carol example, that computation was a simple average function. In a real example, the function is much more complicated and is assembled from thousands of logical operations that when put back from previously divided random shares, produces the original message.

 1.   J. Katz, Y. Lindell, Introduction to Modern Cryptography

Conclusion

The cybersecurity landscape is changing. In most cybersecurity breaches, the adversaries penetrate systems without being detected for weeks, months or even years. The encryption Keys are essential components to keeping our data safe. Once the Key is stolen, data can be decrypted then stolen or even changed without notice. The traditional safeguard of Keys is no longer sufficient as a method of prevention. The Secured Multiparty Computation is one of the new cryptographic methods that can be used to protect encryption Keys. The Keys are split into random shares and distributed to multiple computers. Even if one of the computers is compromised, the adversaries will not be able to guess the remaining parts of the Key. The MPC is one of the safest, if not the safest, ways known today to keep our Keys safe.