International Association
for Cryptologic Research

One of the main shortcomings of classical distributed cryptography is its reliance on a certain fraction of participants remaining honest. Typically, honest parties are assumed to follow the protocol and not leak any information, even if behaving dishonestly would benefit them economically. More realistic models used in blockchain consensus rely on weaker assumptions, namely that no large coalition of corrupt parties exists, although every party can act selfishly. This is feasible since, in a consensus protocol, active misbehavior can be detected and ``punished'' by other parties. However, ``information leakage'', where an adversary reveals sensitive information via, e.g., a subliminal channel, is often impossible to detect and, hence, much more challenging to handle. A recent approach to address this problem was proposed by Dziembowski, Faust, Lizurej, and Mielniczuk (ACM CCS 2024), who introduced a new notion called \emph{secret sharing with snitching}. This primitive guarantees that as long as no large coalition of mutually trusting parties exists, every leakage of the shared secret produces a ``snitching proof'' indicating that some party participated in the illegal secret reconstruction. This holds in a very strong model, where mutually distrusting parties use an MPC protocol to reconstruct any information about the shared secret. Such a ``snitching proof'' can be sent to a smart contract (modeled as a ``judge'') deployed on the blockchain, which punishes the misbehaving party financially. In this paper, we extend the results from the work of CCS'24 by addressing its two main shortcomings. Firstly, we significantly strengthen the attack model by considering the case when mutually distrusting parties can also rely on a trusted third party (e.g., a smart contract). We call this new primitive \emph{strong} secret sharing with snitching (SSSS). We present an SSSS protocol that is secure in this model. Secondly, unlike in the construction from CCS'24, our protocol does not require the \emph{honest} parties to perform any MPC computations on hash functions. Besides its theoretical interest, this improvement is of practical importance, as it allows the construction of SSSS from any (even very "MPC-unfriendly") hash function.

The fundamental assumption in $t$-out-of-$n$ threshold encryption is that the adversary can only corrupt fewer than $t$ parties. However, this may be unrealistic in practical scenarios where shareholders could have financial incentives to collude. Boneh, Partap, and Rotem (Crypto'24) addressed the case where $t$ or more shareholders collude, adding a traceability mechanism to identify at least one colluder. Their constructions require a trusted dealer to distribute secret shares, but it is unclear how to achieve traceability without this trusted party. Since threshold encryption aims to avoid a single point of failure, a natural question is whether we can construct an efficient, traceable threshold encryption scheme without relying on a trusted dealer. This paper presents two dealerless, traceable threshold encryption constructions by extending the PLBE primitive of Boneh et al. (Eurocrypt'06) and combining it with the silent setup threshold encryption construction of Garg et al. (Crypto'24). Our first construction achieves an amortized ciphertext size of $O(1)$ (for $O(n)$ ciphertexts), and the second achieves constant ciphertext size in the worst case but with a less efficient preprocessing phase. Both have constant secret key sizes and require no interaction between parties. A limitation of Boneh et al.’s constructions is that they only guarantee identifying one colluder, leaving the problem of tracing more traitors unsolved. We address this by applying a technique to our first construction that enables tracing up to $t$ traitors.