Patent ID: 8495755

Claim:
A method for tracing traitors on distributed files in a broadcast encryption system to prevent content piracy, comprising: constructing candidate coalitions of potential traitors, each of said coalitions having a size of at least two; determining if any of the candidate coalitions cover variations observed in a pirated file distributed by said system; and when 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 file variations that would uniquely identify a single receiver, calculating a minimum number of file variations that the most probable traitor has by applying the ceiling function to: a length of file variations divided by the size of said coalition, and for each combination of possible variations among the of minimum number of file variations, when a particular receiver assigned to that combination covers the min variations then: (a) if said coalition size is one, identify the particular receiver, (b) if said coalition size is greater than one, then: remove covered variations from the particular receiver, decrease size of said coalition by one, and recursively perform said determining on the remaining variations, and selectively continue if said determining checks all combinations and identify the particular receiver and exit if said determining finds a satisfactory coalition, and (c) if all combinations have been checked then exit.