Abstract:
We deal with the problem of a center sending a secret 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 suggest an algorithm in this scheme that works for any number of revoked users. To revoke $r$ users the resulting message length is at most $2r$ keys. The storage requirements are $\frac{1}{2} \log^2 N$ where $N$ is the total number of users. We also provide a `tracing' mechanism allowing us to detect the non-compliant devices leaking the keys.