Tracing Traitors

  • Benny Chor
  • Amos Fiat
  • Moni Naor
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 839)


We give cryptographic schemes that help trace the source of leaks when sensitive or proprietary data is made available to a large set of parties. This is particularly important for broadcast and database access systems, where the data should be accessible only to authorized users. Such schemes are very relevant in the context of pay television, and easily combine with and complement the Broadcast Encryption schemes of [6].


Hash Function Authorized User Cipher Block Data Supplier Good User 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


  1. 1.
    N. Alon, J. Bruck, J. Naor, M. Naor and R. Roth, Construction of Asymptotically Good Low-Rate Error-Correcting Codes through Pseudo-Random Graphs, IEEE Transactions on Information Theory, vol. 38 (1992), pp. 509–516.CrossRefGoogle Scholar
  2. 2.
    N. Alon and J. Spencer, The Probabilistic Method, Wiley, 1992.Google Scholar
  3. 3.
    J. L. Carter and M. N. Wegman, Universal Classes of Hash Functions, Journal of Computer and System Sciences 18 (1979), pp. 143–154.zbMATHCrossRefMathSciNetGoogle Scholar
  4. 4.
    P. Erdös, P. Frankl, Z. Füredi, Families of finite sets in which no set is covered by the union of r others, Israel J. of math. 51, 1985, pp. 79–89.zbMATHCrossRefGoogle Scholar
  5. 5.
    M. L. Fredman, J. Komlós and E. Szemerédi, Storing a Sparse Table with O (1) Worst Case Access Time, Journal of the ACM, Vol 31, 1984, pp. 538–544.zbMATHCrossRefGoogle Scholar
  6. 6.
    A. Fiat and N. Naor, Broadcast Encryption, Proc. Advances in Cryptology — Crypto’ 93, 1994, pp. 480–491.Google Scholar
  7. 7.
    K. Mehlhorn, Data Structures and Algorithms: Sorting and Searching, Springer-Verlag, Berlin Heidelberg, 1984.zbMATHGoogle Scholar
  8. 8.
    F. J. MacWilliams and N. J. A. Sloane, The theory of error correcting codes, North Holland, Amsterdam, 1977.zbMATHGoogle Scholar
  9. 9.
    M. N. Wegman and J. L. Carter, New Hash Functions and Their Use in Authentication and Set Equality, Journal of Computer and System Sciences 22, pp. 265–279 (1981).zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1994

Authors and Affiliations

  • Benny Chor
    • 1
  • Amos Fiat
    • 2
    • 4
  • Moni Naor
    • 3
  1. 1.Dept. of Computer Science, TechnionHaifaIsrael
  2. 2.Dept. of Computer Science, School of MathematicsTel Aviv UniversityTel AvivIsrael
  3. 3.Dept. of Computer Science and Applied MathWeizmann InstituteRehovotIsrael
  4. 4.Algorithmic Research Ltd.Israel

Personalised recommendations