In the world of cryptography and cybersecurity, there is a fine balance between sharing enough information for productive collaboration and protecting sensitive details to ensure privacy. This challenge becomes especially crucial when multiple parties — each holding private, confidential data — need to perform computations jointly without compromising the security of their individual data. One innovative solution to this quandary is Multi-party computation (MPC).
- What is multi-party computation (MPC)?
- What are the benefits of a wallet that utilizes multi-party computation?
- What drawbacks might come with using an MPC Wallet?
- Comparing multi-party computation and multi-sig wallets
- Navigating security concerns of MPC
- MPC is a stride forward in operations security
- Frequently asked questions
- About the author
What is multi-party computation (MPC)?
Multi-party computation (MPC) is an advanced cryptographic technique. Its primary objective is to enable multiple entities to perform cryptographic operations. All the while, the confidentiality of individual inputs is preserved, and disclosure to any unauthorized third parties is prevented.
MPC is versatile and has multiple use cases, which include:
- Data mining with privacy preservation: MPC facilitates organizations to collaboratively perform data analysis without disclosing confidential data. This allows for the identification of patterns, trends, and correlations while maintaining stringent data privacy protocols.
- Auction security: MPC can be instrumental in designing sealed-bid auctions. It can determine the highest bid without disclosing individual bids, thereby ensuring fairness and averting potential price manipulation.
- Financial services: For secure trading, credit scoring, and risk assessment, financial institutions such as banks can effectively utilize MPC without exposing sensitive information.
- Multi-party machine learning security: MPC enables several organizations to collectively train machine learning models on their combined data sets without revealing individual data points. This promotes mutual collaboration and augments the performance of the model.
- Secure sharing of passwords and secrets: MPC can be used to securely distribute and store sensitive information like passwords and cryptographic keys among multiple entities. This ensures that the information cannot be accessed by a single party without the consent of others.
These are only a few examples of the myriad applications of MPC, underscoring its wide-ranging capabilities in various fields.
Let’s go deeper into understanding MPC with an illustrative example:
Consider three individuals: Karen, Richard, and Melanie. Each of them holds identical roles across different companies, and they’re curious about the average salary for their job title. However, none of them are comfortable disclosing their exact salaries.
We know that Karen’s salary is $60,000, Richard’s is $70,000, and Melanie’s is $80,000. Therefore, the average salary stands at $70,000.
Each input is concealed using a cryptographic function. In this scenario, we represent each salary as the sum of three different values (it’s understood by each member that their salary must be expressed as the sum of precisely three components). While there could be an infinite number of possibilities, for illustration, let’s consider the following:
Each participant only shares two out of the three salary parts with the others, ensuring that they don’t fully disclose their individual incomes:
Each individual combines their salary part with the others they’ve received. Hence, Karen has -$10,000, Richard has $250,000, and Melanie has -$30,000. If they share these sum totals with each other, they can easily calculate the total ($210,000), and by dividing it by 3, they obtain the average salary, which is $70,000. They’ve achieved their goal without disclosing personal salary details.
Distinct features of multi-party computation (MPC)
This concept finds significant applications in the realm of crypto and blockchain technology. For instance, it enables multiple entities to sign transactions without revealing their individual private keys. While this might sound similar to multi-signature (multi-sig) wallet setups, MPC comes with numerous enhancements and advantages.
So how does this work? Given a secret “s,” MPC enables the division of this secret into “n” parts and distributes them among the “n” participants involved in the computation. Applying this concept to the crypto sphere would mean that the wallet‘s private key is disseminated across various members and, consequently, across several devices. This practice provides an additional layer of security to the custody of the private key.
Multi-sig wallet: Each wallet co-owners holds a distinct, fully functional private key.
MPC wallet: Portions of a single wallet’s private key are spread across the devices owned by the members.
What are the benefits of a wallet that utilizes multi-party computation?
- It facilitates collective wallet management. Each transaction must receive approval from either all members or a predefined minimum subset, contingent on the chosen configuration. This is called an MPC wallet k/n setup, where “k” out of “n” total members must agree to authorize a transaction (for example, 2/3, 3/4, etc.). While a multi-sig setup can also allow transaction signing upon reaching a quorum, MPC opens up many new opportunities.
- It removes the single-point-of-failure risk. Every member holds a fragment of the wallet’s private key, which is never shared with others (this holds true only in certain implementations). As such, this removes the single-point-of-failure issue that’s prevalent in wallets, where only one entity manages or safeguards the key. Thus, each member protects their portion of the key on their respective device.
- It offers a high level of customization (the owner can determine the number of wallet members, choose the cryptographic algorithm to use, and so forth).
What drawbacks might come with using an MPC Wallet?
- Members might store their key share on devices that are connected to the internet and thus vulnerable. A potential solution to this could be that each member employs air-gapped or offline custodial devices.
- Members could fall prey to phishing attempts and be duped into disclosing their private key share. This wouldn’t pose any problems until the minimum number of key shares required for signing is compromised.
- Performance suffers when user numbers are high. Having fewer members increases vulnerability (for instance, with three members, a hacker would need to compromise “only” three devices). However, having a larger number of members (like 30) slows down speed and performance due to communication latency.
Comparing multi-party computation and multi-sig wallets
While MPC wallets and multi-sig wallet setups have some common goals, MPC wallets offer several unique advantages:
Key refresh
The private key fragments shared among members can be regularly updated or manually refreshed, providing robust long-term protection against attacks (for example, each salary could be broken down into a different set of three addends indefinitely). Moreover, it’s possible to use keys only once or have them expire after a certain period.
Flexibility
Stemming from the key refreshing feature, it’s easy to adapt an MPC wallet to changes in membership. A simple refresh of the key fragments can transform an MPC wallet from a k/n to a j/m configuration, maintaining the same secret (the wallet’s private key) and hence the same wallet address derived from the public key.
Chain-agnostic
Unlike multi-sig wallets, which are created and deployed on a specific network and have limited compatibility with a select few chains due to on-chain signing, MPC wallets aim to handle the entire shared private key-construction process off-chain. The specific MPC protocol can use various cryptographic mechanisms (such as ECDSA, EdDSA, Schnorr signatures, etc.), making MPC compatible with a broad range of blockchains.
Recovery systems
In the event of a member losing their key fragment, some MPC wallets have recovery mechanisms in place. For instance, all funds could be moved to a dedicated address to prevent permanent loss. Alternatively, thanks to Threshold Signature Schemes, transactions can still be signed with only a portion of the key fragments. Having all shares isn’t a prerequisite.
Lower fees
In a multi-sig setup, each member signs and approves an on-chain transaction, whereas in MPC, the fragments are first assembled, and then a single on-chain transaction is conducted.
Anonymous identities
Because multi-sig operates on-chain, the addresses of the wallet’s members are exposed to potential attackers. MPC only discloses a final address on the chain, keeping all preceding operations confidential.
Role and limit management
Some MPC wallet implementations allow the owner to impose limits on each wallet member’s transactions (for example, restricting the amount of tokens they can transfer).
Delving into threshold signature schemes
MPC wallets are based on multi-party computation technology and utilize several cryptographic concepts that are worth understanding.
Similar to multi-sig systems, MPC-based setups can generate valid signatures even if not all key fragments are collected from all wallet members. A specific minimum, dependent on the chosen configuration, suffices. This is made possible by certain cryptographic threshold schemes, including:
- Shamir Secret Sharing Scheme (SSSS)
- Verifiable Secret Sharing (VSS)
- Threshold Signature Scheme (TSS)
Shamir Secret Sharing Scheme (SSSS)
The Shamir Secret Sharing Scheme (SSSS) is a form of secret sharing that leverages homomorphic encryption. This type of encryption enables operations on encrypted data without the need for decryption.
Within this scheme, a role called “Dealer” is charged with generating the secret (private key) and distributing its fragments to the “n” members of the MPC wallet. When a transaction needs to be signed, all necessary fragments must be returned to the Dealer so they can reconstruct the accurate private key for signing.
This system allows the Dealer to sign a transaction, generating a valid signature, using a private key rebuilt with a minimum set of k pieces out of the total n received from wallet members, where “k < n.” This minimum number is known as the threshold. If only k-1 fragments (below the threshold) are collected from members, it is impossible to reveal any secret, even partially.
One notable drawback with the Shamir Secret Sharing Scheme (SSSS) is the risk posed during key generation and signing, where the entire private key is handled by the Dealer. This results in a single point of failure. So, how can the private key be reassembled from just a handful of fragments?
SSSS hinges on Lagrange polynomial interpolation. This mathematical tool allows for the reconstruction of a polynomial curve (of degree k-1) that intersects the given minimum set of data points (k) and predicts the value in the gaps between known points.
Let’s demonstrate this with an example. Assume the secret code is S = 65, and we aim to reconstruct the secret with k < n shares where k = 2 and n = 10.
If we visualize S as a point on the y-axis of a graph, its coordinates would be S = (0,65). Following this:
- We introduce a random point R in the space. There will only be one line that intersects S and R. We label this line the “secret line.”
- The “secret line” contains infinite points. We denote these points as “secret shares” and distribute a “secret share” to each of the n = 10 members, excluding the point S. This distribution can occur in various ways, depending on the implementation: the Dealer could establish a private communication channel with each participant or broadcast an encrypted version of the secret to everyone (only the correct recipient will be able to decrypt and read the secret share). However, it’s essential that these key shares remain confidential between the Dealer and the recipient.
- We can identify the “secret line” (and thus S by simply intersecting with the y-axis) with any two of the given secrets (points on that line). In this way, we need just any k = 2 of the shares out of n = 10.
- This process can be scaled to a k < n system where k = 3,4,5, and so on. For instance, if k = 3, the “secret line” will be a “secret 2-grade curve” (k-1 = 2). If we manage to retrieve only two secret shares, we cannot retrieve the “secret curve” and thus the secret: we need at least k = 3 points (shares).
SSSS encodes the “secret” (wallet’s private key) as the zero-degree term of a polynomial. Then it creates key shares from the curve and “distributes” it to the various members. As mentioned, to have a correct estimation value in the gap, we need a minimum set of data points k, with k <= n.
Verifiable Secret Sharing (VSS)
A multitude of variants have sprung from the Shamir Secret Sharing, and Verifiable Secret Sharing (VSS) is one such example. VSS operates with the central aim of ensuring that malicious shares are not circulated by the Dealer. This is facilitated through a system where participants validate the piece they’ve received.
One frequently implemented version of VSS is the Feldman VSS algorithm. This method is designed to confirm that each participant receives a secret share from the Dealer that is consistent with the rest.
The VSS protocol is carried out in two stages:
- Sharing Phase: This stage differs slightly from the SSSS. Here, the Dealer, after distributing shares to the participants, also broadcasts commitments to coefficients. These mathematical terms can be used by members to validate the legitimacy of their key share.
- Validity-Check Phase: Once participants have received their private piece and the publicly broadcasted coefficients, they will then proceed to confirm the authenticity of their private share.
In the event of a recipient receiving an incorrect share, they can raise a complaint that must be responded to by the Dealer. If the Dealer fails to address the issue, they are considered malicious and subsequently removed from the protocol. This initiates a dispute phase.
In some cases, an honest Dealer might face a complaint raised by a dishonest member. During this phase, each party must convince the others of their honesty. This underscores the integral role that trust and verification play within the Verifiable Secret Sharing (VSS) protocol.
Threshold Signature Scheme (TSS)
Threshold Signature Scheme (TSS) emerged as a significant development from the Shamir Secret Sharing Scheme (SSSS). While SSSS and its variant, VSS, involve a Dealer entity who knows the complete secret during key share generation and can reconstruct the secret to sign transactions, TSS introduces a significant improvement: the total secret is never located in one place. There’s no longer a sole Dealer entity possessing full knowledge of the secret or capable of retrieving it during signing.
This innovation is achieved through two vital features:
- Distributed key generation: Here, the full secret remains unknown to all members, as each one independently creates a key share. This process, known as Distributed Key Generation (DKG), deviates from the conventional model where a single entity (like the Dealer) generates shares for members. Instead, each participant acts as a dealer in turn. This DKG process applies the VSS scheme, allowing each entity to function as a dealer for a certain round. For instance, Entity A creates a secret S(A) and uses VSS to split it into pieces, distributing S(AA) to itself, S(AB) to Entity B, and S(AC) to Entity C. Each entity verifies the validity of the secret sent by A using VSS and raises complaints, if necessary.
- Distributed signing process: With TSS, members are no longer required to transfer their piece of the private key. Each member creates a signature using the private key to obtain a Partial Signature. The full signature is created by combining these partial signatures shared among members and devices, which validates transactions. One of the entities that provided a partial signature is chosen to serve as the aggregator, which verifies the validity of each received partial signature, as some signers may behave maliciously. If all signatures are valid, the aggregator can compute the final signature. Notably, the role of the aggregator differs from the Dealer’s role in previous schemes. The aggregator can never reveal the full secret key, even when presented with partial or total signatures.
Thus, TSS ensures that the total secret never resides with a single entity at any moment. There are no transferred key shares, and the full private key is never completely reconstructed. This results in a more secure and distributed system for key sharing and transaction signing.
Navigating security concerns of MPC
A crucial concern within an MPC network is phishing, where an attacker manipulates wallet members into revealing their private key share. It underscores the need to handle confidential information securely. Just as it’s imperative for wallets to securely store and never disclose the private key, MPC members should store their private key shares in a secure, trusted environment. Any storage of key shares on vulnerable devices could potentially lead to irreversible consequences.
This is especially critical in MPC systems where “n / n” key shares are required for transaction signing, and the minimum threshold equals the number of wallet members. The loss of even a single key share would result in the inability to manage the funds. Here, members could find solace in maintaining backups of sensitive data.
However, the increase in backup copies doesn’t necessarily correlate with enhanced security. The higher the number of sensitive information copies, the greater the potential attack surface.
An additional trade-off within MPC systems exists between security and performance. MPC-based wallets authenticate key shares or partial signatures using various algorithms and mechanisms. As the MPC network member count increases, so do the iterations of a specific algorithm, such as during key generation or total signature reconstruction. This means having fewer members can make the system more susceptible to risk.
For example, a bad actor targeting an MPC wallet with just three members would only need to compromise three devices/members to retrieve key shares. Conversely, a larger member base (like 30) could decrease speed and performance due to waiting times for protocol cycles, elevated computational power requirements, communication latency, and more.
Vulnerabilities in multi-party computation networks
The communication channel also deserves attention. Since MPC technology relies on a network of internet-connected signers, it could be vulnerable to man-in-the-middle or spoofing attacks initiated by malicious entities. Moreover, in MPC implementations that necessitate simultaneous co-signer member activity, a hacker might perform a denial-of-service attack to disrupt the entire MPC network.
Consider a scenario where three members and a minimum of three partial signatures are required to authorize a transaction. An attacker could force one or more of the co-signers to disconnect from the network, rendering the transaction completion impossible.
Another potential attack vector in some MPC systems is the so-called “Forget and Forgive Attack,” relevant to specific implementations that lack stringent controls when refreshing key shares.
MPC allows secret key shares to be refreshed while maintaining the same total private key and hence, the public key. Despite this process being infinitely repeatable, the newly generated key shares must enable the creation of the same previous private key so that the public key matches the old one. If not, the process is aborted.
The issue arises in some MPC implementations when entities don’t wait for the process completion before erasing their old key share. They simply check the validity of the new share using VSS, potentially allowing a hacker to distribute newly-generated key shares to a subset of the MPC members, bypassing their control mechanisms.
The aim is to get a subset of the entities to reject it and others to accept it, leading to a mix of old and new key shares that no longer add up to issue a valid signature. To counteract this problem, parties should wait for the final “result” before deleting their old key share, possibly by implementing back-channel communication mechanisms between entities.
MPC is a stride forward in operations security
MPC technology marks a notable stride in operations security involving secrets shared among multiple parties. This is particularly pertinent in the burgeoning crypto sphere, where an increasing number of companies and organizations in the Web3 domain require shared asset management across various entities.
Frequently asked questions
What is multi-party computation (MPC) and how does it differ from multi-signature wallets?
What are the major security concerns in multi-party computation?
How does the number of members in an MPC system affect its security and performance?
How does Multi-Party Computation technology fit into the current landscape of Web3?
About the author
Connie Lam is the Head of Solutions Architect at CertiK. Lam is a blockchain expert, software engineer, technical lead, and manager with eight years of experience in full-stack development, data analytics, and SaaS.
Disclaimer
In line with the Trust Project guidelines, the educational content on this website is offered in good faith and for general information purposes only. BeInCrypto prioritizes providing high-quality information, taking the time to research and create informative content for readers. While partners may reward the company with commissions for placements in articles, these commissions do not influence the unbiased, honest, and helpful content creation process. Any action taken by the reader based on this information is strictly at their own risk. Please note that our Terms and Conditions, Privacy Policy, and Disclaimers have been updated.
