Patent ID: 8176568

Claim:
A method for tracing traitors in a broadcast encryption system, comprising: (a) constructing candidate coalitions of potential traitors having a size of T, wherein T is at least two; (b) determining if any of the candidate coalitions cover variations observed in a pirated file; and (c) if a candidate coalition covers variations observed in the pirated file, identifying the candidate coalition as having at least one traitor, wherein said identifying comprises: computing a minimum number of k file variations that would uniquely identify a single receiver, wherein if the product of k and coalition size T is greater than the number of variations then returning an indication that many satisfactory coalitions exist (true result), calculating a minimum number of variations that the most probable traitor has by applying the ceiling function to: a length of variations divided by T, and for each combination of k possible variations, if a particular receiver assigned to that combination covers the min variations then: (i) if the candidate coalition size T is one, then identify the particular receiver and exit (true result), (ii) if coalition size T is greater than one then remove all the covered variations from the particular receiver, decrease the candidate coalition size T by one, and recursively perform said determining on the remaining variations, and selectively: (1) continue if said determining checks all combinations (false result), and (2) identify the particular receiver and exit (true result) if said determining finds a satisfactory coalition (true result), and (iii) if all combinations have been checked then exit (false result).