Secure multiparty computation explained: Ensuring trust in untrustworthy environments

What is secure multiparty computation?

The term “secure multiparty computation” (SMPC) refers to a collection of algorithms that allow people to work together over a network to find a consensus or compute a value and have faith that the answer is correct. Everyone contributed fairly and there was no cheating.

The idea emerged as cryptographers looked for ways to play games over a network. In the beginning, computers worked by themselves. When networks appeared, programmers found ways for computers to work together on solutions. Today, it’s common for constellations of virtual machines to toil away together until they find the right response. The problem is figuring out how to do it securely while ensuring that no one is cheating.

Theoretical mathematicians have studied idea of multi-party computation for decades. Now the algorithms are starting to emerge from the labs and find a role in the more complicated web applications, APIs, and services being developed.

The new role is found where there’s less trust.

Most enterprise stacks are filled with code that is, more-or-less, working together and pulling in the same direction. One web service query might be answered by assembling the data stored on one machine with data stored on a different machine formatted by a template controlled third machine, all orchestrated by a Kubernetes cluster supervisor running behind a load balancer. Even desktop machines bundled together trust that the CPU chip is working together with the power of the graphics card and the network card to serve the same user.

All these examples operate in a little Shangri-La or bubble of trust. What if the different machines and layers of the software stack are run by people who don’t trust each other? Maybe they’re on different sides of some political line. Perhaps they each have different fiduciary obligations to protect. Or maybe they just don’t like each other.

SMPC algorithms make it possible for people and their computers to work together even when they don’t trust each other. They fold together enough basic auditing and cryptographic power so each side can be sure that the final answer is correct, even if their sworn enemy on the other side of the network is trying to betray them and steal everything—even if your so-called friend is stabbing you (metaphorically) in the back.

How secure multiparty computation works

Most encryption algorithms are run by one person and all the mathematical calculations are done inside that person’s or entity’s bubble of trust. A file might be encrypted in the safety of a personal, password-protected machine before being emailed or stored in the wild, untamed internet. A digital signature is created by a private machine using a key that’s protected against disclosure and so others will believe that only the owner of the key created the signature.

SMPC can leverage many of these basic algorithms to find solutions to politically more complicated problems. They often use the same standard encryption or digital signatures, but they apply them in a coordinated dance to extend their bubble of trust. 

The blockchains used by many cryptocurrencies are a good basic example of how basic digital signatures can be applied in a coordinated way to create a larger bubble of trust between people who don’t know each other. In many of these algorithms, the ownership of a particular cryptocoin is linked to knowing a secret key and the coin is spent by adding a digital signature transferring ownership to someone else’s secret key. Often these transactions are certified with other transactions in a big block by the digital signature of someone else. Taken together, this web of digital signatures tracks the ownership of money and may one day form the foundation for a stable economy.

Secure multi-party computation also has a more precise definition in the world of theoretical computer science. Some of the earliest algorithms proved that arbitrary calculations could be split up and still produce a trustworthy answer. The earliest proofs showed that it could work for any arbitrary computation that’s expressed as a sequence of Boolean gates. Over the years, the mathematicians have developed more sophisticated and focused algorithms that can tackle problems.

Types of secure multiparty computation

Many different algorithms are considered under the SMPC umbrella. The earliest algorithms were first published in the 1970s as mathematicians searched for a way to play games like poker over a distance when both sides could not watch for cheating during the dealing of the cards. They soon evolved into a search for good algorithms for solving arbitrary Boolean functions.

The following common types of algorithms can be used by themselves for smaller problems or combined to tackle more elaborate challenges.

• Secret sharing: A secret value is split into N parts in such a way that any subset of K is enough to reconstruct the secret. The simplest example encodes the secret in the Y-intercept of a line. N points on the line are chosen at random. Any two are enough to reconstruct the line and recover the Y-intercept, K=2 in this example. More sophisticated math can work with larger values of K. The secret that’s hidden is often a private key to a larger file. Once the parts are distributed and the original key is destroyed, some K people must work together to unlock it.
• Cut and choose: This basic step is the foundation for many algorithms because it allows one side to audit the other without revealing secret information. One side will scramble their data into several packets of data that are scrambled in some way. When these are presented, the other side will choose some of the packets to audit at random by asking for the keys to unscramble those packets. If everything is consistent and the data is correct, these unscrambled packets are discarded and the unaudited packets are assumed to be correct. Both sides can commit to sharing information while still keeping the unaudited parts private. 
• Zero-knowledge proofs: These are more elaborate versions of digital signatures where the creator of the proof can demonstrate knowledge without revealing the values themselves. These are often useful in more complicated algorithms because one party can commit themselves to a secret choice without revealing it. A simple version is often called “bit commitment” and it is a protocol in many games. Both sides can flip a coin over an insecure line by each choosing heads or tails at random. Each side uses a one-way function like the Secure Hash Algorithm (SHA) to scramble their choice with extra randomness for secrecy. First, both share the scrambled version with each other. After both sides know both scrambled values, both sides reveal their original random value of heads or tails. One side wins if they match and the other side wins if the values don’t. Both sides can audit each other by recomputing the one-way function.
• Non-interactive zero-knowledge proofs: The earliest zero-knowledge proofs required two parties to interact as one would prove some statement to the other. Later, non-interactive versions emerged and were given names like SNARKs or ZK-SNARKS. The goal was to produce a small bundle of bits that would contain all the information of the proof. Anyone could examine the bundle after the fact, perform similar calculations, and come away with the same conclusion. These bundles often act like more powerful digital signatures by attesting to complex facts while also keeping some information private. A simple example might be a driver’s license that established a person was over 21 years old and eligible to purchase alcohol without revealing the actual age or birthday.

Secure multiparty computation use cases

The algorithms are useful in many business transactions because they allow people to both, in the motto of Ronald Reagan, trust each other but verify everything they do. Use cases include:

• Cryptocurrencies: While debate remains about whether society should trust the economy to a digital currency, there’s no doubt that the market capitalization is a testament to the power of SMPC. A vast majority of the transactions continue to run smoothly as expected by both sides. Many of the high-profile problems have been caused not by failures of the algorithm but by leaks in the surrounding computer systems.
• Game play: As people turned to online venues for entertainment, cheating became easier. Giving each side control of their local hardware is an invitation for cheaters to break into the game software to look for hidden data like maps. Some might even fiddle with the data structures to add extra powers or currency. SMPC algorithms can help prevent this cheating without requiring special trustworthy hardware. (I wrote an early exploration of the topic almost 20 years ago called Policing Online Games.)
• Contract negotiations: Many businesses often work closely with some essential partners but can’t completely trust each other. Car dealerships, for example, work with banks for loans and insurance companies to guarantee the asset. Traditionally, the purchase requires plenty of paperwork as each side tries to protect themselves. SMPC can enable more parties to close deals without elaborate paperwork.
• Data collection: People are often hesitant to participate in studies because they don’t want to reveal private information. Many marketplaces depend on accurate aggregated data about demand and supply. Gathering this information, though, can be tricky because participants don’t want to share their raw numbers. Secure algorithms can help gather this information in a way that protects privacy.
• Automated marketplaces: Traditional markets often depend upon people who take a neutral role as an arbiter. The Bitcoin blockchain is just one example of how an algorithm can replace the middleman in transactions.