Efficient Trace and  Revoke Schemes

 Moni Naor and Benny Pinkas


Our goal is to design encryption schemes for mass distribution of data in which it is possible to:
  1. (1) deter users from leaking their personal keys
  2. (2) trace which users leaked keys to construct an illegal decryption device
  3. (3) revoke these keys as to render the device dysfunctional.

We start by designing an efficient revocation scheme,  based on secret sharing.  It can remove up to t parties and is secure against coalitions of size t. The performance of this scheme is more efficient than that of previously proposed schemes with the same properties. We then show how to combine the revocation scheme with traitor tracing and self enforcement schemes. More precisely, how to construct schemes such that

  1. (1) Each user's personal key contains some sensitive information of that user (e.g., the user's credit card number), and therefore users would be reluctant o disclose their keys.
  2. (2) An illegal decryption device discloses the identity of users that contributed keys to construct the device.
  3. (3) it is possible to revoke the keys of corrupt users. For this point it is important to be able to do so without publicly disclosing the sensitive information.

Postscript, gzipped Postscript.

Related On-Line Papers:

Back to On-Line Publications

Back Home