Copyrighting Public-key Functions and Applications to Black-box Traitor Tracing
Aggelos Kiayias and Moti Yung
Abstract
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
-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 -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.