Paper 2006/458

Copyrighting Public-key Functions and Applications to Black-box Traitor Tracing

Aggelos Kiayias and Moti Yung


Copyrighting a function is the process of embedding hard-to-remove marks in the function's implementation while retaining its original functionality. Here we consider the above problem in the context of public-key encryption and we parallel the process of copyrighting a function to the process of designing traitor tracing schemes. We derive two copyrighted public-key encryption functions for the $2$-key setting, solving an open question left by earlier work with respect to copyrighting discrete-logarithm based functions. We then follow a modular design approach and show how to elevate the $2$-key case to the multi-user setting, employing collusion secure codes. Our methodology provides a general framework for constructing public-key traitor tracing schemes that has the interesting property that the transmission rate remains constant if the plaintext size can be calibrated to reach an appropriate minimal length. Achieving a constant rate, i.e., constant expansion in the size of ciphertexts and keys, is an important open problem in the area of traitor tracing schemes. Our design shows how one can solve it for settings that accommodate the required plaintext calibration (e.g., when a bulk of symmetric cipher keys can be encrypted in one message). Our constructions support ``black-box traitor tracing'', the setting  where the tracer only accesses the decryption box in input/output queries/responses. For the first time here we provide a modeling of black-box traitor tracing that takes into account adversarially chosen plaintext distributions, a security notion we call {\em semantic black-box traceability}. In order to facilitate the design of schemes with semantic black-box traceability we introduce as part of our modular design approach a simpler notion called semantic user separability and we show that  this notion implies semantic black-box traceability. In the multi-user setting our constructions also demonstrate how one can derive public-key traitor tracing by reducing the required ``marking assumption'' of collusion-secure codes to cryptographic hardness assumptions.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Preliminary version appeared in Eurocrypt 2002
traitor tracing
Contact author(s)
aggelos @ cse uconn edu
2006-12-04: revised
2006-12-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aggelos Kiayias and Moti Yung},
      title = {Copyrighting Public-key Functions and Applications to Black-box Traitor Tracing},
      howpublished = {Cryptology ePrint Archive, Paper 2006/458},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.