## Cryptology ePrint Archive: Report 2001/059

**Revocation and Tracing Schemes for Stateless Receivers**

*Dalit Naor and Moni Naor and Jeff Lotspiech*

**Abstract: **We deal with the problem of a center sending a message to a group
of users such that 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 case, where the users
do not (necessarily) update their state from session to session.
We present a framework called the Subset-Cover framework,
which abstracts a variety of revocation schemes including some
previously known ones. We provide sufficient conditions that
guarantee the security of a revocation algorithm in this class.

We describe two explicit Subset-Cover revocation algorithms; these
algorithms are very flexible and work for any number of revoked
users. The schemes require storage at the receiver of $\log N$ and
$\frac{1}{2} \log^2 N$ keys respectively ($N$ is the total number
of users), and in order to revoke $r$ users the required message
lengths are of $r \log N$ and $2r$ keys respectively. 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.

The main improvements of these methods over previously suggested
methods, when adapted to the stateless scenario, are: (1) reducing
the message length to $O(r)$ regardless of the coalition
size while maintaining a single decryption at the user's end (2)
provide a seamless integration between the revocation and
tracing so that the tracing mechanisms does not require any change
to the revocation algorithm.

**Category / Keywords: **foundations / broadcast encryption, traitor tracing, key management, multicast, revocation scheme

**Publication Info: **Published in Crypto 2001

**Date: **received 24 Jul 2001, last revised 5 Dec 2001

**Contact author: **dalit at il ibm com

**Available format(s): **PDF | BibTeX Citation

**Version: **20011205:104841 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]