Secure Multi-Party Computing (sMPC) — Collaboration Without Sharing
The next step in the world of analyzing big data is sharing data, which leads us to innovations. Sharing data allows us to create products that make our lives easier (god bless self-driving cars, health care tips, and those tik-toks that perfectly summarize our complex stream of thoughts late at night, etc.).
This is all good until we’re betrayed, and someone shares our data with the dark side (cough… 2020’s US Elections). This is why privacy is crucial and why many organizations are starting to embrace privacy-enhancing tech (PET). Privacy tech is a broad field and ranges from zero-knowledge proofs to ring signatures, today, we’re going to focus solely on secure multi-party computing (sMPC).
💻 What is Secure Multi-Party Computing?
👨👦👦 Threshold Signatures (TSS)
🏬 Different MPC Implementations
What is Secure Multi-Party Computing (sMPC)?
The simplified description of MPC is it’s a software solution that allows multiple parties to collaborate on an answer without ever revealing their data to one another.
Secure multi-party computation (MPC) enables a group of independent data owners who do not trust each other or any common third party to jointly compute a function that depends on all of their private inputs.
- Secure Computation, Wei Jiang
Use Cases
Multi-party computing has been around for years and has several applications outside the blockchain and crypto space, including advertisement optimizations, machine learning, etc. Below are a few notable use cases MPC was used in.
Private Auction for Sugar Beets
The first large-scale commercial application of the technology was used to preserve privacy in sealed-bid sugar beet auctions in Denmark.
In this type of auction, the highest bidder wins but pays the price proposed by the second-highest bidder.
MPC enabled the sugar beet farmers to place bids without revealing what they were willing to pay to Danisco, the only Danish sugar beet processor at the time.
https://csrc.nist.gov/csrc/media/events/meeting-on-privacy-enhancing-cryptography/documents/toft.pdf
Salary Inequity
The City of Boston and the Boston Women’s Workforce Council (BWWC) needed to identify salary inequities across different genders and ethnicities at various levels of employment (executives to entry-level). To prevent anyone’s salary from getting exposed in this study, Boston University created a tool that allowed employers to submit salary data privately. This work indirectly led Congress to include secure multi-party computation as a consideration in the bill “Student Right to Know Before You Go Act of 2017”.
Key Management
Today many companies that secure crypto assets rely on MPC technologies, including PayPal, Facebook, Coinbase, and BNY Mellon (based on the fact they acquired or announced relationships with MPC companies like Curv, Unbound, etc.).
A little bit about Crypto Assets…
Crypto assets are represented with key pairs (public and private keys). The crypto wallet address is derived from the public key and the public key is derived from the private key.
The twist is that you can’t go reverse, you can’t use the address or public key to ever derive the private key. Whoever has the private key can prove ownership of the crypto assets and sign transactions (which essentially means they can spend/send crypto).
Hence the phrase, “Not your keys, Not your coins”.
MPC is used to prevent a “single point of breach” with crypto keys, no one device or party can own or spend the crypto alone. Each party (machine or entity) jointly produces a single signature for a transaction using their “piece of the puzzle.”
Plot Twist: There are never actual keys in this solution, they use variables that mimic the actions of a piece of a key.
Another Plot Twist: The variables that represent the pieces of a key are never combined in one place. Instead, they use homomorphic encryption to jointly create a resemblance of key pieces and sign the transaction.
Below are a few open source libraries that tackle MPC in the crypto asset space:
Unbound’s Experimental MPC Implementation — Currently in Archieve (since 2021)
ZenGo’s MPC over Signal
ZenGo’s MPC ECDSA
Taurus Groups — Using the implementation CGGMP
Yao’s Millionaire Problem
In 1982 Yao introduced Yao’s Millionaire problem, where Bob and Alice want to know who’s richer without ever revealing their wealth to each other. To solve the millionaire problem, Yao proposed a two-party computation (2PC) protocol based on Garbled Circuits.
Yao’s Millionaire Problem — What’s Alice and Bob’s average net worth?
In this scenario, we will try to find the average wealth between Alice and Bob. We don’t want either Bob or Alice to reveal their wealth, that’s where sMPC (secure multi-party computing) comes into play.
- Alice and Bob split up their wealth in secret shares, these shares are random and all add up to their wealth (i.e., Alice’s secret shares $2 million + $6 million + -$3 million = $5 million)
2. Alice and Bob randomly distribute their shares to each other, at this point, these shares mean nothing to one another.
3. Alice and Bob add up all their shares (i.e., Alice’s shares include Bob’s secret share of $500,000 and her shares of $2 million and $6 million, which all adds up to $8.5 million).
3. Alice and Bob combine their results from step 2, the addition results of their shares, and calculate the average of their salaries.
Disclaimer: This is an over simplified explainer of MPC and the Yao Millionaire problems.
Homomorphic Encryption
To preserve privacy, we need to work with encrypted data without ever decrypting and viewing it, this is where homomorphic encryption comes in.
Homomorphic encryption allow mathematical operations (booelan and arithmetic) to be performed on encrypted data without compromising the encryption.
The Goal for Homomorphic Encryption
After allowing a finite number of additions or multiplications on encrypted data, it must provide a result that would be the same as the results if it was all done without encryption.
“So, basically, anybody can come and they can stick their hands inside the gloves and manipulate what’s inside the locked box. They can’t pull it out, but they can manipulate it; they can process it. They can take raw materials and produce a necklace or something inside the box. And, you know, they finish and [the person with the private key] has to come with the secret key and open it up, and only they can extract the finished product out of there.”
- Dr. Craig Gentry
Types of Homorphic Encryptions
There are three types of homomorphic encryptions, partially homomorphic (PHE), somewhat homomorphic (SHE), and fully homomorphic encryption (FHE). They vary by the types and frequency of mathematical operations performed on the encrypted data.
Partially Homorphic (PHE)
PHE allows only select mathematical functions to be performed on encrypted values. This means that only one operation, either addition or multiplication, can be performed an unlimited number of times on the encrypted data. This operation can be only addition or only multiplication.
Choose Your Poison: Pick one operation, and you can use it infinitely
Ciphertext 1 + Ciphertext 2 + Ciphertext 3 +… + Ciphertext NA few examples of PHE are RSA encryption (multiplicatively homomorphic*), pallier encryption (additive homomorphic), and ElGamal encryption (multiplicative homomorphic).
- RSA is based on exponentiation: C = (m^x) (mod n), where m is the message and x is the secret key. The rules of exponents say that (a^n)(b^n)=(ab)^n. This means that multiplying two ciphertexts encrypted with the same key is equivalent to raising the product of the plaintexts to the power of the secret key.
Somewhat Homorphic (SHE)
SHE supports limited operations (for example, either addition or multiplication) up to a certain complexity, but these operations can only be performed a set number of times.
For example, a somewhat homomorphic encryption algorithm may support any combination of up to four additions or multiplications. However, the fifth operation of either type would create an invalid result.
Choose Your Poison: Pick a combination of operations and use it a set number of times.
Ciphertext 1 + Ciphertext 2 x Ciphertext 3 + Ciphertext 4Fully Homomorphic (FHE)
With fully homomorphic encryption, you can have it all, a combination of operations, and run them infinitely. The main FHE schemes are based on the LWE (Learning With Errors), Ring-LWE, NTRU, and Approximate-GCD problems.
Choose Your Poison: Pick a combination of operations and use it infinitely
Ciphertext 1 + Ciphertext 2 x Ciphertext 3 x … + Ciphertext NDr. Craig Gentry proposed the first FHE scheme based on lattice cryptography. Checkout Dr. Craig Gentry’s thesis on FHE in the paper below:
https://crypto.stanford.edu/craig/craig-thesis.pdf
Sadly, FHE has limitations with its performance and storage requirements, and it’s still a work in progress. You can’t have it all!
Open Sourced Homomorphic Encryption
LattiGo
Microsoft SEAL
PALISADE
HElib
Threshold Signatures (TSS)
Threshold Signatures (TSS) allows parties to share the capability of digitally signing messages.
Threshold signatures require a subset of parties (access structure) authorized to produce signatures on behalf of the group. The message is only considered signed if a threshold (t out of n, t = threshold of signers, n = number of total signers) of signers sign off on the message.
Examples of threshold signature schemes are El Gamal, Schnorr, and multi-signatures. Multi-signatures have additional features that reveal the identities of the group members who produced them.
TSS and Shamir Secret Sharing Scheme (SSSS) sound similar…
TSS and SSSS are similar because they require a certain number of participants from the group to collaborate on a secret. The big difference between TSS and SSSS is that a centralized “dealer” handles the secret share generation process and recombination. In securing cryptocurrencies, the “dealer” in SSSS would generate all the key shares, distribute them to all the different parties, and at the time of signing, regenerate the private key all in one place. With TSS, the private key would never be in a single place.
Check out Rosario Gennaro’s lecture on Threshold Signatures and how they’re used with RSA Signatures:
Oblivious Transfers (OT)
Before we get into the meat of the different protocols, we’re going to review what Oblivious Transfers are, trust me, this all connects when we get into Yao’s Garbled Circuit protocol.
Oblivious transfer is based on the Diffie Hellman key exchange protocol*. Oblivious transfer allows the sender to send two secret messages as inputs to the OT machine without knowing which message will be accepted. The receiver will choose the message they want to receive without letting the sender know.
What is the Diffie Hellman key exchange protocol?*
Diffie Hellman is an end-to-end encrypted key exchange method that allows two parties to communicate securely by giving each party enough information to get the same secret without sharing the secret.
Now let’s see Alice and Bob’s story around Oblivious Transfers…
Bob generates 2 El Gamal public keys that Alice can use to encrypt her two messages.
Alice encrypts her two messages using the public keys Bob sent over and sends the messages to Bob.
Bob uses his choice key to decrypt the choice he made. He won’t be able to decrypt the other message, and Alice will never know his choice.
Voila! This is Oblivious Transfers high level, refer to the resources below to get a deeper understanding.
Stanford Lecture on Oblivious Transfers and Garbled Circuits
Below is Stanford’s lecture on Oblivious Transfers and Garbled Circuits:
https://crypto.stanford.edu/cs355/18sp/lec6.pdf
3 part blog on ADI Engineering
Prof Bill Buchanan OBE video on Oblivious Transfers
Different MPC Implementations
There are quite a few MPC algorithms in use today, some of them are Yao’s Protocol, Gennaro & Goldfeder, Lindel, Doerner, MPC CMP, and PSI (Private Set Intersection).
Yao’s Protocol
Yao’s protocol is the simplest form of MPC, and it introduced garbled circuits. It’s built for “honest-but-curious” (semi-honest) situations, where the parties follow the protocol to create and evaluate the circuit but might try learning extra information during the exchange. There are also malicious scenarios or byzantine adversarial, which this specific protocol doesn’t account for.
How does Yao’s Protocol of Garbled Circuits work?
Yao’s protocol solves for two-party privacy-preserving computation with a “Garbler” and an “Evaluator.” The garbler takes the results and garbles them like a shuffle, and the evaluator comes up with a result from the shuffled input.
Before getting into the fun, we need to first convert the function we need to evaluate into a circuit of gates.
Gates
Any discrete, fixed-size function can be implemented as a logic gate (AND, OR, NOT, XOR, etc.) and can be represented as a truth table. Check out https://byjus.com/jee/basic-logic-gates/ to dive deeper into gates.
Using the images above, the expression AB + BC + AC would look like the image below in a circuit.
The goal now is to encrypt the circuit so we won’t know the inputs and the output of the circuit, and still produce an output that we can use as an input in the next gate.
Garbled Circuits
Encrypting the circuit’s truth table is called “Garbled Circuits.” In Garbled Circuits, we have an evaluator and a garbler, the names say it all, the garbler is the one that garbles the circuit, and the evaluator is the one that evaluates the circuit. Below is the story of Garbling Circuits:
Alice creates her “Truth Table” by converting her function into circuits
Alice garbles her truth table and encrypts her output keys
Alice sends the garbled circuit and her encrypted keys, and now Bob is almost ready to evaluate
Alice asks Bob to send her his keys
Bob can’t send his keys, so Alice proposes to use Oblivious Transfer
Check out Introduction to Garbled Circuits by the Ku Leuven Cosic research center:
https://www.esat.kuleuven.be/cosic/blog/introduction-to-garbled-circuit/
PSI (Private Set Intersection)
Many of us have already interacted with an MPC implementation by Google. When Google Chrome notifies you that your password has been compromised, they use MPC, specifically PSI.
They are not reading your password. Instead, they are using their MPC implementation, Private Join and Compute, they are cross referencing your encrypted passwords with an encrypted list of compromised passwords.
Below is a good video on PSI by Google:
This infographic cleared up a few difficult concepts in MPC:
https://storage.googleapis.com/gweb-uniblog-publish-prod/documents/private_join_and_compute.pdf
MPC CMP (UC Non-Interactive, Proactive, Threshold ECDSA)
MPC CMP is based on Gennaro (City College, CUNY) & Goldfeder (Cornell) and Lindell & Nof protocols. It was devised by Ran Canetti (Boston University), Nikolaos Makriyannis (Fireblocks), and Udi Peled (Fireblocks). MPC CMP addresses the following:
- Reduced Signature Rounds (Performance): Signatures generation takes 4 rounds, compared to 8 rounds.
- Non-interactive (Cold Wallet Support): 3 of the signature generation rounds are done in the pre-processing before the signed message is known, allowing for the non-interactive property where not all machines need to be online at the same time.
- Identifiable Abort (Accountability): Faulty/malicious signers are identified in case of a failure.
- Proactive Security (Adaptive Adversary Secure): Protects long-haul security against adaptive adversaries. Adaptive adversaries are adversaries allowed to evolve dynamically, there are adaptive online adversaries (medium adversaries) and adaptive offline adversaries (strong adversaries).
- UC (Universal Composable) Security: It uses the UC framework for the global random oracle model, strong RSA, semantic security of the Paillier encryption, and an enhanced variant of existential unforgeability of ECDSA.
Notes about Rounds
Parties exchange information in a sequence of rounds to compute a signature for a given message. Since CMP leverages pallier encryption as a committment scheme, it reduces round-complexity and enables concurrent signings.
The combination of pallier committments and ZK (zero-knowledge) proofs, allows the parties to be confident the share is well-formed at the end of the pre-signing phase, which means there’s no additional rounds needed.
Online and Offline Signing Rounds
CMP interactive (online signing) requires the parties to run the pre-signing stage followed by the signing stage for a total of 4 rounds. Non-interactive (offline signing) differs because the signature nonces are known before the message is signed. To prove security, we rely on the assumption about the unforgeability of the underlying (non-threshold) scheme.
Below is a comparison between MPC CMP and other MPC algorithms:
Check out the white paper for further details on the implementation:
Or check out the intro video:
Or the detailed video:
If you like the post, then you can buy me coffee, thank you in advance!
Hooked? Learn More About MPC
ZenGo’s MPC Intro Video — Dating Game
ZenGo’s 2020 MPC Predictions
MPC Alliance
Pragmatic MPC — PDF Book
https://www.cs.virginia.edu/~evans/pragmaticmpc/pragmaticmpc.pdf
MPC Awesome
Meta’s MPC Intro
Nigel Smart’s Multi-Party Computation: From Theory to Practice Presentation
Where FastAPI becomes FastEnclaves: MPC in Minutes 🦹♀️ 🦸♂️ 👩🚀
Yehuda’s Secure Multi-Party Computing
