Adaptive Traitor Tracing with Bayesian Networks

Philip Zigoris, Hongxia Jin

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 \emph{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.

Subjects: 1.5 Diagnosis; 3.4 Probabilistic Reasoning

Submitted: Apr 3, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.