Nov 8, 2024 7 min read shutter

Secret Sharing with Snitching: Addressing Shareholder Collusion in Threshold Cryptography

Secret Sharing with Snitching solves the issue of shareholder collusion by making it provable and punishable.

Threshold secret sharing is a fundamental cryptographic primitive used to protect sensitive information by distributing it across multiple parties, known as shareholders. Only a specified number of shareholders, called the "threshold", can collaborate to reconstruct the secret. If fewer than the threshold number of shareholders attempt to piece it together, they learn nothing about the secret.

Threshold secret sharing is an essential building block for many advanced cryptographic primitives, including secure multi-party computation (MPC) and threshold encryption, both of which are crucial to the success of secure, decentralized applications. Looking ahead, a threshold fully homomorphic encryption scheme (threshold FHE) could leverage secret sharing to enable fully private and trustless, yet auditable transaction processing on a blockchain. Even today, Shutter’s threshold identity-based encryption scheme uses secret sharing to safeguard sensitive information in decentralized settings.

However, despite its wide potential, threshold secret sharing faces a significant challenge: its security crucially relies on the threshold assumption, i.e., the assumption that fewer than the threshold number of shareholders act maliciously. As soon as the threshold amount or more malicious shareholders collude, all security guarantees are lost. Indeed, the risk of this happening is a genuine threat, as demonstrated by several high-profile attacks on multi-signature (multi-sig) bridges and wallets. For instance, in the Ronin Bridge Attack, 5 out of 9 parties were compromised, resulting in a theft of approximately $625 million, while in the Radiant Capital Hack, 3 out of 11 parties were corrupted, resulting in $50 million stolen. While these examples involve multi-sigs rather than threshold secret sharing, they underscore the risk of having more than the threshold amount of parties acting maliciously.

Although collusion can generally not be prevented, it is relatively easy to detect in the case of multi-sigs because (1) the resulting signature is typically used on-chain and therefore serves as a public proof of collusion, and (2) the colluding parties can be uniquely identified. So while we cannot prevent collusion, we can identify and punish malicious actors, thereby achieving some form of economic security. However, the same is not true for threshold secret sharing. Here, the reconstructed secret often does not need to be published on-chain, and simply knowing the secret does not reveal the identities of the colluding parties. Thus, real-world cases of collusion in threshold secret sharing schemes may have occurred but remained undisclosed.

This raises the question:

How can we make shareholder collusion in threshold secret sharing schemes identifiable and punishable such that we can ensure security beyond the threshold assumption?

A recent paper by Dziembowski et al., that was published at the ACM CCS 2024 conference, made significant progress towards answering this question. The paper is co-authored by Stefan Dziembowski and Sebastian Faust, the two cryptographers behind the Shutter protocol scheme, and introduces an innovative cryptographic primitive called Secret Sharing with Snitching (SSS), which solves the issue of shareholder collusion by making it provable and punishable.

Snitch: To turn informer; tattle. To secretly tell someone in authority that someone else has done something bad.

With SSS, if a group of shareholders collude to prematurely reconstruct a shared secret, there is a strong chance they will be snitched on by one of their fellow collaborators. The snitcher, in this case, can produce cryptographic evidence of the malicious reconstruction, which can be submitted to an external judge (like a smart contract) to trigger penalties. Shareholders could be economically incentivized to snitch to the judge, which creates a self-regulating system where the risk of betrayal from within the colluding group deters any attempt at dishonest behavior.

This novel primitive is poised to address the fundamental collusion problem of threshold cryptography and therefore paves the way for wide adoption in practice. Let’s go into a bit more detail of how SSS works.

Naive Solution Attempt.

At first glance, it might seem simple to construct a snitching mechanism for secret sharing: if colluding shareholders reconstruct the secret too early (at time t instead of the agreed time t', where t' > t), a snitch could reveal the secret to the judge before time t'. Since the snitcher knows the secret, they must have colluded with other shareholders.

However, this naive approach has three critical flaws:

Identifying the colluders: Simply revealing the secret does not prove which shareholders participated in the illicit reconstruction.
Partial Reconstruction: Colluding shareholders might compute a function of the secret instead of the full secret, thereby escaping detection.
Framing: Any party knowing the full secret could frame the shareholders (even honest ones) by sending the secret to the judge.

Thus, a more sophisticated method is required to detect and punish collusion effectively.

The Actual Solution

The real power of SSS lies in a series of mechanisms that ensure collusion is provable and punishable. Here’s how it works in a nutshell:

Cryptographic Trap: Each share in the secret-sharing process is embedded with identifiable cryptographic information. If the secret is illicitlly reconstructed, this information can be used to trace back to the colluding shareholders.
Proof of Misbehavior: Any illicit reconstruction generates cryptographic fraud proofs. These proofs can be used to demonstrate that shareholder collusion has taken place. Additionally, they ensure that an honest (non-colluding) shareholder cannot be wrongfully punished.
Snitch Mechanism: The system sets up a scenario where any of the colluding shareholders can "snitch" on the others by providing the fraud proof, effectively betraying the misbehaving group. This creates a strong incentive to not collude, as there is always the risk that one party might expose the illicit activity.
Smart Contract Enforcement: Once a fraud proof is generated, it can be submitted to a smart contract on-chain. The smart contract can enforce penalties, such as confiscating staked assets or imposing financial punishments.
Deterrence by Design: The very existence of a snitching mechanism and the ability to enforce punishment via smart contracts discourages shareholders from even considering collusion. They are aware that someone within the group could expose their wrongdoing, making honest behavior the safest and most profitable option.

The paper also describes a sophisticated attack that an SSS scheme must be secure against: a so-called MPC attack. Here, colluding shareholders run an MPC protocol to compute an arbitrary function of the secret without revealing their shares to each other. Without the shares, the snitcher has no identifiable information and therefore cannot punish the colluding shareholders. The authors deal with this problem by using so-called MPC-hard functions. These are functions that are hard to compute in a distributed manner, e.g., using an MPC protocol, but easy to compute on an individual device. This effectively prevents such sophisticated MPC attacks.

The threshold trust assumption has been and continues to be a major barrier to widespread adoption of threshold cryptographic schemes in practice. With SSS, that assumption can be reduced significantly, enabling substantial growth in MPC and threshold cryptography use cases. A good example is Shutter’s threshold encryption based MEV protection, which can be secured from Keyper collusion and premature decryption of shielded transactions. More generally, SSS enables the adoption of more Actively Validated Services (AVSs) and it provides enhanced security and integrity for MPC protocols.

Direct Impact on Shutter

For the specific case of Shutter, SSS has the potential to enable full transaction encryption while disincentivizing collusion among Keypers, thereby eliminating the risk of malicious MEV extraction. Recall that Shutter is a threshold encryption scheme, where the secret key is shared among a set of Keypers. Users can encrypt their transactions with Shutter such that the transactions can only be decrypted when a threshold number of Keypers agree to do so. In order to prevent malicious MEV extraction, it is crucial that the decryption only occurs once the execution order is fixed; any premature decryption would expose transaction content and enable transaction reordering for MEV extraction. This is where SSS becomes crucial: If the secret key is shared via an SSS scheme, any attempt by Keypers to decrypt transactions before the execution order is locked can be detected and punished, thereby disincentivizing collusion. We are currently exploring possibilities to integrate a mechanism for anti-collusion into the Shutter protocol.

What About Other Anti-Collusion Mechanisms?

Trusted Execution Environment (TEEs) are often used to mitigate trust assumptions like the one in threshold secret sharing. A TEE is a hardware module designed to ensure a trusted environment for computation, even if the host machine is compromised. As such, TEEs are a powerful and versatile tool with numerous applications, including many that overlap with those of threshold cryptography. In these applications, rather than executing a cryptographic task in a decentralized way as is done in threshold cryptography, the task is executed centrally inside a TEE.

Unfortunately, it is well known that today’s TEEs are not fully secure, as demonstrated by several past attacks (e.g., see the list of past attacks on Intel’s SGX). Even beyond their vulnerabilities, another critical issue arises: inputs and outputs of a TEE are always handled by the potentially corrupted host machine. This creates a serious risk of censorship attacks, where the host could choose to not forward an input to the TEE or refuse to relay the TEE’s output. Lastly, the use of TEEs always requires trust in the hardware manufacturer.

Despite these issues, TEEs pose a promising direction to achieve some form of anti-collusion in the near future, while SSS is still under research. TEEs can serve as a practical stop-gap, providing some security until more mature and scalable SSS schemes are available. Companies like Flashbots and PolyCrypt are actively exploring potential solutions based on TEEs. Notably, PolyCrypt is currently working on integrating TEEs into Shutter to reduce the threshold trust assumption, helping to safeguard against shareholder collusion.

In the long term, however, we envision a combination of SSS and TEEs to obtain the best guarantees possible against colluding shareholders.

It’s worth noting that besides the work on SSS, several other research papers on anti-collusion mechanisms in threshold cryptography have emerged recently (e.g., [1,2,3]). This surge in academic focus highlights the importance of this topic, and with many researchers working in this area, we are optimistic about making significant progress towards a practically efficient anti-collusion mechanism for threshold schemes.

Overcoming the Threshold Assumption for Wide Adoption of MPC and Threshold Cryptography

While the current SSS schemes are more of a feasibility result than fully efficient, deployable solutions, they represent an important step toward solving the critical problem of shareholder collusion in distributed cryptographic protocols. This novel primitive paves the way for a more secure use of threshold cryptography and MPC.

The concept of making collusion provable and punishable is an exciting new direction for the security of decentralized systems, offering potential breakthroughs in privacy, information symmetry, and trust in decentralized environments. For MPC and threshold cryptography projects such as Shutter, SSS provides a glimpse into a future where cryptographic security can be guaranteed in the face of potential collusion.

Now is the time for the MPC and threshold cryptography communities to explore the possibilities of Secret Sharing with Snitching. While not yet fully ready for deployment, SSS holds tremendous potential to enhance the security, privacy, and trustworthiness of your decentralized applications.

Follow us on X-Twitter, visit the Shutter Forum, and join our community on Shutter Discord to learn more about how Shutter works and stay updated on our progress.