White Box Traitor Tracing

Traitor tracing aims to identify the source of leaked decryption keys. Since the "traitor" can try to hide their key within obfuscated code in order to evade tracing, the tracing algorithm should work for general, potentially obfuscated, decoder programs. In the setting of such general decoder programs, prior work uses black box tracing: the tracing algorithm ignores the implementation of the decoder, and instead traces just by making queries to the decoder and observing the outputs.

We observe that, in some settings, such black box tracing leads to consistency and user privacy issues. On the other hand, these issues do not appear inherent to white box tracing, where the tracing algorithm actually inspects the decoder implementation. We therefore develop new white box traitor tracing schemes providing consistency and/or privacy. Our schemes can be instantiated under various assumptions ranging from public key encryption and NIZKs to indistinguishability obfuscation, with different trade-offs. To the best of our knowledge, ours is the first work to consider white box tracing in the general decoder setting.

How to white box trace general adversarial decoders?

Remark 1. An early model for traitor tracing, which we will call faked key tracing, stipulates that the traitor outputs an actual valid key for the system. Tracing then uses the combinatorial or algebraic structure of the key, as opposed to its input/output behavior. Many early traitor tracing works consider faked key tracing [KD98, BF99, NP01, KY03, TS06, JKL09, JKL09, ADVW13], and some refer to this model as "white box tracing" or "non-black box tracing" (see, e.g. [NDC + 15] and [GNPT13], respectively). Such naming reflects that non-black box tracing algorithms have always coincided with tracing models where the traitor must output a valid key. Outside of traitor tracing, however, the labels "white box" or "non-black box" refer to the type of access to a program, and is potentially orthogonal to the format of the program. We therefore prefer the terms "faked key" versus "general decoder" to refer to the structure of the adversary's decoder, and terms "black box" versus "white box" to refer to the level of access the tracing algorithm has to the decoder. To the best of our knowledge, ours is the first work exploring white box tracing in the general decoder setting.

To motivate white box tracing, we now discuss limitations of black box tracing; overcoming these limitations will be the focus of our work. These limitations are orthogonal to the "usual" goal of traitor tracing, namely minimizing parameter sizes. As such, parameter sizes are only a secondary consideration in this work.

We first motivate a particular type of traitor tracing which has both public tracing and embedded identities. Embedded identities, originally proposed by Nishimaki et al. [NWZ16], means that arbitrary information can be embedded in the secret keys; in contrast, most tracing schemes only embed an index from a polynomial-sized set. Nishimaki et al. point out that the tracer would naturally want to know useful identifying information about the traitor, in order to prosecute or fine. The key issuer could of course maintain a database mapping user indices to actual identifying information, but having to store such a database in the clear naturally creates privacy concerns. Embedded identities allow this information to be stored directly in the issued keys themselves, eschewing the need for such a database. For public tracing, the tracing algorithm only needs the public key and no secrets. This is in contrast to secret tracing, where a secret key is required to trace, and anyone with the secret key can break the security of the system. There are at least a few reasons to prefer public tracing algorithms:

• Secret key tracing means the tracer cannot be compromised. Public key tracing allows anyone to trace, removing a potential point of failure.

• As explained in [Pfi96], private tracing provides no natural mechanism for submitting evidence to a judge, as there is no way besides revealing the secret tracing key to certify the results of tracing. While there are solutions in the secret tracing setting, public tracing automatically solves the problem: the judge can always verify by simply re-tracing with the public key.

• In private key tracing, the tracer must somehow discover the decoder in order to trace, and deterrence therefore relies on such discovery. It may take time for the tracer to discover the