Paper 2001/067

An Attack on A Traitor Tracing Scheme

Jeff Jianxin Yan and Yongdong Wu

Abstract

In Crypto'99, Boneh and Franklin proposed a public key traitor tracing scheme~\cite{Boneh}, which was believed to be able to catch all traitors while not accusing any innocent users (i.e., full-tracing and error-free). Assuming that Decision Diffie-Hellman problem is unsolvable in $G_{q}$, Boneh and Franklin proved that a decoder cannot distinguish valid ciphertexts from invalid ones that are used for tracing. However, our novel pirate decoder $P_{3}$ manages to make some invalid ciphertexts distinguishable without violating their assumption, and it can also frame innocent users to fool the tracer. Neither the single-key nor arbitrary pirate tracing algorithm presented in~\cite{Boneh} can identify all keys used by $P_{3}$ as claimed. Instead, it is possible for both algorithms to catch none of the traitors. We believe that the construction of our novel pirate also demonstrates a simple way to defeat some other black-box traitor tracing schemes in general.