Systems for fingerprinting digital data

• US 7,200,244 B2
• Filed: 12/22/2004
• Issued: 04/03/2007
• Est. Priority Date: 10/28/1999
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yacobi, Yacov
• Primary Examiner(s): Mehta; Bhavesh M.
• Assistant Examiner(s): LAVIN, CHRISTOPHER L
• Application Number:
  US11/021,192
• Publication Number:
  US 20050117777A1
• Time in Patent Office: 832 Days
• Field of Search: None
• US Class Current: 382/100
• CPC Class Codes: G06T 1/005 Robust watermarking, e.g. average attack or collusion attack resistant
• CPC Class Codes: G06T 2201/0051 Embedding of the watermark in the spatial domain
• CPC Class Codes: G06T 2201/0061 Embedding of the watermark in each block of the image, e.g. segmented watermarking
• CPC Class Codes: G06T 2201/0063 in relation to collusion attacks, e.g. collusion attack resistant
• CPC Class Codes: H04N 1/32101 Display, printing, storage or transmission of additional information, e.g. ID code, date and time or title
• CPC Class Codes: H04N 2201/3235 Checking or certification of the authentication information, e.g. by comparison with data stored independently
• CPC Class Codes: H04N 2201/3236 Details of authentication information generation

Abstract

Systems for fingerprinting digital data are described. In one embodiment, a system is configured to form a Γ code by defining a plurality of fingerprinting words. Each fingerprinting word is unique and contains at least one spread sequence. Each fingerprinting word contains a plurality of Γ-symbols, each Γ-symbol containing 2c−1 spread sequences, where c is the number of colluders that are desired to be defended against. The fingerprinting words are structured to permit a collusion analysis to ascertain identities of potential colluders who change an associated fingerprinting word. The individual fingerprinting words are assigned to individual respective entities who constitute potential colluders and serve to identify an entity to which it is assigned.

Claims

1. A system for forming a Γ

code comprising;

means for defining a plurality of fingerprinting words, each fingerprinting word being unique and containing at least one spread sequence, wherein each fingerprinting word contains a plurality of Γ

-symbols, each Γ

-symbol containing 2c−

1 spread sequences, where c is the number of colluders that are desired to be defended against, said fingerprinting words being structured to permit a collusion analysis to ascertain identities of potential colluders who change an associated fingerprinting word; and

means for assigning individual fingerprinting words to individual respective entities who constitute potential colluders, the fingerprinting words serving to identify an entity to which it is assigned.

2. A system for protecting an object comprising:

means for defining a plurality of fingerprinting words, each fingerprinting word being unique and containing at least one spread sequence, said fingerprinting words being structured to permit a collusion analysis to ascertain identities of potential colluders who change an associated fingerprinting word, wherein the fingerprinting words each comprise a plurality of spread sequences, wherein the spread sequences for each fingerprinting word are arranged in individual blocks,

means for assigning individual fingerprinting words to individual respective entities, the fingerprinting words serving to identify an entity to which it is assigned, said entities comprising potential colluders;

means for embedding a plurality of objects with a respective individual fingerprinting word to provide individual protected objects;

means for distributing the protected objects to the individual entities;

means for receiving a protected object; and

means for processing the protected object sufficient to identify an entity that is associated with a fingerprinting word that is contained by the received protected object, said means for processing comprising;

means for calculating a weight for each block, wherein said means for calculating comprises means for determining a weight of a block relative to an original spread sequence block value in accordance with the following equation;

Let x∈

{1, −

1} and y∈

{0, 1, −

1};

f(y, x)=1 if x is not equal to y, and y is not equal to 0, 0 Otherwise,

Let X=(x₁, . . . , x_d) where x_i∈

{1, −

1} and Y=(y₁, . . . , y_d) where y_i∈

{1, −

1, 0}. The weight of Y relative to X is w(Y, X)—

which is the sum from i=1 to d of f(y_i, x_i), where “

d”

is the number of chips in each block; and

means for restricting the weights of certain blocks to a predetermined value.

3. The system of claim 2, wherein said means for restricting comprises means for doing so if a block is likely unseen.

4. The system of claim 2, wherein the predetermined value is equal to(1-δ

)μ

, where;

For N users, and to defend against a collusion of size c, with error probability ε

, select the following;

Number of Γ

-symbols per a fingerprint word=L=2cln(2N/ε

),

Block size (measured in chips)=d=8c²ln(8cL/ε

),

f=2ln(4c²ln(2N/ε

)/ε

),

δ

=f/√

(d/2),

μ

=d/2.

5. The system of claim 2, wherein the embedded fingerprinting word has a plurality of Γ

-symbols each of which comprise a plurality of blocks, and wherein each of a plurality of entities are assigned unique fingerprinting words having a plurality of Γ

-symbols, said means for processing comprising;

for each Γ

-symbol of the embedded fingerprinting word, means for determining a set of one or more likely colors that might be the subject of a collusion;

for each of the entities'"'"' fingerprinting words, means for evaluating each Γ

-symbol to ascertain whether it coincides with a color in the set for the corresponding Γ

-symbol of the embedded fingerprinting word; and

means for selecting an entity that has the largest number of colors.

6. A system for protecting objects containing digital data comprising:

means for defining a plurality of unique fingerprinting words, each fingerprinting word comprising at least one spread sequence, said fingerprinting words being structured to permit a collusion analysis to ascertain identities of potential colluders who change an associated fingerprinting word, wherein said defining comprises defining each fingerprinting word to contain a plurality of Γ

-symbols, each Γ

-symbol containing a plurality of spread sequences and each fingerprinting word contains the same number of Γ

-symbols, wherein each Γ

-symbol contains 2c−

1 spread sequences, where c is the number of colluders that are desired to be defended against;

means for associating each fingerprinting word with an individual entity who can constitute a potential colluder;

means for embedding a plurality of objects containing digital data with an individual fingerprinting word to provide protected objects; and

means for distributing the protected objects to the individual entities.

7. A system for protecting an object comprising:

means for defining a plurality of fingerprinting words, each fingerprinting word being unique and containing at least one spread sequence, said fingerprinting words being structured to permit a collusion analysis to ascertain identities of potential colluders who change an associated fingerprinting word, wherein the fingerprinting words each comprise a plurality of spread sequences, wherein the spread sequences for each fingerprinting word are arranged in individual blocks,

means for assigning individual fingerprinting words to individual respective entities, the fingerprinting words serving to identify an entity to which it is assigned, said entities comprising potential colluders;

means for embedding a plurality of objects with a respective individual fingerprinting word to provide individual protected objects;

means for distributing the protected objects to the individual entities;

means for receiving a protected object; and

means for processing the protected object sufficient to identify an entity that is associated with a fingerprinting word that is contained by the received protected object, said means for processing comprising;

means for calculating a weight for each block; and

means for restricting the weights of certain blocks to a predetermined value, wherein the predetermined value is equal to(1-δ

)μ

,

where;

For N users, and to defend against a collusion of size c, with error probability ε

, select the following;

Number of Γ

-symbols per a fingerprint word=L=2cln(2N/ε

),

Block size (measured in chips)=d=8c²ln(8cL/ε

),

f=2ln(4c²ln(2N/ε

)/ε

),

δ

=f/√

(d/2),

μ

=d/2.

8. A system for protecting an object comprising:

means for defining a plurality of fingerprinting words, each fingerprinting word being unique and containing at least one spread sequence, said fingerprinting words being structured to permit a collusion analysis to ascertain identities of potential colluders who change an associated fingerprinting word, wherein the fingerprinting words each comprise a plurality of spread sequences, wherein the spread sequences for each fingerprinting word are arranged in individual blocks,

means for assigning individual fingerprinting words to individual respective entities, the fingerprinting words sewing to identify an entity to which it is assigned, said entities comprising potential colluders;

means for embedding a plurality of objects with a respective individual fingerprinting word to provide individual protected objects;

means for distributing the protected objects to the individual entities;

means for receiving a protected object; and

means for processing the protected object sufficient to identify an entity that is associated with a fingerprinting word that is contained by the received protected object, said means for processing comprising;

means for calculating a weight for each block; and

means for restricting the weights of certain blocks to a predetermined value, wherein said means for restricting comprises means for doing so if a block is likely unseen.