Breaking and Repairing Asymmetric Public-Key Traitor Tracing

Traitor tracing schemes are a very useful tool for preventing piracy in digital content distribution systems. A traitor tracing procedure allows the system-manager to reveal the identities of the subscribers that were implicated in the construction of a pirate-device that illegally receives the digital content (called traitors). In an important variant called “asymmetric ” traitor tracing, the system-manager is not necessarily trusted, thus the tracing procedure must produce undeniable proof of the implication of the traitor subscribers. This non-repudiation property of asymmetric schemes has the potential to significantly increase the effectiveness of the tracing procedure against piracy. In this work, we break the two previous proposals for efficient asymmetric public-key traitor tracing, by showing how traitors can evade the proposed traitor tracing procedures. Then, we present a new efficient Asymmetric Public-Key Traitor Tracing scheme for which we prove its traceability in detail (in the non-black-box model); to the best of our knowledge this is the first such scheme. Our system is capable of proving the implication of all traitors that participate in the construction of a pirate-key. We note that even though we break th