Systems and methods for embedding messages in look-up tables

• US 7,558,961 B2
• Filed: 04/21/2005
• Issued: 07/07/2009
• Est. Priority Date: 04/21/2005
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Schweid, Stuart A., Sharma, Gaurav
• Primary Examiner(s): Nalven, Andrew L
• Application Number:
  US11/110,813
• Publication Number:
  US 20060242416A1
• Time in Patent Office: 1,538 Days
• Field of Search: 713/176
• US Class Current: 713/176
• CPC Class Codes: G06T 1/005 Robust watermarking, e.g. average attack or collusion attack resistant
• CPC Class Codes: H04L 2209/043 of tables, e.g. lookup, substitution or mapping
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC

Abstract

System and methods provide a message, generated based on a message authentication code (MAC), embedded in a look-up table associated with an image. The embedding of the message does not affect the image. The message may be used to authenticate the image.

Claims

1. A computer-readable storage medium storing computer-executable instructions for executing a method of embedding a message in a look-up table (LUT) for a data set, the LUT including a plurality of entries for a plurality of values, each of the plurality of values providing information regarding the data set, each of the plurality of entries capable of being used for one of the plurality of values, the plurality of values capable of being arranged in the entries of the LUT in a plurality of arrangements, wherein the plurality of entries is associated with a set of N indices, N being an integer, the method comprising:

obtaining a message, the message providing information other than the information regarding the data set;

selecting an arrangement from the plurality of arrangements based on the message;

arranging the plurality of values in the LUT based on the selected arrangement; and

embedding first M bits of the message in first M spaces of a least significant bit (LSB) plane of the set of N indices, wherein M is an integer equal to or less than N/2 and M is at least 2.

2. The method of claim 1, wherein the image is a palettized image, the LUT is a color code table, and the values are RGB values.

3. The method of claim 1, wherein entries of the LUT are arranged in an increasing order based on the RGB values according to:

R+256*G+256*256*B.

4. The method of claim 1, further comprising:

embedding first L1 bits of remaining bits of the message in first L1 spaces of a second least significant bit plane of the N indices, wherein L1 is an integer equal to or less than M/2.

5. The method of claim 4, wherein M=N/2, L1=M/2, the method further comprising:

embedding invert values of the first L1 bits in spaces L1+1 to M of the second least significant bit plane, an invert value of a bit A being (1-A); and

embedding second L1 bits of the remaining bits of the message in spaces M+1 to M+L1+1 of the second least significant bit plane.

6. The method of claim 4, further comprising:

embedding subsequent L1 bits of remaining bits of the message in L1 subsequent available indices of the second least significant bit plane, the available indices being restricted by binary expressions of the N indices.

7. The method of claim 1, further comprising:

embedding a message having a length of (N/2)*log2(N) bits.

8. The method of claim 1, wherein, when the message has a length of N1 bits, N1 being an integer great than N, the method comprises:

replicating values of the LUT; and

adding N2 indices to the set of indices, the added N2 indices indicating positions of the replicated in the LUT,

wherein N2 is an integer equal to or greater than N1-N.

9. The method of claim 1, the data set being an image, the image having pixels, each pixel being associated with one of the plurality of values via one of a set of indices, each index indicating a position of the associated value in the LUT, the method further comprising:

reconstructing the image by replacing the indices at the pixels with the respective associated values;

converting the reconstructed image into a bit stream representation by scanning bits of the pixels in a predefined order;

determining a characteristic of the image from the bit stream representation;

encrypting the characteristic using a private key; and

generating the message based on the encrypted characteristic.

10. The method of claim 9, wherein the characteristic is a CRC or hash function of the bit stream representation.

11. The method of claim 9, further comprising:

transforming the characteristic into a transformed function; and

encrypting the transformed function with the private key.

12. The method of claim 9, further comprising:

obtaining a message authentication code (MAC) based on the encrypted characteristic; and

generating the message based on the message authentication code (MAC).

13. The method of claim 1, the data set being an image, the image having pixels, each pixel being associated with one of the plurality of values via one of a set of indices, each index indicating a position of the associated value in the LUT, the method further comprising:

determining an order of the set of indices in the LUT; and

altering the determined order into an altered order.

14. A system of embedding a message in a look-up table (LUT) for a data set, the LUT including a plurality of entries for a plurality of values, each of the plurality of values providing information regarding the data set, each of the plurality of entries capable of being used for one of the plurality of values, the plurality of entries is associated with a set of N indices, N being an integer, the plurality of values capable of being arranged in the entries of the LUT in a plurality of arrangements, the system comprising:

a controller, wherein the controller obtains a message, the message providing information other than the information regarding the data set; and

a LUT and image rearrangement circuit, routine or application that selects an arrangement from the plurality of arrangements based on the message, and arranges the plurality of values in the LUT based on the selected arrangement,

wherein the controller controls the LUT and image rearrangement circuit, routine or application to;

embed first M bits of the message in first M spaces of a least significant bit (LSB) plane of the set of N indices, wherein M is an integer equal to or less than N/2 and M is at least 2.

15. The system of claim 14, wherein the image is a palettized image, the LUT is a color code table, and the values are RGB values.

16. The system of claim 15, wherein entries of the LUT are arranged in an increasing order based on the RGB values according to:

R+256*G+256*256*B.

17. The system of claim 14, the controller further controlling the LUT and image rearrangement circuit, routine or application to:

embed first L1 bits of remaining bits of the message in first L1 spaces of a second least significant bit plane of the N indices, wherein L1 is an integer equal to or less than M/2.

18. The system of claim 17, wherein M=N/2, L1=M/2, the controller further controlling the LUT and image rearrangement circuit, routine or application to:

embed invert values of the first L1 bits in spaces L1+1 to M of the second least significant bit plane, an invert value of a bit A being (1-A); and

embed second L1 bits of the remaining bits of the message in spaces M+1 to M+L1+1 of the second least significant bit plane.

19. The system of claim 17, the controller further controlling the LUT and image rearrangement circuit, routine or application to:

embed subsequent L1 bits of remaining bits of the message in L1 subsequent available indices of the second least significant bit plane, the available indices being restricted by binary expressions of the N indices.

20. The system of claim 14, the controller controlling the LUT and image rearrangement circuit, routine or application to:

embed a message having a length of (N/2)*log2(N) bits.

21. The system of claim 14, wherein, when the message has a length of N1 bits, N1 being an integer great than N, the controller further controlling the LUT and image rearrangement circuit, routine or application to:

replicate values of the LUT; and

add N2 indices to the set of indices, the added N2 indices indicating positions of the replicated in the LUT,

wherein N2 is an integer equal to or greater than N1-N.

22. The system of claim 14, the data set being an image, the image having pixels, each pixel being associated with one of the plurality of values via one of a set of indices, each index indicating a position of the associated value in the LUT, the system further comprising:

a bit stream generating circuit, routine or application that reconstructs the image by replacing the indices at the pixels with the respective associated values, and converts the reconstructed image into a bit stream representation by scanning bits of the pixels in a predefined order;

a characteristic generating circuit, routine or application that determines a characteristic of the image from the bit stream representation;

an encryptor that encrypts the characteristic using a private key; and

an ancillary information generating circuit, routine or application that generates the message based on the encrypted characteristic.

23. The system of claim 22, wherein the characteristic is a CRC or hash function of the bit stream representation.

24. The system of claim 22, the controller controlling the ancillary information generating circuit, routine or application to:

transform the characteristic into a transformed function; and

encrypt the transformed function with the private key.

25. The system of claim 22, the controller controlling the ancillary information generating circuit, routine or application to:

obtain a message authentication code (MAC) based on the encrypted characteristic; and

generate the message based on the message authentication code (MAC).

26. The system of claim 14, the data set being an image, the image having pixels, each pixel being associated with one of the plurality of values via one of a set of indices, each index indicating a position of the associated value in the LUT, the controller controlling the LUT and image rearranging circuit, routine or application to:

determine an order of the set of indices in the LUT; and

alter the determined order into an altered order.

27. An authentication apparatus comprising the system of claim 14.