Secure Multiparty Computation

Jarred McGinnis
February 26, 2021

Working Together in this Less than Ideal World

Previously we talked about Zero Knowledge Proofs as an emerging way to avoid having to trust large organizations who may intentionally misuse or unintentionally compromise our data. Secure Multiparty Computation (SMPC) is another cryptographic approach, like Zero Knowledge Proofs, that had been kicking around in academia for a number of decades before our messy and hyperconnected world found practical applications for it. 

Secure Multiparty Computation is a way for a number of parties to work together to solve a problem without revealing the information used in the computation to the other parties. It is an approach seen as more straightforward and less computationally expensive than alternatives, e.g. homomorphic encryption.

The most famous toy example to explain SMPC is the 'Millionaire Problem' - there are plenty of examples already of SMPC being explained by some variation of the ‘Millionaire Problem', but we’d be foolish to ignore the opportunity for sweet SEO performance by using the keywords 'SPMC' and 'Millionaire Problem' more often than absolutely necessary.

The Millionaire Problem as an example of Secure Multiparty Computation

There are three millionaires who want to see who has the most money, but they don't want to reveal how much money they have, which is exactly how millionaires spend their free time when not hunting men for sport.

In an ideal world, the millionaires could take turns whispering their net worth to a trusted third-party who then points at the richest millionaire, but these people didn't get their black AMEXs by being trusting. Instead, the first millionaire types a random number into a calculator then adds it to her net worth before passing the calculator to the millionaire on her left-hand side.

This millionaire adds his net worth to the existing number and passes the calculator to his left. The third millionaire adds their net worth to the sum and hands it back to the first millionaire. She subtracts the random number then divides the result by three. She announces the number, which is the average of the three net worths. Each millionaire now knows where they stand, depending on whether their worth is below or above the average, but no millionaire knows the net worth of the others. 

The Call is Coming from Inside the Computation 

Unlike more traditional applications of cryptography where it is assumed that the adversary is a third-party, the assumption for SMPC is that the adversary is a participant, or a number of participants who are in collusion to either gain secret information from the others, or corrupt the output of the shared computation. To avoid these shenanigans, an SMPC protocol must preserve two conditions: privacy and correctness.

A protocol is private if none of the inputs of the participants has been shared. It is correct if each and every party receives the correct output for the given function. The interesting consequence of the adversary being part of the systems means you have different degrees of adversarial behaviour. ‘Semi-honest’ or ‘passive’ participants may follow the protocol but may attempt to break the privacy condition by gaining information that they aren't supposed to have. More cheeky than delinquent, perhaps.

‘Malicious’ or ‘active’ participants on the other hand are trying to cheat or subvert the established protocol. These guys are definitely destined for the naughty step. A lot of research has been carried out to understand the various scenarios and how the malicious or active participants would affect the security and correctness of an SMPC scenario. For example, Shamir's Secret Sharing algorithm is considered still secure as long as less than half of the participants are passive adversaries, or less than a third are active adversaries.  

Practical Applications for SMPC

The value of using data across organizations without compromising the privacy of that data is obvious. The above toy example of the ‘Millionaire Problem’ is a simplified version of how SMPC has been used in Danish sugar beet contracts to ensure that the only information revealed is the winning bids. With 25,000 tons of sugar beet production rights traded, the project claims that this was the first large scale practical application of the technology.

SMPC has proven useful in scenarios where data protection is concerned such as studies on gender equality, which allowed researchers to gather data about salaries from over a hundred different companies who would have been otherwise reluctant to see their payroll information leaving their premises. Scenarios where government agencies or market competitors need to collaborate to answer a question of common interest, such as pay inequality between genders, or genetic factors in certain types of cancers, without contravening data privacy legislation or compromising proprietary information are commonly cited as areas where this technology can help.

Of most immediate interest to us is the application of SMPC in the management and protection of cryptographic keys. The shared computation in this scenario is the generation of secret keys. By ensuring that the participants needed to generate the keys exist in separate and secure environments, the task of the attacker to access that key becomes much more difficult. There are already a number of companies focused on the blockchain offering commercial products in this space

SMPC has the potential to enable collaborative research and analytics that are impossible today because of security issues and the lack of a trust-worthy centralised datastore (i.e. that trusted third party in the ideal world). It can be argued that SMPC has only been deployed in relatively benign settings, and has yet to really be tested in scenarios where the naughty rather than just the cheeky have a go at cracking it. There are lots of settings and properties to consider and one man’s ‘secure’ computation is another's: "What’s Bureau 121 doing in a beet production auction?"

Currently the technology requires a high-level of expertise to deploy. It remains to be seen if SMPC can scale to solve complex problems and large data sets with large numbers of participants. We’re a long way from standardization, but interest from the blockchain community is driving innovation based on quite a long history of theoretical understanding. 

The most likely applications are going to come from the SecOps sector as key management and security is increasingly recognized as critical to an organization’s infrastructure. The loss and/or theft of private keys is time and again shown to be the weak link. Using tools like our analyzer platform is part of understanding that infrastructure and seeing how successfully an organization is managing to secure its keys. It's a classic case of: “An ounce of prevention is worth a pound of cure.”

Further Reading

Check out these review articles that have more depth and a bit more maths to them: 

https://dl.acm.org/doi/pdf/10.1145/3387108

https://securecomputation.org