Revocation and Tracing Schemes for Stateless
Receivers
Dalit Naor Moni Naor
Jeff Lotspiech
Abstract:
We address the problem of a Center sending a message to a group of users
where some subset of the users is considered revoked and should not be
able to obtain the content of the message. We concentrate on the stateless
receiver/user case, where the users do not (necessarily) update their state
from session to session. This scenario is particularly applicable for Copyright
Protection for media devices.
We present a framework called the Subset-Cover framework, which
abstracts a variety of revocation schemes and suggest two new algorithms
in this framework. These algorithms are very flexible and work for any
number of revoked users. We also provide a general traitor tracing mechanism
that can be integrated with any Subset-Cover revocation scheme that satisfies
a ``bifurcation property.'' This mechanism does not need an a priori bound
on the number of traitors and does not expand the message length by much
compared to the revocation of the same set of traitors.
These methods improve upon previously suggested ones, when adopted to
the stateless scenario, by: (1) reducing the message length to O(r) regardless
of the coalition size (r is the number of revoked users) while maintaining
a single decryption at the user's end (2) providing a seamless integration
between the revocation and tracing so that the tracing mechanism does not
require any change to the revocation algorithm.
We also give a rigorous treatment of the security of such schemes, identifying
the effect of parameter choice on the overall security of the scheme.
Postscript
,
gzipped
Postscript.
Slides of talk on the subject: ppt
Related On-Line Papers:
-
Dalit Naor,
Moni Naor, Protecting Cryptographic Keys:
The Trace and
Revoke Approach,
Abstract,
Postscript,
gzipped Postscript.
-
Cynthia Dwork, Jeff Lotspiech and Moni Naor, Digital Signets: Self-Enforcing
Protection of Digital Information,
Abstract
,
Postscript,
gzipped
Postscript
-
Amos Fiat and Moni Naor, Broadcast Encryption,
Abstract,
Postscript,
gzipped
Postscript.
-
Moni Naor and Benny Pinkas, Threshold Traitor Tracing, Crypto
98. Postscript,
gzipped
Postscript
-
Benny Chor, Amos Fiat, Moni Naor and Benny Pinkas, Tracing
Traitors , IEEE Transactions on Information Theory, Vol. 46(3), pp.
893-910, 2000.
Postscript
-
Moni Naor and Benny Pinkas, Efficient Trace and Revoke Schemes,
FC'2000. Postscript,
gzipped
Postscript
Back
to On-Line Publications
Back Home