Analysis of Set-cover traitor tracing scheme

In this paper, we report our work to analyze the false positive of the Set-cover probabilistic traitor tracing scheme. The Set-cover scheme was proposed to trace a coalition of traitors simultaneously. Comparing with most tracing schemes, the Set-cover scheme identifies more traitors per tracing. The authors of Set-cover scheme claimed their scheme greatly reduced the false positive and increased the tracing efficiency. They also claimed the Set-cover scheme is a good candidate to replace the tracing scheme used in the standard AACS (Advanced Access Content System). However, we present an Enclosure attack to challenge the Set-cover scheme. With the attack we can frame multi innocent users at one time with unnegligible probability no matter how many movies are detected, namely, the false positive of Set-cover scheme is much higher than the authors claimed. Both of our theoretical results and experimental results show that 39 arbitrary users can successfully frame 7 users with a probability bigger than 80%, which means the false positive is bigger than 80%. Obviously, such a false positive is too high to be applied in practice.