IACR News item: 30 July 2015
Ryo Nishimaki, Daniel Wichs, Mark Zhandry
ePrint ReportIn prior solutions, the users are indexed by numbers $1,\\ldots,N$ and the tracing algorithm recovers the index $i$ of a user in a coalition. Such solutions implicitly require the content distributor to keep a record that associates each index $i$ with the actual identifying information for the corresponding user (e.g., name, address, etc.) in order to ensure accountability. In this work, we construct traitor tracing schemes where all of the identifying information about the user can be embedded directly into the user\'s key and recovered by the tracing algorithm. In particular, the content distributor does not need to separately store any records about the users of the system, and honest users can even remain anonymous to the content distributor.
The main technical difficulty comes in designing tracing algorithms that can handle an exponentially large universe of possible identities, rather than just a polynomial set of indices $i \\in [N]$. We solve this by abstracting out an interesting algorithmic problem that has surprising connections with seemingly unrelated areas in cryptography. We also extend our solution to a full ``broadcast-trace-and-revoke\'\' scheme in which the traced users can subsequently be revoked from the system. Depending on parameters, some of our schemes can be based only on the existence of public-key encryption while others rely on indistinguishability obfuscation.
Additional news items may be found on the IACR news page.