International Association
for Cryptologic Research

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.