Systems for fingerprinting digital data

• US 20050111695A1
• Filed: 12/22/2004
• Published: 05/26/2005
• Est. Priority Date: 10/28/1999
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yacobi, Yacov
• Granted Patent: US 7,158,655 B2
• Time in Patent Office: Days
• 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 for detecting a fingerprinting word is configured to receive a protected object that has embedded therein a fingerprinting word that contains a plurality of spread spectrum chips that are arranged in individual blocks that define individual spread sequences. The system processes the protected object sufficient to identify an entity that is associated with the fingerprinting word and which comprises a potential colluder. The system is configured to process the protected object by calculating a weight for each block and restricting the weights of certain blocks to a predetermined value.

Claims

1. A system for detecting a fingerprinting word comprising:

means for receiving a protected object that has embedded therein a fingerprinting word that contains a plurality of spread spectrum chips that are arranged in individual blocks that define individual spread sequences; and

means for processing the protected object sufficient to identify an entity that is associated with the fingerprinting word, said entity comprising a potential colluder, wherein said means for processing comprises;

means for calculating a weight for each block; and

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

2. The system of claim 1, wherein said means for calculating comprises means for determining the weight of a block relative to the Is complement of an original spread sequence block value.

3. The system of claim 1, wherein said means for calculating comprises means for determining the weight of a block relative to the is complement of 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.

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

5. The system of claim 1, 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/e),

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

),

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

),

δ

=f/{square root}(d/2),

μ

=d/2.

6. The system of claim 1, 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.

7. The system of claim 6, wherein said means for determining comprises:

means for evaluating the weight of each block; and

means for selecting a Γ

-symbol if the weight of the blocks satisfies a predefined relationship.

8. A computer-readable medium having computer-executable instructions thereon which, when executed by a computer implement the system of claim 1.

9. A computer-readable medium having computer-executable instructions thereon which, when executed by a computer implement the system of claim 2.

10. A computer-readable medium having computer-executable instructions thereon which, when executed by a computer implement the system of claim 3.

11. A computer-readable medium having computer-executable instructions thereon which, when executed by a computer implement the system of claim 4.

12. A computer-readable medium having computer-executable instructions thereon which, when executed by a computer implement the system of claim 5.

13. A computer-readable medium having computer-executable instructions thereon which, when executed by a computer implement the system of claim 6.

14. A computer-readable medium having computer-executable instructions thereon which, when executed by a computer implement the system of claim 7.