Adaptive Traitor Tracing with Bayesian Networks

Abstract

The practical success of broadcast encryption hinges on the ability to (1) revoke the access of compromised keys and (2) determine which keys have been compromised. In this work we focus on the latter, the so-called traitor tracing problem. We present an adaptive tracing algorithm that selects forensic tests according to the information gain criteria. The results of the tests refine an explicit, Bayesian model of our beliefs that certain keys are compromised. In choosing tests based on this criteria, we significantly reduce the number of tests, as compared to the state-of-the-art techniques, required to identify compromised keys. As part of the work we developed an efficient, distributable inference algorithm that is suitable for our application and also give an efficient heuristic for choosing the optimal test.