Detecting collusion among multiple recipients of fingerprinted information Number:7,036,024 from the United States Patent and Trademark Office (PTO) owispatent

Title: Detecting collusion among multiple recipients of fingerprinted information

Abstract: Embedding fingerprinting or watermarking information includes delivering information in-band within digital content representing a media stream, so unauthorized distributors must choose between degrading the media stream, or leaving sufficient information detectable that unauthorized distribution can be detected. For fingerprinting, the method provides a relatively high degree of confidence of both detecting at least one colluding unauthorized distributor, and not falsely accusing any innocent party of being an unauthorized distributor. Embedding fingerprinting or watermarking information includes selecting a sequence of locations within digital content, and embedding information in the form of a sequence of one or more bits at each of those locations, thus representing a set of marking symbols. Marking symbols cannot be readily manufactured without at least one colluding unauthorized distributor having received it, so any distributed digital content includes at least some marking symbols traceable to at least one colluding unauthorized distributor.

Patent Number: 7,036,024 Issued on 04/25/2006 to Watson

---

Inventors:	Watson; Stephen (Toronto, CA)
Assignee:	Kaleidescape, Inc. (Mountain View, CA)
Appl. No.:	378046
Filed:	February 28, 2003

---

Current U.S. Class:	726/22
Current International Class:	G06F 1/24 (20060101)
Field of Search:	713/176 380/201,203

---

Foreign Patent Documents

	WO 2004/070585		Aug., 2004		WO

Other References

Combining digital watermarks and collusion secure fingerprints for customer copy monitoring; Dittmann, J.; Secure Images and Image Authentication (Ref. No. 2000/039), IEE Seminar on, Vol., Iss., 2000; pp.: 6/1-6/6. cited by examiner . Boneh, Dan et al. "Collusion-Secure Fingerprinting for Digital Data." IEEE Transactions on Information Theory, 1998, pp. 1897-1905, vol. 44, No. 5. cited by other.

Primary Examiner: Peeso; Thomas R.
Attorney, Agent or Firm: Swernofsky Law Group PC

---

Claims

---

The invention claimed is:

1. A method, including steps of associating a sequence of marking symbols with digital content, said sequence including information substantially unique to a selected copy of said digital content, at least one marking symbol not included in said sequence not being reliably manufactured without a copy thereof; and asymmetrically distributing information representing said marking symbols among a set of locations for said digital content and generating a set of marked digital content in response thereto, said steps of asymmetrically distributing information not being reliably reversible by a recipient of said marked digital content, whereby said recipient cannot reliably determine said sequence of marking symbols.

2. A method as in claim 1, wherein said digital content represents at least a portion of a media stream.

3. A method as in claim 1, wherein said digital content represents at least a portion of an audio or visual presentation.

4. A method as in claim 1, wherein said information substantially unique to a selected copy of said digital content includes fingerprint information.

5. A method as in claim 1, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique authorized distributor of said digital content.

6. A method as in claim 1, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique authorized redistribution event for said digital content.

7. A method as in claim 1, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique presentation of said digital content.

8. A method as in claim 1, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique presentation of a media stream, said presentation of said media stream including an analog encoding of said digital content.

9. A method as in claim 1, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique presentation of a media stream, said presentation of said media stream including an encoding of said media stream in a form substantially different from said selected copy of said digital content.

10. A method as in claim 1, wherein said information substantially unique to a selected copy of said digital content includes watermark information.

11. A method as in claim 1, wherein said steps of asymmetrically distributing information are not one-to-one.

12. A method as in claim 1, wherein said steps of asymmetrically distributing information place information at a first set of locations for a first said recipient and a second set of locations for a second said recipient, said first set of locations and said second set of locations being substantially distinct.

13. A method as in claim 1, wherein said steps of asymmetrically distributing information include, for at least some locations of said marked digital content, steps of pseudo-randomly selecting at least a portion of said marking symbols to be embedded at said locations.

14. A method as in claim 13, wherein said portion of said marking symbols are individual bits of embedded information.

15. A method as in claim 13, wherein said at least one said portion of said marking symbols defines an individual bit of a representation of at least one of said marking symbols.

16. A method as in claim 1, wherein said steps of asymmetrically distributing information include steps of selecting information to be embedded at locations in digital content, said steps of selecting information being responsive only to substantially local information regarding said locations.

17. A method as in claim 16, wherein a number of locations selected at which to embed a particular bit involved in representing at least one said marking symbol are different for at least two distinct ones of said particular bits.

18. A method as in claim 16, wherein a number of locations selected at which to embed bits involved in representing each said marking symbol is different for at least two distinct ones of said marking symbols.

19. A method as in claim 16, wherein locations selected at which to embed at least one bit involved in representing at least one said marking symbol are pseudo-randomly selected.

20. A method as in claim 1, wherein said steps of asymmetrically distributing information include steps of selecting said set of locations in response to a function which independently assigns each said location to represent a selected portion of one of said sequence of marking symbols.

21. A method as in claim 20, wherein said function includes a function responsive to substantially only an identifier for said location for said digital content.

22. A method as in claim 20, wherein said function includes a function responsive to substantially only local features of said digital content.

23. A method as in claim 1, wherein said steps of asymmetrically distributing information include steps of selecting said set of locations in response to a function which probabilistically assigns each said location to represent a selected portion of one of said sequence of marking symbols.

24. A method as in claim 23, wherein said function includes a function responsive to substantially only an identifier for said location for said digital content.

25. A method as in claim 23, wherein said function includes a function responsive to substantially only local features of said digital content.

26. A method as in claim 23, wherein said probabilistic assignment is responsive to a nonuniform distribution of said marking symbols.

27. A method as in claim 23, wherein said probabilistic assignment is responsive to a fixed distribution of said marking symbols.

28. A method as in claim 23, wherein said selected portion includes more than zero bits of a representation of said one marking symbol.

29. A method as in claim 23, including a second sequential order for said set of locations, said one sequential order and said second sequential order being substantially distinct.

30. A method as in claim 23, wherein said probabilistic assignment is responsive to a uniform distribution of said marking symbols.

31. A method as in claim 23, wherein said probabilistic assignment is responsive to a distribution of said marking symbols, said distribution being substantially identical for each said recipient of said marked digital content.

32. A method, including steps of associating a sequence of marking symbols with digital content for a media stream X, said sequence including information substantially unique to a selected copy of said digital content, at least one marking symbol not included in said sequence not being reliably manufactured without a copy thereof; and distributing information representing said marking symbols among a set of locations for said digital content and generating a set of marked digital content in response thereto, whereby a recipient of said marked digital content cannot reliably determine said sequence of marking symbols, said steps of distributing using O(f(.parallel.X.parallel.)) bits of information, where O(f(.parallel.X.parallel.)) is substantially less than O(.parallel.X.parallel.) as .parallel.X.parallel..fwdarw..infin..

33. A method as in claim 32, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique authorized distributor of said media stream.

34. A method as in claim 32, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique authorized redistribution event for said media stream.

35. A method as in claim 32, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique presentation of said media stream.

36. A method as in claim 32, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique presentation of said media stream, said presentation of said media stream including an analog encoding of said media stream.

37. A method as in claim 32, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique presentation of said media stream, said presentation of said media stream including an encoding of said media stream in a form substantially different from said selected copy of said digital content.

38. A method as in claim 32, wherein said steps of distributing are not one-to-one reversible.

39. A method as in claim 32, wherein said steps of distributing place information at a first set of locations for a first said recipient and a second set of locations for a second said recipient, said first set of locations and said second set of locations being substantially distinct.

40. A method as in claim 32, wherein said steps of distributing include, for at least some locations of said marked digital content, steps of pseudo-randomly selecting at least a portion of said marking symbols to be embedded at said locations.

41. A method as in claim 40, wherein said elements of said marked digital content are individual bits of embedded information.

42. A method as in claim 40, wherein said at least one said portion of said marking symbols defines an individual bit of a representation of at least one of said marking symbols.

43. A method as in claim 32, wherein said steps of distributing include steps of selecting information to be embedded at locations in digital content, said steps of selecting information being responsive only to substantially local information regarding said locations.

44. A method as in claim 43, wherein a number of locations selected at which to embed a particular bit involved in representing at least one said marking symbol are different for at least two distinct ones of said particular bits.

45. A method as in claim 43, wherein a number of locations selected at which to embed bits involved in representing each said marking symbol is different for at least two distinct ones of said marking symbols bits.

46. A method as in claim 43, wherein locations selected at which to embed bits involved in representing at least one said marking symbol are pseudo-randomly selected.

47. A method as in claim 32, wherein said steps of distributing include steps of selecting said set of locations in response to a function which independently assigns each said location to represent a selected portion of one of said sequence of marking symbols.

48. A method as in claim 47, wherein said function includes a function responsive to substantially only an identifier for said location for said digital content.

49. A method as in claim 47, wherein said function includes a function responsive to substantially only local features of said digital content.

50. A method as in claim 32, wherein said steps of distributing include steps of selecting said set of locations in response to a function which probabilistically assigns each said location to represent a selected portion of one of said sequence of marking symbols.

51. A method as in claim 50, wherein said function includes a function responsive to substantially only an identifier for said location for said digital content.

52. A method as in claim 50, wherein said function includes a function responsive to substantially only local features of said digital content.

53. A method as in claim 50, wherein said probabilistic assignment is responsive to a nonuniform distribution of said marking symbols.

54. A method as in claim 50, wherein said probabilistic assignment is responsive to a selected distribution of said marking symbols, said selected distribution being responsive to said information sufficient to identify said recipient.

55. A method as in claim 50, wherein said selected portion includes more than zero bits of a representation of said one marking symbol.

56. A method as in claim 50, including a second sequential order for said set of locations, said one sequential order and said second sequential order being substantially distinct.

57. A method as in claim 50, wherein said probabilistic assignment is responsive to a uniform distribution of said marking symbols.

58. A method as in claim 50, wherein said probabilistic assignment is responsive to a distribution of said marking symbols, said distribution being substantially identical for each said recipient of said marked digital content.

59. A method, including steps of associating a sequence of marking symbols with at least one copy of digital content, said sequence including information substantially unique to each said copy of said digital content, at least one marking symbol not included in said sequence not being reliably manufactured without a copy thereof; examining information representing a particular sequence of marking symbols from among a set of locations for received digital content, and detecting from said information residual information, wherein said steps of examining or said steps of detecting are responsive to asymmetrically distributed information representing said marking symbols associated with at least one said copy of digital content; in response to said residual information, identifying at least one of a set of senders of said digital content, wherein said steps of identifying include a relatively high degree of confidence of identifying at least said one unauthorized distributor while concurrently including a relatively high degree of confidence of not falsely accusing any innocent party of being an unauthorized distributor.

60. A method as in claim 59, wherein said digital content represents at least a portion of a media stream.

61. A method as in claim 59, wherein said digital content represents at least a portion of an audio or visual presentation.

62. A method as in claim 59, wherein said information substantially unique to a selected copy of said digital content includes fingerprint information.

63. A method as in claim 59, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique authorized distributor of said digital content.

64. A method as in claim 59, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique authorized redistribution event for said digital content.

65. A method as in claim 59, wherein said information substantially unique to a selected copy of said digital content includes watermark information.

66. A method as in claim 59, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique presentation of said digital content.

67. A method as in claim 59, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique presentation of a media stream, said presentation of said media stream including an analog encoding of said digital content.

68. A method as in claim 59, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique presentation of a media stream, said presentation of said media stream including an encoding of said digital content in a form substantially different from said selected copy of said digital content.

69. A method as in claim 59, wherein said relatively high degree of confidence exceeds about 99% confidence when an unauthorized distributor has access to less than about 100 copies of said sequences of marking symbols.

70. A method as in claim 59, wherein said steps of detecting residual information are performed separately for each said marking symbol in its place in substantially said sequential order.

71. A method as in claim 59, wherein said steps of examining are performed separately for each said marking symbol in its place in substantially said sequential order.

72. A method as in claim 59, wherein at least one of said steps of examining or said steps of identifying are responsive to a function which probabilistically assigns each said location to represent a selected portion of one of said sequence of marking symbols.

73. A method as in claim 72, wherein said function includes a function responsive to substantially only an identifier for said location for said digital content.

74. A method as in claim 72, wherein said function includes a function responsive to substantially only local features of said digital content.

75. A method as in claim 72, wherein said probabilistic assignment is responsive to a nonuniform distribution of said marking symbols.

76. A method as in claim 72, wherein said probabilistic assignment is responsive to a selected distribution of said marking symbols, said selected distribution being responsive to said information sufficient to identify said at least one of said set of senders of said digital content.

77. A method as in claim 72, wherein said selected portion includes more than zero bits of a representation of said one marking symbol.

78. A method as in claim 72, wherein said probabilistic assignment is responsive to a uniform distribution of said marking symbols.

79. A method as in claim 72, wherein said probabilistic assignment is responsive to a distribution of said marking symbols, said distribution being substantially identical for each said recipient of said marked digital content.

80. A method as in claim 59, wherein at least one of said steps of examining or said steps of identifying include steps of for each said marking symbol, determining whether said residual information indicates the presence, in said sequence of marking symbols of a restricted sequence of said marking symbols, said restricted sequence including at least one location at which one or more such marking symbols are detectable responsive to said residual information; in response to a result of said steps of determining, performing a statistical test for each said marking symbol in said sequence of marking symbols, said statistical test being adapted to identify marking symbols in response to said asymmetrically distributed information representing said marking symbols; in response to a result of said statistical test, identifying a set of senders of said digital content, said set having the property that members are statisfically likely to have sent at least a portion of said digital content and that nonsenders of any portion of said digital content are statistically unlikely to be members of said set of senders.

81. A method as in claim 80, wherein said statistical test includes a measure of likelihood that said marking symbol was derived from at least a portion of said digital content from a member of said set of senders.

82. A method as in claim 80, wherein said statistical test includes a nonuniformly weighted summation responsive to the presence of each said marking symbol in said sequence of marking symbols.

83. A method as in claim 80, wherein said statistical test includes a value responsive to a selected probability of the presence of said marking symbol, the presence of said marking symbols having a nonuniform distribution.

84. A method as in claim 80, wherein said statistical test is responsive to a selected distribution of said marking symbols, said selected distribution being responsive to said information sufficient to identify said recipient.

85. A method as in claim 80, wherein said steps of determining presence are performed separately for each said marking symbol in its place in substantially said sequential order.

86. A method as in claim 80, wherein said steps of performing a statistical test are performed separately for each said marking symbol in its place in substantially said sequential order.

87. A method, including steps of associating a sequence of marking symbols with digital content for a media stream X, said sequence including information substantially unique to a selected copy of said digital content, at least one marking symbol not included in said sequence not being reliably manufactured without a copy thereof; and examining information representing said sequence of marking symbols from among a set of locations for said digital content, and detecting from said set of locations residual information, said steps of examining using O(f(.parallel.X.parallel.)) bits of information, where O(f(.parallel.X.parallel.)) is substantially less than O(.parallel.X.parallel.) as .parallel.X.parallel..fwdarw..infin., wherein said steps of examining or said steps of detecting are responsive to asymmetrically distributed information representing said marking symbols associated with at least one said copy of digital content; in response to said residual information, identifying at least one of a set of senders of said digital content.

88. A method as in claim 87, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique authorized distributor of said media stream.

89. A method as in claim 87, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique authorized redistribution event for said media stream.

90. A method as in claim 87, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique presentation of said media stream.

91. A method as in claim 87, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique presentation of said media stream, said presentation of said media stream including an analog encoding of said media stream.

92. A method as in claim 87, wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify a substantially unique presentation of said media stream, said presentation of said media stream including an encoding of said media stream in a form substantially different from said selected copy of said digital content.

93. A method as in claim 87, wherein said steps of detecting residual information are performed separately for each said marking symbol in its place in substantially said sequential order.

94. A method as in claim 87, wherein said steps of examining are performed separately for each said marking symbol in its place in substantially said sequential order.

95. A method as in claim 87, wherein at least one of said steps of examining or said steps of identifying include steps of selecting said set of locations in response to a function which probabilistically assigns each said location to represent a selected portion of one of said sequence of marking symbols.

96. A method as in claim 95, wherein said function includes a function responsive to substantially only an identifier for said location for said digital content.

97. A method as in claim 95, wherein said function includes a function responsive to substantially only local features of said digital content.

98. A method as in claim 95, wherein said probabilistic assignment is responsive to a nonuniform distribution of said marking symbols.

99. A method as in claim 95, wherein said probabilistic assignment is responsive to a selected distribution of said marking symbols, said selected distribution being responsive to said information sufficient to identify said at least one of said set of senders of said digital content.

100. A method as in claim 95, wherein said selected portion includes more than zero bits of a representation of said one marking symbol.

101. A method as in claim 87, wherein at least one of said steps of examining or said steps of identifying include steps of for each said marking symbol, determining whether said residual information indicates the presence, in said sequence of marking symbols of a restricted sequence of said marking symbols, said restricted sequence including at least one location at which one or more such marking symbols are detectable responsive to said residual information, said steps of determining being responsive to asymmetrically distributed information representing said marking symbols; in response to a result of said steps of determining, performing a statistical test for each said marking symbol in said sequence of marking symbols; in response to a result of said statistical test, identifying a set of senders of said digital content, said set having the property that members are statistically likely to have sent at least a portion of said digital content and that nonsenders of any portion of said digital content are statistically unlikely to be members of said set of senders.

102. A method as in claim 101, wherein said statistical test includes a measure of likelihood that said marking symbol was derived from at least a portion of said digital content from a member of said set of senders.

103. A method as in claim 101, wherein said statistical test includes a nonuniformly weighted summation responsive to the presence of each said marking symbol in said sequence of marking symbols.

104. A method as in claim 101, wherein said statistical test includes a value responsive to a selected probability of the presence of said marking symbol, the presence of said marking symbols having a nonuniform distribution.

105. A method as in claim 101, wherein said statistical test is responsive to a selected distribution of said marking symbols, said selected distribution being responsive to said information sufficient to identify said at least one of said set of senders of said digital content.

106. A method as in claim 101, wherein said steps of determining presence are performed separately for each said marking symbol in its place in substantially said sequential order.

107. A method as in claim 101, wherein said steps of performing a statistical test are performed separately for each said marking symbol in its place in substantially said sequential order.

108. A method, including steps of associating a sequence of marking symbols with at least one copy of digital content, said sequence including information substantially unique to each said copy of said digital content, at least one marking symbol not included in said sequence not being reliably manufactured without a copy thereof; examining information representing a particular sequence of marking symbols from among a set of locations for received digital content, and detecting from said information residual information; in response to said residual information, identifying at least one of a set of unauthorized distributors of said digital content, wherein said steps of identifying include a relatively high degree of confidence of identifying said one unauthorized distributor while concurrently including a relatively high degree of confidence of not falsely accusing any innocent party of being an unauthorized distributor; wherein said information substantially unique to a selected copy of said digital content includes information sufficient to identify at least one of: a substantially unique authorized distributor of said digital content, a substantially unique authorized redistribution event for said digital content, a substantially unique presentation of said digital content.

109. A method, including steps of associating a sequence of marking symbols with at least one copy of digital content, said sequence including information substantially unique to each said copy of said digital content, at least one marking symbol not included in said sequence not being reliably manufactured without a copy thereof; examining information representing a particular sequence of marking symbols from among a set of locations for received digital content, and detecting from said information residual information, said steps of examining being responsive to asymmetrically distributed information representing said marking symbols; in response to said residual information, identifying at least one of a set of unauthorized distributors of said digital content, wherein said steps of identifying include a relatively high degree of confidence of identifying said one unauthorized distributor while concurrently including a relatively high degree of confidence of not falsely accusing any innocent party of being an unauthorized distributor; wherein at least one of said steps of examining or said steps of identifying include steps of for each said marking symbol, determining whether said residual information indicates the presence, in said sequence of marking symbols of a restricted sequence of said marking symbols, said restricted sequence including at least one location at which one or more such marking symbols are detectable responsive to said residual information; in response to a result of said steps of determining, performing a statistical test for each said marking symbol in said sequence of marking symbols; in response to a result of said statistical test, identifying a set of senders of said digital content, said set having the property that members are statistically likely to have sent at least a portion of said digital content and that nonsenders of any portion of said digital content are statistically unlikely to be members of said set of senders.

110. A method, including steps of associating a sequence of marking symbols with digital content for a media stream X, said sequence including information substantially unique to a selected copy of said digital content, at least one marking symbol not included in said sequence not being reliably manufactured without a copy thereof; and examining information representing a particular sequence of marking symbols from among a set of locations for received digital content, and detecting from said information residual information, wherein said steps of examining or said steps of detecting using O(f(.parallel.X.parallel.)) bits of information, where O(f(.parallel.X.parallel.)) is substantially less than O(.parallel.X.parallel.) as .parallel.X.parallel..fwdarw..infin.; in response to said residual information, identifying at least one of a set of senders of said digital content, wherein said steps of identifying include steps of for each said marking symbol, determining whether said residual information indicates the presence, in said sequence of marking symbols of a restricted sequence of said marking symbols, said restricted sequence including at least one location at which one or more such marking symbols are detectable responsive to said residual information; in response to a result of said steps of determining, performing a statistical test for each said marking symbol in said sequence of marking symbols; in response to a result of said statistical test, identifying a set of senders of said digital content, said set having the property that members are statistically likely to have sent at least a portion of said digital content and that nonsenders of any portion of said digital content are statistically unlikely to be members of said set of senders.

---

Description

---

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention relates to distribution of digital content.

2. Related Art

Distribution of digital content for media streams, such as for example movies, is subject to several problems. One problem is that it is easy to make exact copies of digital content, thus allowing any recipient of that content to redistribute it, whether authorized or not. It would be advantageous to be able to distribute digital content, particularly digital content for media streams, without fear of its unauthorized distribution. This would be particularly advantageous when it is desired to distribute digital content using a communication link, such as for example a computer network or other technique for distribution to end viewers (for example, either on demand, in anticipation of future demand, or in response to something else).

One known solution is to mark digital content with a "fingerprint," that is, information sufficient to identify the recipient of the digital content, so that an unauthorized distributor of the content can be determined, thus hopefully deterring potential unauthorized distributors. Other known solutions include marking digital content with a "watermark," that is, information sufficient to identify the digital content itself. Thus for example, if a recipient of the digital content distributes it without authorization, that recipient can be identified and called to account for that activity. However, fingerprinting and watermarking of digital content is subject to attacks by recipients, by which those recipients might be able to erase or alter the fingerprint or watermark, or to otherwise make copies of the digital content from which it is difficult or impossible to determine the unauthorized distributors. Possible attacks include (1) alteration or erasure of the fingerprinting or watermarking information, (2) collusion among multiple recipients to mix fingerprinting or watermarking information together, and (3) combinations of multiple attacks.

Known techniques for countering attacks against fingerprinting information have been directed to detecting colluders. However, such known techniques, to the extent they are effective, are also subject to another important problem--avoiding accusation of innocent recipients. Moreover, such known techniques are relatively ineffective when the number of colluders is more than a few. For example, one known technique can be defeated by as few as 8 10 colluders, even when using millions of bits of embedded fingerprinting or watermarking information.

It would be advantageous to provide a technique by which attacks against fingerprinting and watermarking can be thwarted, with the effect that recipients responsible for distributed digital content can be identified notwithstanding such attacks.

SUMMARY OF THE INVENTION

A method of embedding fingerprinting or watermarking information includes delivering information in-band within digital content representing a media stream, with the effect that unauthorized distributors are forced to choose between (A1) degrading the media stream to no longer be commercially valuable, or (A2) leaving sufficient fingerprinting or watermarking information detectable in the digital content representing the media stream that unauthorized distribution can be detected with a relatively high degree of confidence. In the case of fingerprinting (including when the embedded information in the digital content representing the media stream is sufficient to identify a recipient of the media stream), the method provides relatively high degree of confidence of both (B1) detecting at least one of a team of colluding unauthorized distributors, and (B2) not falsely accusing any innocent party of being an unauthorized distributor.

The method of embedding fingerprinting or watermarking information includes selecting a sequence of locations within digital content representing the media stream, and embedding information in the form of a sequence of one or more bits (or fractions of a bit) at each of those locations, with the effect of representing a set of marking symbols. The embedded information is selected pseudo-randomly, with the effect that the marking symbols cannot readily be manufactured without at least one colluding unauthorized distributor having received that marking symbol. While it is conceivable that a marking symbol could be manufactured without having been received by at least one colluding unauthorized distributor, there is a very small probability of the colluding unauthorized distributors being able to do so, either individually or collectively. This has the effect that any distributed digital content (still having commercial value) includes at least some residual information, with the effect that the digital content would be traceable to at least one of the colluding unauthorized distributors. Probability theory allows the method to identify that residual information, with the effect that the method can identify at least one colluding unauthorized distributor with relative confidence that the identified party is truthfully an unauthorized distributor and not falsely accused.

In one aspect of the invention, symbols are selected pseudo-randomly, in response to pseudo-random functions that need only be statistically pseudo-random, not necessarily cryptographically pseudo-random, but are cryptographically secure against ciphertext-only attacks. For each symbol that might be embedded in the digital content, fingerprinting or watermarking information detected in post-attack digital content is compared with fingerprinting or watermarking information embedded in original digital content. The method performs one or more statistical tests to evaluate whether the embedded symbol from the original digital content is detectable in the post-attack digital content. In one embodiment, the statistical tests include assigning accused distributors a weighted point-count, in response to whether the detected symbol equals the embedded symbol. This has the effect that, in response to a total weighted point-count, it can be determined with relatively high confidence whether an accused distributor is truthfully an unauthorized distributor or not.

In one embodiment, each set of digital content, associated with an identifier n, is assigned a unique sequence of r marking symbols, where r is relatively large, each symbol of which is selected from an alphabet of k possibilities, encoded in a bit sequence P.sub.n(X), where X represents the media stream (such as for example a movie) being watermarked or fingerprinted, and I(X) represents a set of possible locations at which information might be embedded in the digital content representing X. The unique sequence is selected in response to the identifier n, in response to a pseudo-random function R.sub.n( ): r.fwdarw.k, with the effect that the function R.sub.n( ) defines the unique sequence of symbols associated with the identifier n. (The identifier n might identify the sender of the digital content, the recipient thereof, or an individual event such as a selected sender/recipient interaction or a selected presentation of the media stream, such as an individual presentation at a movie theater.) The unique sequence is further encoded within the actual fingerprinting or watermarking information in response to a pseudo-random function p( ): I(X).fwdarw.r(k-1), with the effect that each marking symbol is distributed across a set of bits within P.sub.n(X) that are not readily identifiable by an attacker, with the effect that attackers cannot readily determine if a selected symbol was embedded in the original digital content. The combination of the two functions R.sub.n( ) and p( ) produces a set of embedded fingerprinting or watermarking information, with the effect that recipients of the original digital content cannot readily both remove the embedded information and maintain the quality of the media stream represented by the original digital content.

The invention is not restricted to movies, but is also applicable to other media streams, such as for example animation or sound, as well as to still media, such as for example pictures or illustrations, and to databases and other collections of information.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 shows a block diagram of a system for detecting collusion among multiple recipients of fingerprinted information.

FIG. 2 shows a flow diagram of a method for embedding identifying information in digital content.

FIG. 3 shows a flow diagram of a method for detecting collusion among multiple recipients of fingerprinted information.

INCORPORATED DISCLOSURES

This application claims priority of the following documents, each of which is hereby incorporated by reference as if fully set forth herein. U.S. provisional patent application 60/394,630, filed Jul. 9, 2002, in the name of Michael Malcolm, Stephen Watson, Daniel Collens, and Kevin Hui, titled "Watermarking and Fingerprinting a Movie for Secure Distribution." U.S. provisional patent application 60/394,922, filed Jul. 9, 2002, in the name of Michael Malcolm, Stephen Watson, and Daniel Collens, titled "System Architecture of a System for Secure Distribution of Media." U.S. provisional patent application 60/394,588, filed Jul. 9, 2002, in the name of Michael Malcolm, Stephen Watson, and Daniel Collens, titled "Topology of Caching Nodes in a System for Secure Delivery of Media Content." U.S. patent application Ser. No. 10/356,692, filed Jan. 31, 2003, in the name of Daniel Collens, Stephen Watson, and Michael Malcolm, titled "Parallel Distribution and Fingerprinting of Digital Content". U.S. patent application Ser. No. 10/356,322, filed Jan. 31, 2003, in the name of Stephen Watson, Daniel Collens, and Kevin Hui, titled "Watermarking and Fingerprinting Digital Content Using Alternative Blocks to Embed Information". U.S. patent application Ser. No. 10/377,266, filed Feb. 28, 2003, in the name of the same inventor as this application, titled "Recovering from De-Synchronization Attacks Against Watermarking and Fingerprinting".

These documents are hereby incorporated by reference as if fully set forth herein, and are sometimes referred to herein as the "incorporated disclosures".

Inventions described herein can be used in combination or conjunction with technology described in the incorporated disclosures.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

In the description herein, a preferred embodiment of the invention is described, including preferred process steps and data structures. Those skilled in the art would realize, after perusal of this application, that embodiments of the invention might be implemented using a variety of other techniques not specifically described, without undue experimentation or further invention, and that such other techniques would be within the scope and spirit of the invention.

Lexicography

The general meaning of each of these following terms is intended to be illustrative and in no way limiting. The phrase "media stream" describes information intended for presentation in a sequence, such as motion pictures including a sequence of frames or fields, or such as audio including a sequence of sounds. As used herein, the phrase "media stream" has a broader meaning than the standard meaning for "streaming media," (of sound and pictures that are transmitted continuously using packets and that start to play before all of the content arrives). Rather, as described herein, there is no particular requirement that "media streams" must be delivered continuously. Also as described herein, media streams can refer to other information for presentation, such as for example animation or sound, as well as to still media, such as for example pictures or illustrations, and also to databases and other collections of information. The phrase "digital content" describes data in a digital format, intended to represent media streams or other information for presentation to an end viewer. "Digital content" is distinguished from packaging information, such as for example message header information. For the two phrases "digital content" and "media stream," the former describes a selected encoding of the latter, while the latter describes a result of presenting any encoding thereof. The phrase "embedded information in a media stream" describes information incorporated into a set of digital content representing that media stream, in a form capable of later detection. For example, digital content representing media streams might include embedded information, such that the media streams are still capable of presentation to viewer without substantial change, but in which the embedded information can be recovered by suitable processing of the digital content. The phrase "embedding information in a media stream" describes generating a set of digital content representing that media stream, for which the digital content both represents the streaming media and also includes the embedded information in a form capable of later detection. The phrase "asymmetrically distributing information" describes selecting locations in digital content where embedded information is to be located, where those locations are selected in a manner that there are no particular global requirements regarding the locations selected for each bit of embedded information. For some examples, not intended to be limiting in any way, (1) the number of locations selected at which to embed each bit might be different for distinct bits, (2) the pattern of locations selected at which to embed each bit might be different for distinct bits, (3) the locations at which to embed each bit might be pseudo-randomly selected. The term "watermark" describes a schema for digital content by which information can be embedded into that digital content. In preferred embodiments, as described in related applications, an attacker cannot easily remove the watermark. However, the concept of a watermark as described herein is sufficiently general to include watermarks that are not so resistant to attack, or which use other techniques for embedding information. The term "fingerprint" and the phrase "embedded identifying information" describe sets of information sufficient to identify at least one designated recipient of digital content. In a preferred embodiment, as described in a related application, multiple attackers colluding together cannot easily remove the fingerprint provided by the invention, or prevent at least one of them from being detected as unauthorized distributor of the digital content. However, the concept of the fingerprint as described herein is sufficiently general to include fingerprints that are not so resistant to removal, or do not provide such capability for detecting unauthorized distributors of the digital content, or which use other techniques for embedding information, for detecting the embedded information, or for detecting unauthorized distributors of the digital content. As described in the incorporated disclosure and in related applications, a "watermark" refers to a set of locations in a media stream at which information might be embedded, while a "fingerprint" refers to the actual information that is embedded, such as for example by selecting a block or alt-block for each such location. However, in the context of the invention, there is no requirement that the concepts of watermarking and fingerprinting be so restricted. More generally, a watermark might be used for any technique by which a source of the digital content for the media stream might be identified, or a fingerprint might be used for any technique by which a recipient of the digital content for the media stream might be identified. For example, not intended to be limiting in any way, watermarking and fingerprinting information as described herein includes a representation of the entire path (or set of paths) by which the digital content representing the media stream was sent from its source and received by its end viewer (or equipment associated therewith). The phrase "identifying information" describes, generally, either information associated with a watermark, information associated with a fingerprint, or other information by which authorized or unauthorized distribution of digital content representing a media stream might be identified. The phrase "residual information" describes, generally, any information recoverable from digital content from which at least a portion of the identifying information can be associated with that digital content, even if that digital content has been altered significantly since its original distribution or receipt. The phrase "marking symbol" describes information included as part of the embedded identifying information. In one embodiment, marking symbols are embedded, from which residual information might be recovered even from post-attack digital content. Techniques for selecting and embedding marking symbols are described herein, having the effect that colluding attackers of the digital content must (unless there are a very large number of them) retain sufficient residual information with the effect that at least one of them can be identified with a high degree of confidence, and with the effect that, also with a high degree of confidence, no innocent recipient is falsely identified. The phrases "original movie" and "alt-movie" describe alternative versions of the same media stream, such as one being an original version of that media stream introduced into a system using aspects of the invention, and another being an alternative version of that same media stream generated in response to the original movie. Similarly, the phrases "original block" and "alt-block" describe alternative versions of the same individual block or macroblock within the original movie or alt-movie. As described in a related application, a difference between the original movie and the alt-movie is historical, in that the alt-movie can be substituted for the original movie in nearly every respect. Similarly, a difference between any one original block and its associated alt-block is historical, in that the alt-block can be substituted for the original block in nearly every respect. The phrases "original digital content" and "altered digital content" (or in the latter case, "post-attack digital content") describe digital content representing media streams, in a first format (original digital content) and in a second format (altered digital content), the altered digital content having been produced in response to the original digital content and with the intent of representing substantially similar media streams, but with the effect that detecting identifying information from the original digital content is made relatively difficult. Thus, the altered digital content is a result of a de-synchronization attack on the original digital content. In preferred embodiments, the original digital content might be an actual original of some digital content before it was subject to a de-synchronization attack, or might be a constructed form of digital content, such as in response to an original movie and alt-movie, or in response to a set of original blocks and alt-blocks. For one example, not intended to be limiting in any way, the original digital content might be an average of the original movie and the alt-movie, or there might be two sets of original digital content, one for the original movie and one for the alt-movie. In one embodiment, a typical case of original digital content will include a block-by-block selection from the blocks of the original movie and the alt-movie. However, in the context of the invention, there is no particular restriction to such formats being used or included as the "original digital content" for which resynchronization is sought. Moreover, as described below, numerous variations on this theme are all within the scope and spirit of the invention, and would be workable without undue experimentation or further invention.

The scope and spirit of the invention is not limited to any of these definitions, or to specific examples mentioned therein, but is intended to include the most general concepts embodied by these and other terms.

Notation

The general meaning of following notation is intended to be illustrative and in no way limiting. X the media stream (such as for example a movie) being watermarked or fingerprinted; I(X) the set of possible locations at which bits might be embedded in the watermarked or fingerprinted digital content; n a substantially unique identifier associated with a selected copy of digital content (as noted above, the identifier n might identify the sender of the digital content, the recipient thereof, or an individual event such as a selected sender/recipient interaction or a selected presentation of the media stream, such as an individual presentation at a movie theater); P.sub.n(X): X.fwdarw.{0, 1} the bit sequence associated with the identifier n, which represents the sequence of actual bits of watermark or fingerprint information; P*(X): X.fwdarw.{0, 1} the bit sequence after recovery from alterations made by one or more colluding attackers; r a number of marking symbols embedded in the digital content (that is, the sequence of marking symbols forms a word of length r such symbols); k a number of possibilities in an alphabet of possible marking symbols (in one embodiment, as further described herein, the alphabet of possible marking symbols includes those bit strings having no more than one transition from a logical 0 bit to a logical 1 bit, with the effect that each such marking symbol might be represented by k-1 bits, each of which may be represented by one or more bits in the bit sequence P.sub.n(X)); R.sub.n( ): r.fwdarw.k a pseudo-random function substantially unique to the identifier n, which generates the bit sequence P.sub.n(X); Z a selected symbol which might be selected by R.sub.n( ) from the alphabet of k possibilities; Z* a selected special symbol which might be selected by R.sub.n( ) from the alphabet of k possibilities, such as with a different probability of being selected by R.sub.n( ) than other symbols Z from the alphabet of k possibilities; p( ): I(X).fwdarw.r(k-1) a pseudo-random function which assigns each location within I(X) to represent a selected one of the r marking symbols, and assigns within that marking symbol, one of (k-1) possible bits for representing that marking symbol, with the effect that each selected marking symbol Z has its bits (that is, those bits representing that marking symbol Z) spread among the locations in I(X), with the effect that each of the bits representing the marking symbol Z is assigned to a number of locations (preferably a substantial plurality of locations for each such bit) within I(X), with the effect that attackers cannot readily determine those locations within I(X), and with the effect that attackers cannot readily remove Z or replace Z with a different marking symbol (for one example, the pseudorandom function might be obtained by taking a pseudorandom bijection xi: I(X).fwdarw.r(k-1)J for some set J and then defining pi(i) to be the first two coordinates of xi(i)=(r', k', j), that is (r', k')); B a length of a fixed length marking symbol Z (as described above, in one embodiment, each marking symbol is selected from an alphabet of k possibilities, and each marking symbol selected from the alphabet of k possibilities has a representation using a sequence of k bits, with the effect that B=k for that one embodiment); B* a length of a variable length marking symbol Z; +E a weighted value +E added to a total for a possible attacker if the specific marking symbol Z is present in the post-attack fingerprinting or watermarking information at the r.sup.th position; -F a weighted value -F added to a total for a possible attacker if the specific marking symbol Z is not present in the post-attack fingerprinting or watermarking information at the r.sup.th position; p a probability of a specific marking symbol being a specific selected marking symbol Z.

The scope and spirit of the invention is not intended to be limited in any way by any of these definitions or notations, or to specific examples mentioned therein, but is intended to include the most general concepts embodied by these and other notations.

System Elements

FIG. 1 shows a block diagram of a system for detecting collusion among multiple recipients of fingerprinted information.

A system 100 includes a processor 101, program and data memory or mass storage 102, at least one input element 103, and preferably at least one output element 104.

The memory or mass storage 102 is capable of including instructions 105 capable of being executed or interpreted by the processor 101 to perform steps as described herein.

The memory or mass storage 102 is also capable of receiving copies of at least portions of a set of original digital content 111, and copies of at least portions of a set of watermark or fingerprint information 112 to be impressed on the original digital content 111. Either the entire original digital content 111 and watermark or fingerprint information 112, or comparable portions thereof, might be maintained in the memory or mass storage 102.

The memory or mass storage 102 is also capable of receiving copies of at least portions of a set of post-attack digital content 121 (herein sometimes called "altered" digital content), where the post-attack digital content 121 may have been derived from the digital content 111 by means of an attack on the watermark or fingerprint information 112. Either the entire original digital content 111 and post-attack digital content 121, or comparable portions thereof, might be maintained in the memory or mass storage 102.

In those cases where only comparable portions thereof are maintained in the memory or mass storage 102, the at least one input element 103 preferably includes at least one communication link 106, the communication link 106 being capable of receiving the original digital content 111 and post-attack digital content 112, or portions thereof, and capable of coupling them to the memory or mass storage 102.

As described below, the instructions 105 direct the system 100 to perform the following actions: (A) to generate a set of watermarked or fingerprinted digital content 113 in response to the original digital content 111 and in response to the watermark or fingerprint information 112.

The specific techniques to be applied are further described below.

As described below, the instructions 105 also direct the system 100 to perform the following actions: (B1) to identify post-attack watermark or fingerprint information 122 in response to the post-attack digital content 121, and (B2) to compare that post-attack watermark or fingerprint information 122 with the original watermark or fingerprint information 112 associated with the original digital content 111, with the effect that (B3) the post-attack digital content 121 can be identified as derivative of the original digital content 111, in the case of watermarking information, or (B4) the post-attack digital content 121 can be identified as derivative of at least one specific copy of the original digital content 111, in the case of fingerprinting information.

The specific techniques to be applied are further described below.

In a preferred embodiment, the system 100 uses a method of watermarking and fingerprinting, and a method for identifying watermarking and fingerprinting information, such as for example described in related applications for watermarking digital content ("WATERMARKING AND FINGERPRINTING DIGITAL CONTENT USING ALTERNATIVE BLOCKS TO EMBED INFORMATION"). In a preferred embodiment, the system 100 uses a method of identifying post-attack watermark or fingerprint information, such as for example described in related applications for identifying post-attack watermark or fingerprint information ("RECOVERING FROM DESYNCHRONIZATION ATTACKS AGAINST WATERMARKING AND FINGERPRINTING").

Some specific methods of identifying post-attack watermark or fingerprint information 122, and comparing that post-attack watermark or fingerprint information 122 with original watermark or fingerprint information 112, are further described below.

Method of Operation (Embedding Information)