System and method for digitally marking a file

• US 6,434,701 B1
• Filed: 04/06/1999
• Issued: 08/13/2002
• Est. Priority Date: 04/06/1999
• Status: Expired due to Term

• Current Assignee: KWAN Software Engineering Incorporated
• Original Assignee: KWAN Software Engineering Incorporated
• Inventors: Kwan, John Man Kwong
• Primary Examiner(s): Hayes, Gail
• Assistant Examiner(s): DI LORENZO, ANTHONY
• Application Number:
  US09/287,537
• Time in Patent Office: 1,225 Days
• Field of Search: 713/176, 382/194, 382/236, 382/245, 382/239, 382/283
• US Class Current: 713/176
• CPC Class Codes: G11B 20/00086 Circuits for prevention of unauthorised reproduction or copying, e.g. piracy indicating unauthorised use of record carriers in general G11B23/28; scrambling for television signal recording H04N5/913; network architectures or network protocols for network security H04L63/00; cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
• CPC Class Codes: G11B 20/00884 involving a watermark, i.e. a barely perceptible transformation of the original data which can nevertheless be recognised by an algorithm
• CPC Class Codes: H04N 1/32203 Spatial or amplitude domain methods H04N1/32309 takes precedence
• CPC Class Codes: H04N 1/32208 involving changing the magnitude of selected pixels, e.g. overlay of information or super-imposition H04N1/32219, H04N1/32224 take precedence
• CPC Class Codes: H04N 1/32229 with selective or adaptive application of the additional information, e.g. in selected regions of the image H04N1/32213 takes precedence
• CPC Class Codes: H04N 2005/91335 the copy protection signal being a watermark
• CPC Class Codes: H04N 2201/3226 of identification information or the like, e.g. ID code, index, title, part of an image, reduced-size image
• CPC Class Codes: H04N 2201/3233 of authentication information, e.g. digital signature, watermark
• CPC Class Codes: H04N 2201/327 which are undetectable to the naked eye, e.g. embedded codes

Abstract

A system enables encoding of a removable mark into digital data, and decoding of the mark from the digital data. The system comprises an encoder and a decoder. The encoder includes a target area locator for locating in the digital data a flat area having a flatness value n, and includes a marker for using the flatness value n to encode a mark into the flat area. The decoder attempts to extract a mark that includes a plateau and a core from digital data. The decoder includes a mark area locator for using a flatness value n to search digital data for a possible plateau, an unmarker coupled to the flat area locator for decoding a possible core upon locating a possible plateau and for using the flatness value n to replace the possible core with possible original data, and an authenticator coupled to the unmarker for examining the possible core for accuracy.

Claims

1. A method of encoding a mark into digital data, comprising:

locating in digital data a flat area having a flatness value n; and

using the flatness value n to encode a mark into the flat area,

wherein the mark includes a plateau of only zero bits.

2. The method of claim 1, wherein the digital data includes a set of data values of equal length, and the flatness value n is less than or equal to the data value length with n−

1 bits of data changing in the flat area.

3. The method of claim 1, wherein the flat area is at least as long as the mark.

4. The method of claim 2, wherein using the flatness value to encode includes inverting at least the nth least significant bit of each digital data value in the flat area corresponding to a bit in the mark having a value of one.

5. The method of claim 2, wherein using the flatness value to encode includes inverting the n least significant bits of each data value in the flat area corresponding to a bit in the mark having a value of one.

6. The method of claim 2, wherein using the flatness value to encode includes not inverting any bits of each digital data value in the flat area corresponding to a bit in the mark having a value of zero.

7. The method of claim 1, further comprising selecting the lowest possible flatness value n.

8. The method of claim 1, further comprising selecting a predetermined flatness value n.

9. The method of claim 1, further comprising selecting a predetermined portion of the digital data.

10. The method of claim 9, wherein the mark includes a content-identifying value that identifies the content of the digital data portion.

11. The method of claim 10, wherein the content-identifying value is obtained by using an algorithm based on the content of the digital data portion.

12. The method of claim 1, wherein the mark includes a signature.

13. The method of claim 1, further comprising encrypting a value in the mark.

14. The method of claim 1, further comprising obtaining the digital data from a digital input device.

15. The method of claim 7, wherein the mark includes a front plateau, a rear plateau, and a core disposed between the front and rear plateaus.

16. A system for encoding a mark into digital data, comprising:

a target area locator for locating in digital data a flat area having a flatness value n; and

a marker coupled to the flat area locator for using the flatness value n to encode a mark into the flat area,

wherein the mark includes a plateau of only zero bits.

17. The system of claim 16, wherein the digital data includes a set of data values of equal length, and the flatness value n is less than or equal to the data value length with n−

1 bits of data changing in the flat area.

18. The system of claim 16, wherein the flat area is at least as long as the mark.

19. The system of claim 17, wherein the marker inverts at least the nth least significant bit of each digital data value in the flat area corresponding to a bit in the mark having a value of one.

20. The system of claim 17, wherein the marker inverts the n least significant bits of each digital data value in the flat area corresponding to a bit in the mark having a value of one.

21. The system of claim 17, wherein the marker does not invert any bits of each digital data value in the flat area corresponding to a bit in the mark having a value of zero.

22. The system of claim 16, wherein the target area locator uses the lowest possible flatness value n.

23. The system of claim 16, wherein the target area locator uses a predetermined flatness value n.

24. The system of claim 16, further comprising a data portion selector for selecting a predetermined portion of the digital data.

25. The system of claim 24, wherein the mark includes a content-identifying value that identifies the content of the digital data portion.

26. The system of claim 25, further comprising an analyzer for obtaining the content-identifying value by using an algorithm based on the content of the digital data portion.

27. The system of claim 16, wherein the mark includes a signature.

28. The system of claim 16, further comprising an encryptor for encrypting values in the mark.

29. The system of claim 16, further comprising an interface for obtaining the digital data from a digital input device.

30. The system of claim 16, wherein the mark includes a front plateau, a rear plateau, and a core disposed between the front and rear plateaus.

31. A system for encoding a mark into digital data, comprising:

means for locating in digital data a flat area having a flatness value n;

means for using the flatness value n to encode a mark into the flat area, and

wherein the mark includes a plateau of only zero bits.

32. A computer-readable storage medium storing program code for causing a computer to perform the steps of:

locating in digital data a flat area having a flatness value n;

using the flatness value n to encode a mark into the flat area, and

wherein the mark includes a plateau of only zero bits.

33. A method of attempting to extract a mark that includes a plateau and a core from digital data, comprising:

using a flatness value n to search digital data for a plateau;

decoding a candidate core upon locating a plateau;

using the flatness value n to replace the candidate core with candidate original data; and

examining the candidate core for accuracy.

34. The method of claim 33, wherein the digital data includes a set of data values of equal length, and the flatness value n is less than or equal to the data value length with n−

1 bits of data changing in the flat area.

35. The method of claim 33, further comprising selecting the lowest possible flatness value n.

36. The method of claim 33, further comprising selecting a predetermined flatness value n.

37. The method of claim 33, further comprising selecting a predetermined portion of the digital data.

38. The method of claim 33, wherein the length of the plateau is known.

39. The method of claim 33, wherein the plateau should include only zero bits encoded into the digital data.

40. The method of claim 37, wherein the core should include a content-identifying value that identifies the content of the original digital data portion.

41. The method of claim 40, wherein the content-identifying value was obtained by using an algorithm based on the content of the original digital data portion.

42. The method of claim 41, further comprising using the same algorithm to compute a content-identifying value for the digital data after the core has been replaced with candidate original data, and wherein examining the candidate core for accuracy includes comparing the computed content-identifying value against the content-identifying value in the candidate core.

43. The method of claim 34, wherein decoding the candidate core includes comparing a digital data value corresponding to the candidate plateau against a digital data value corresponding to the candidate core.

44. The method of claim 34, wherein using the flatness value n to replace the candidate core includes inverting at least the nth least significant bit of each data value corresponding to each one core bit.

45. The method of claim 34, wherein using the flatness value n to replace the candidate core includes inverting the n least significant bits of each data value corresponding to each one core bit.

46. The method of claim 34, wherein using the flatness value n to replace the candidate core includes not inverting any bits of each data value corresponding to each zero core bit.

47. The method of claim 33, wherein the core includes a signature, and further comprising decoding a candidate signature upon locating the plateau, using the flatness value n to replace the candidate signature with candidate original data, and examining the candidate signature for accuracy.

48. The method of claim 33, further comprising decrypting the core before examining it for accuracy.

49. The method of claim 33, wherein the mark includes a front plateau, a rear plateau, and wherein the core is disposed between the front and rear plateaus.

50. The method of claim 33, further comprising, if the candidate core is inaccurate,

using a flatness value n to search for another plateau;

decoding another candidate core upon locating another plateau;

using the flatness value n to replace the other candidate core with other candidate original data; and

examining the other candidate core for accuracy.

51. A system for attempting to extract a mark that includes a plateau and a core from digital data, comprising:

a mark area locator for using a flatness value n to search digital data for a plateau;

an unmarker coupled to the flat area locator for decoding a candidate core upon locating a plateau, and for using the flatness value n to replace the candidate core with candidate original data; and

an authenticator coupled to the unmarker for examining the candidate core for accuracy.

52. The system of claim 51, wherein the digital data includes a set of data values of equal length, and the flatness value n is less than or equal to the data value length with n−

1 bits of data changing in the flat area.

53. The system of claim 51, wherein the mark area locator selects the lowest possible flatness value n.

54. The system of claim 51, wherein the mark area locator uses a predetermined flatness value n.

55. The system of claim 51, further comprising a data portion selector for selecting a predetermined portion of the digital data.

56. The system of claim 51, wherein the mark area locator knows the length of the plateau.

57. The system of claim 51, wherein the plateau should include only zero bits encoded into the digital data.

58. The system of claim 55, wherein the core includes a content-identifying value that identifies the content of the digital data portion.

59. The system of claim 58, wherein the content-identifying value was obtained by using an algorithm based on the content of the original digital data portion.

60. The method of claim 59, further comprising an analyzer for using the same algorithm to compute a content-identifying value for the digital data after the core has been replaced with candidate original data, and wherein the authenticator compares the computed content-identifying value against the content-identifying value in the candidate core.

61. The system of claim 52, wherein the unmarker compares a digital data value corresponding to the plateau against a digital data value corresponding to the candidate core to decode the candidate core.

62. The system of claim 52, wherein the unmarker inverts at least the nth least significant bit of each data value corresponding to each one core bit to replace the candidate core with candidate original data.

63. The system of claim 52, wherein the unmarker inverts the n least significant bits of each data value corresponding to each one core bit to replace the candidate core with candidate original data.

64. The system of claim 52, wherein the unmarker does not invert any bits of each data value corresponding to each zero core bit to replace the candidate core with candidate original data.

65. The system of claim 51,

wherein the mark includes a signature;

wherein the unmarker decodes a candidate signature upon locating the plateau and uses the flatness value n to replace the candidate signature with candidate original data; and

further comprising a signature matcher for examining the candidate signature for accuracy.

66. The system of claim 51, further comprising a decryptor for decrypting a value in the core before the authenticator examines the core for accuracy.

67. The system of claim 51, wherein the mark includes a front plateau, a rear plateau, and the core is disposed between the front and rear plateaus.

68. The system of claim 51, wherein, if the core is inaccurate,

the mark area locator uses a flatness value n to search for another plateau;

the unmarker decodes another candidate core after the mark area locator locates another plateau;

the unmarker uses the flatness value n to replace the other candidate core with other candidate original data; and

the authenticator examines the other candidate core for accuracy.

69. A system for attempting to extract a mark that includes a plateau and a core from digital data, comprising:

means for using a flatness value n to search digital data for a plateau;

means for decoding a candidate core upon locating a plateau;

means for using the flatness value n to replace the candidate core with candidate original data; and

means for examining the candidate core for accuracy.

70. A computer-readable storage medium storing program code for causing a computer to perform the steps of:

using a flatness value n to search digital data for a plateau;

decoding a candidate core upon locating a plateau;

using the flatness value n to replace the candidate core with candidate original data; and

examining the candidate core for accuracy.