Threshold Cryptography, MPC, and MultiSigs: A Complete Overview
Threshold cryptography is one of the most secure techniques for carrying out cryptographic operations. For context, cryptography is a field of study in computer science that emphasizes securely accessing and transferring information between two or more parties without external influence. The importance of cryptography cannot be overstated, not only in the virtual but in the real world as well.
In practice, cryptographic techniques are targeted at keeping information or secrets between the concerned parties away from adversaries. Looking at the bigger picture, cryptography aims to create secure ecosystems that can remain functional with or without the participation of trusted entities.
In 1994, Alfredo et al. proposed one of the earliest proof-of-security systems based on threshold cryptography. In the early years, the military, governments, and organizations that held private data were the only major users of threshold cryptosystems. Since then, there have been several applications of threshold technology.
What is threshold cryptography?
Threshold cryptosystems protect information by encrypting and distributing secrets amongst a cluster of independent computers that qualify as fault-tolerant. The fault-tolerance of a system simply refers to the system’s ability to continue operating despite failures or malfunctions.
As the name suggests, the threshold setting enables individual keyholders to lock a secret in a way that no single keyholder can open the lock individually. Instead, it requires a minimum number of keyholders out of all keyholders (a threshold number) to unlock the secret. Each keyholder has a key pair consisting of a public key and a private key. The public keys are used to encrypt the secret, while the private keys are used to decrypt it.
Since the general idea is to assume that the participating entities are susceptible to compromise, decrypting the shared secret or signing a message requires the cooperation of some, not all, participants, usually above a minimum number.
Moreover, the participants can verify each other’s signature using standard methods, such as checking the validity and authenticity of the certificate.
Threshold encryption also ensures that keyholders are able to collaborate without seeing other participants’ parts of the key. The verification algorithm checks that each keyholder has a valid share of the key without revealing it to others.
With a minimum threshold, it can be ensured that even if some of the participants collude, the secret remains secure. In essence, this technique makes sure that a single individual doesn’t have the full authority, which can lead to vulnerability in the system. It also ensures that even if one or more individuals are unavailable, the secret can be unlocked and doesn’t cause bottlenecks. This makes the system fault-tolerant.
How does threshold cryptography work?
To understand how it works, let us assume we have a secret (S), for example, the seed phrase of a wallet address. After encrypting S using a public key, we split up the corresponding private key among a fixed number of participants, say N.
After setting the number of participants N, threshold cryptography introduces a new variable, which we call K, representing the minimum number of participants required to reform the secret or sign a message. As we mentioned earlier, threshold schemes consider fault tolerance and assume that a single point of failure is not ideal for any functional system. Therefore, in a threshold cryptosystem, the number of signers required to decrypt the secret has to be greater than or equal to K but less than N, where K is also less than N.
Let's say you are a member of a board of trustees of ten people. The secret you’re trying to safeguard is encrypted with its private key split up into shares and distributed amongst the board in secrecy. No board member knows what other fractions exist and who holds them, except the piece in their possession.
To sign a transaction using the private key, the board chooses a threshold of seven persons. This means that seven out of the ten board members must agree and cooperate if the need to carry out any operation that involves the private key arises. Thus, even if half of the board is compromised, they will not be able to reconstruct the secret without at least two more people. Getting 7 out of 10 points of failure is not exactly something that often happens. Furthermore, even if one bad actor can corrupt another six actors, it would anyway be equivalent to a direction taken by a clear majority. This thereby suggests that the system is secure as long as the majority (higher than a threshold number) of participants are acting in a democratic way.
Applications of threshold cryptography
Threshold schemes offer more security than many other cryptographic techniques. As a result, several cryptographic protocols, operations, and applications adopted it.
The most typical application is in the storage of secrets. Most often the secrets that are "split" are the secret key material of a public key cryptography or of a digital signature scheme.
Their applications can be found in various sectors such as the Internet of Things, cloud computing, authentication, ad-hoc and sensor networks, etc. Here are some of threshold cryptograpy’s most common applications today:
Mitigating MEV
MEV, short for Maximal Extractable Value, is a “tax” that miners, validators, and other blockchain actors extract by reordering transactions before confirming them on the blockchain. Although MEV extraction has been used for good causes like balancing token prices across decentralized exchanges, most MEV extraction techniques are outrightly malicious, profiting from a user’s trades without their knowledge.
Blockchains like Ethereum do not require transactions in a block to be processed in any specific order. Thus, validators can rearrange transactions in it however they like. The validators profit from this reordering or rearranging of certain transactions so that they can extract a profit via liquidation or arbitrage.
In a threshold cryptosystem built on the blockchain, the participants collaborate off-chain to create a single transaction and submit it to the network. Since the private keys are split up among multiple computers or nodes, the transaction leaves no on-chain trail behind.
Some protocols, like SKALE, have applied threshold cryptography schemes to combat MEV. SKALE’s S-Chain validators create a key collectively. Senders use this key to encrypt transactions before submission to the network for validation. When encrypted transactions lie in the mempool, their details are shielded from validators. After they are posted to the blockchain, transactions remain encrypted until validators decrypt them.
While transactions are in transit, they retain their encrypted form. Validators cannot decrypt them until they have approved them on the blockchain, thus blocking any opportunity for front-running, sandwich attacks, or reordering according to preference.
Even if some network nodes become compromised, the system remains functional because a single node cannot decrypt transactions. Both encryption and decryption are spread across the validators and require a minimum number (threshold value) of validators. As long as the majority –above the threshold– remain honest, the system remains secure.
Similarly, Osmosis also intends to leverage similar techniques to mitigate MEV. Osmosis plans to encrypt the transactions in the mempool before they’re included in a block. This would hide the transaction information and prevent validators from re-ordering or censoring the transactions for their profit. Once transactions are encrypted, the shards of the private key are shared among all validators and the key can only be reconstructed by ⅔ validators. That way, Osmosis will be able to mitigate the MEV, since the block will be almost simultaneously decrypted while it’s being confirmed. Validators will not be able to extract value at the cost of users’ profit.
Another platform mitigating MEV by leveraging the threshold cryptographic techniques is Shutter Network. Shutter Network is an open-source project that aims to prevent front-running (a type of MEV) on Ethereum by using a distributed key generation (DKG) protocol based on threshold cryptographic techniques.
Similar to SKALE & Osmosis, Shutter also uses these techniques to send encrypted transactions in a way that protects them from front-runners on their path through the dark forest (the metaphorical hunting ground of front-runners that each transaction must cross).
Improving MultiSig
Multisignature schemes, popularly known as MultiSigs, multi sig wallets or multisignature wallets, require two or more participants to sign a message or approve a transaction before the transaction can be executed. Using the earlier “'board of trustees” example, if all board members had to vote on transferring funds in their treasury to a charity, all ten board members would need to contribute their signatures to the MultiSig scheme to approve the transaction.
Multisigs can be set up with an arbitrary number of keyholders. A 2-of-2 MultiSig requires that both parties holding the keys sign any message. With a 2-of-3 MultiSig wallet or setup, three parties hold the keys, but only two need to come together to sign a transaction.
MultiSig schemes are similar to threshold cryptosystems, as they are distributed systems. Yet, MultiSig participants each have a complete public key, while participants on threshold schemes receive only a share of a single common public key.
Threshold signature schemes are replacing MultiSig applications. While multisignature wallets are more secure than single signature wallets , threshold signature schemes cost less because they are computed off-chain. They relay a single transaction to the blockchain, while MultiSig relays all the individual contributions separately.
MultiSig schemes are a kind of threshold scheme without the threshold feature. They need all participants to contribute, as opposed to threshold signature schemes which only require a preset number of participants to sign transactions. To be clear, we can refer to MultiSig schemes as a threshold cryptosystem built on a blockchain’s application layer.
MultiSig schemes have been used in developing secure blockchain interaction infrastructure like wallets. Several cryptocurrency wallet providers are developing wallet infrastructure based on threshold schemes instead of MultiSig. Threshold schemes are more secure as they offer better privacy than MultiSig addresses, consume less block space, are easier to deploy on any blockchain (unlike MultiSig schemes that several blockchains do not support), and provide more operational flexibility.
Multi-party computation (MPC)
Multi-party computation, also called secure multi-party computation, is a simple cryptographic scheme that involves multiple participants. If a single private key is split into shares and distributed amongst participants in an MPC protocol, each participant only knows the share in her possession and must do some collective computational work with each using their share.
A useful example for the use of MPC would be a group of individuals desiring to compute their average salary. They might use MPC to output the average of all these secret numbers without disclosing their own salary to the other members or another trusted third party.
When comparing MPC vs Multi Sigs, we need to consider that the purposes of both digital signature schemes are completely distinct. While MultiSigs are used to distribute between multiple parties the power to sign transactions, messages, or decisions in general, MPC’s goal is to perform computation without revealing the data being processed.
An average threshold cryptosystem splits the private keys among participants such that a minimum number of participants must contribute to decrypting the information or signing transactions. When analyzing MPC vs Multi Sigs in practice, it's worth noting that a threshold scheme's only similarity to Multi-Party Computation lies in the fact that both are distributed systems. When you combine a threshold scheme with a partially homomorphic protocol, it can function effectively as a secure multi-party computation scheme.
Homomorphism allows participants to perform computation while retaining encryption, while the threshold feature ensures that decryption is only possible when dishonest participants are less than the threshold value. Thus, the scheme becomes a threshold multi-party computation protocol.
Qredo is a blockchain protocol that uses a threshold multi-party computation scheme, combining a threshold signature scheme with multi-party computation. When signing transactions on Qredo, each separate node contributes to signing the message.
Silence Laboratories, on the other hand, leveraged threshold multi-party computation schemes to offer not only singing a message with multiple shards, but also social recovery in Web3 wallets. Using the threshold MPC scheme, Silence Laboratories enables the Web3 wallet providers to break a private key into multiple shards, which can be combined to reconstruct the key in case a user loses access to her part of the key.
Trusted setups
A trusted setup is a procedure that involves more than one party. Its aim is to produce the standard parameters that a proof system or similar cryptographic protocols rely on. Trusted setups can also be called exceptional cases of multi-party computation, that require randomness, multiple individuals, and at least one honest party.
Earlier, we spoke of how some contributions in threshold schemes are usually completed off-chain or offline before submitting the results online. Threshold cryptosystems can be used to create trusted setups, as their formations' processes are inherently similar. Threshold signature schemes require a trusted setup phase.
The setup phase in a threshold signature scheme is called Distributed Key Generation, usually the most important part of a threshold scheme. In a Distributed Key Generation setup, participants have to contribute to the key generation and distribution process. Each participant sends their portion of the private keys to the DKG function, which hands over the public key to everyone and splits the private key such that each participant receives a portion that must be kept secret.
While such trusted setups are similar to the average distributed system approach, they have a threshold. Only the threshold number of participants will be required to generate new parameters in a threshold-trusted setup. However, there is a risk of failure if the number of participants that conspire to betray the system is up to the threshold value. Also, some participants may receive incorrect shares, rendering their participation invalid. The latter problem is only valid if contributions stay offline, as participants can validate their shares on-chain.
Electronic Voting
According to Gallegos-Garcia et al. in a 2009 paper, the security of electronic voting protocols needs to evolve to represent true democracy. When it comes to electronic voting, the existing security algorithms at the time had so far always been based on public key schemes.
This paper, on the other hand, proposed providing security to electronic voting protocols via threshold cryptography and blind signatures as a less expensive alternative. Not only do they cost less, but they also offer better privacy, accuracy, and robustness.
Another paper titled A Practical Electronic Voting Protocol Using Threshold Schemes presents a novel secret voting scheme that fully conforms to the requirements of large-scale elections.
The participants in this scheme would be voters, candidates, an administrator, and a counter. The scheme uses threshold encryption to preserve the privacy and accuracy of the votes against the dishonesty of voters, candidates, the administrator, and the counter. Executed well, this could ensure the verifiability, fairness, and soundness of the voting process, and neither administrator, candidates, nor the counter would be capable of producing a false tally, affecting the voting result, or corrupting/disrupting the election.
Threshold cryptography applications do not stop here
Threshold cryptography is a field of cryptography that involves secure secret sharing while eliminating single points of failure usually associated with most distributed systems. In threshold schemes, the system remains functional as long as the majority, usually above the minimum number required to sign a message, remain honest. Even if one or two entities become compromised, the network will retain its integrity.
Several cryptographic protocols have adopted threshold schemes for different purposes, including inhibiting MEV extraction, building secure multi-party computation protocols, trusted setups, replacing MultiSig applications, etc. This cryptographic approach can pass as untested waters in computer science, and extensive research will continue to increase its applications and security potential. In the coming year, we might see many more innovative techniques leveraging it to improve the security of systems with more than one party involved.
About Panther
Panther is a decentralized protocol that enables interoperable privacy in DeFi using zero-knowledge proofs.
Users can mint fully-collateralized, composable tokens called zAssets, which can be used to execute private, trusted DeFi transactions across multiple blockchains.
Panther helps investors protect their personal financial data and trading strategies, and provides financial institutions with a clear path to compliantly participate in DeFi.