International Association
for Cryptologic Research

In a traitor tracing system there are $n$ parties and each party holds a secret key. A broadcaster uses an encryption key to encrypt a message $m$ to a ciphertext $c$ so that every party can decrypt~$c$ using its secret key and obtain $m$. Suppose a subset of parties ${\cal J} \subseteq [n]$ combine their secret keys to create a pirate decoder $D(\cdot)$ that can decrypt ciphertexts from the broadcaster. Then it is possible to trace $D$ to at least one member of ${\cal J}$ using only blackbox access to the decoder. Traitor tracing received much attention over the years and multiple schemes have been developed.

In this paper we explore how to do traitor tracing in the context of a threshold decryption scheme. Again, there are $n$ parties and each party has a secret key, but now~$t$ parties are needed to decrypt a ciphertext~$c$, for some $t>1$. If a subset ${\cal J}$ of at least $t$ parties use their secret keys to create a pirate decoder $D(\cdot)$, then it must be possible to trace $D$ to at least one member of ${\cal J}$. This problem has not yet been explored in the literature, however, it has recently become quite important due to the use of encrypted mempools, as we explain in the paper.

We develop the theory of traitor tracing for threshold decryption. While there are several non-threshold traitor tracing schemes that we can leverage, adapting these constructions to the threshold decryption settings requires new cryptographic techniques. We present a number of constructions for traitor tracing for threshold decryption, and note that much work remains to explore the large design space.