Public Key Trace and Revoke Scheme Secure against Adaptive Chosen Ciphertext Attack

  • Yevgeniy Dodis
  • Nelly Fazio
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2567)


A (public key) Trace and Revoke Scheme combines the functionality of broadcast encryption witht he capability of traitor tracing. Specifically, (1) a trusted center publishes a single public key and distributes individual secret keys to the users of the system; (2) anybody can encrypt a message so that all but a specified subset of “revoked” users can decrypt the resulting ciphertext; and (3) if a (small) group of users combine their secret keys to produce a “pirate decoder”, the center can trace at least one of the “traitors” given access to this decoder. We construct the first chosen ciphertext (CCA2) secure Trace and Revoke Scheme based on the DDH assumption. Our scheme is also the first adaptively secure scheme, allowing the adversary to corrupt players at any point during execution, while prior works (e.g., [14]

Of independent interest, we present a slightly simpler construction that shows a “natural separation” between the classical notion of CCA2- security and the recently proposed [15]


  1. [1]
    J.H. An, Y. Dodis, and T. Rabin. On the Security of Joint Signature and Encryption. In Advances in Cryptology-EuroCrypt’ 02, pages 83–107, Berlin, 2002. Springer-Verlag. LNCS 2332. 100, 101, 103, 104Google Scholar
  2. [2]
    M. Bellare, A. Desai, E. Jokipii, and P. Rogaway. A Concrete Security Treatment of Symmetric Encryption: Analysis of the DESModes of Operation. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science-FOCS’ 97, pages 394–403, 1997. 104Google Scholar
  3. [3]
    D. Boneh. The Decision Diffie-Hellman Problem. In Algorithmic Number Theory-ANTS-III, pages 48–63, Berlin, 1998. Springer-Verlag. LNCS 1423. 102CrossRefGoogle Scholar
  4. [4]
    B. Chor, A. Fiat, and N. Naor. Tracing Traitors. In Advances in Cryptology-Crypto’ 94, pages 257–270, Berlin, 1994. Springer-Verlag. LNCS 839. 102Google Scholar
  5. [5]
    R. Cramer and V. Shoup. A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack. In Advances in Cryptology-Crypto’ 98, pages 13–25, Berlin, 1998. Springer-Verlag. LNCS 1462. 101, 105, 107, 108, 111CrossRefGoogle Scholar
  6. [6]
    R. Cramer and V. Shoup. Design and Analysis of Practical Public-Key Encryption Scheme Secure against Adaptive Chosen Ciphertext Attack. Manuscript, 2001. 101, 103, 105, 107, 108, 111, 112Google Scholar
  7. [7]
    Y. Dodis and N. Fazio. Public Key Trace and Revoke Scheme Secure against Adaptive Chosen Ciphertext Attack. Full version of this paper, available at, 2002. 100, 107, 110, 111, 113, 114
  8. [8]
    A. Fiat and M. Naor. Broadcast Encryption. In Advances in Cryptology-Crypto’ 93, pages 480–491, Berlin, 1993. Springer-Verlag. LNCS 773. 100Google Scholar
  9. [9]
    E. Gafni, J. Staddon, and Y. L. Yin. Efficient Methods for Integrating Traceability and Broadcast Encryption. InAdvances in Cryptology-Crypto’ 99, pages 372–387, Berlin, 1999. Springer-Verlag. LNCS 1666. 102Google Scholar
  10. [10]
    A Garay, J. Staddon, and A. Wool. Long-Lived Broadcast Encryption. In Advances in Cryptology-Crypto 2000, pages 333–352, Berlin, 2000. Springer-Verlag. LNCS 1880. 100CrossRefGoogle Scholar
  11. [11]
    D. Halevy and A. Shamir. The LSD Broadcast Encryption Scheme. In Advances in Cryptology-Crypto’ 02, pages 47–60, Berlin, 2002. Springer-Verlag. LNCS 2442. 100Google Scholar
  12. [12]
    M. Luby and J. Staddon. Combinatorial Bounds for Broadcast Encryption. In Advances in Cryptology-EuroCrypt’ 98, pages 512–526, Berlin, 1998. Springer-Verlag. LNCS 1403. 100CrossRefGoogle Scholar
  13. [13]
    D. Naor, M. Naor, and J. Lotspiech. Revocation and Tracing Schemes for Stateless Receivers. In Advances in Cryptology-Crypto’ 01, pages 41–62, Berlin, 2001. Springer-Verlag. LNCS 2139. 100, 101Google Scholar
  14. [14]
    M. Naor and B. Pinkas. Efficient Trace and Revoke Schemes. In Financial Cryptography-FC 2000, pages 1–20, Berlin, 2000. Springer-Verlag. LNCS 1962. 100, 101, 102, 105CrossRefGoogle Scholar
  15. [15]
    V. Shoup. A Proposal for an ISO Standard for Public-Key Encryption. Manuscript, 2001. 100, 101, 103Google Scholar
  16. [16]
    W.G. Tzeng and Z. J. Tzeng. A Public-Key Traitor Tracing Scheme with Revocation Using Dynamics Shares. In Public Key Cryptography-PKC’ 01, pages 207–224, Berlin, 2001. Springer-Verlag. LNCS 1992. 100, 101, 102, 105, 107Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Yevgeniy Dodis
    • 1
  • Nelly Fazio
    • 1
  1. 1.Computer Science DepartmentNew York UniversityUSA

Personalised recommendations