2001 | OriginalPaper | Buchkapitel
Efficient Traitor Tracing Algorithms Using List Decoding
verfasst von : Alice Silverberg, Jessica Staddon, Judy L. Walker
Erschienen in: Advances in Cryptology — ASIACRYPT 2001
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We use powerful new techniques for list decoding error-correcting codes to efficiently trace traitors. Although much work has focused on constructing traceability schemes, the complexity of the tracing algorithm has received little attention. Because the TA tracing algorithm has a runtime of O(N) in general, where N is the number of users, it is inefficient for large populations. We produce schemes for which the TA algorithm is very fast. The IPP tracing algorithm, though less efficient, can list all coalitions capable of constructing a given pirate. We give evidence that when using an algebraic structure, the ability to trace with the IPP algorithm implies the ability to trace with the TA algorithm. We also construct schemes with an algorithm that finds all possible traitor coalitions faster than the IPP algorithm. Finally, we suggest uses for other decoding techniques in the presence of additional information about traitor behavior.