An improved public-key tracing scheme with sublinear ciphertext size

To overcome the piracy problem in digital content distribution systems, a number of traitor tracing schemes have been suggested by researchers. The goal of these schemes is to enable the tracer to identify at least one of the traitors. In this context, Matsushita and Imai (2004) proposed a black-box tracing scheme with sublinear header size that is able to perform tracing of self-defensive pirate decoders. Kiayias and Pehlivanoglu (2009) proved that this scheme is vulnerable to an attack which allows an illicit decoder to recognize normal ciphertext to tracing ones and distinguish two consecutive tracing ciphertexts. For making the scheme no more susceptible to such attack, authors modified the encryption phase and assumed that traitors belong to the same user group. In this paper, we present a solution that has no traitors restrictions, repairing the scheme totally. In particular, we modified the tracing scheme proving that (a) a pirate decoder is not able to recognize normal ciphertext to tracing ones with sufficiently high probability, and (b) the statistical distance between two consecutive tracing operations is negligible under Decision Diffie Hellman assumption.