Content-based authentication of graph presented in text documents

• US 7,107,450 B1
• Filed: 10/28/1999
• Issued: 09/12/2006
• Est. Priority Date: 10/28/1999
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Yu, Hong Heather
• Primary Examiner(s): Moise, Emmanuel L.
• Assistant Examiner(s): CALLAHAN, PAUL E
• Application Number:
  US09/429,470
• Time in Patent Office: 2,511 Days
• Field of Search: 380/54, 705/57, 705/176, 713/176, 382/112, 382/113, 340/5.86, 340/5.8, 356/71, 399/12, 399/366, 283/73, 283/902, 358/3.28, 358/526, 358/405, 358/464, 285/73, 285/902
• US Class Current: 713/176
• CPC Class Codes: G06T 1/0021 Image watermarking
• CPC Class Codes: H04L 2209/608 Watermarking
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions

Abstract

A system and method provide for content-based authentication of binary graphs. The method includes the step of receiving an electronic file having a graphical content. An object level representation of the graphical content is then generated and authentication information is added to the electronic file based on the object level representation. The method further provides for authenticating the object level representation with a text authentication algorithm. Thus, by building a bridge from graphs to text at the character level, the present invention allows authentication of graphs using suitable text document authentication algorithms. When pixel level precision of the graph is required, a pixel level authentication can be added. This layer lets the owner detect as well as localize changes in the graph at the pixel level. Both levels of authentication are optional depending on the application.

Claims

1. A computerized method for authenticating an electronic file, the method comprising the steps of:

receiving an electronic file having a graphical content;

generating an object level representation of the graphical content;

adding authentication information to the electronic file based on the object level representation of the graphical content, wherein the graphical content contains one bit per pixel values; and

authenticating the object level representation with a text authentication algorithm.

2. A computerized method for authenticating an electronic file, the method comprising the steps of:

receiving an electronic file having a graphical content;

generating an object level representation of the graphical content;

adding authentication information to the electronic file based on the object level representation of the graphical content, wherein the graphical content contains one bit per pixel values;

authenticating the object level representation with a text authentication algorithm; and

authenticating the object level representation with a checksum.

3. A computerized method for authenticating an electronic file, the method comprising the steps of:

receiving an electronic file having a graphical content;

generating an object level representation of the graphical content;

adding authentication information to the electronic file based on the object level representation of the graphical content, wherein the graphical content contains one bit per pixel values;

authenticating the object level representation with a text authentication algorithm; and

authenticating the object level representation with a checksum, wherein the checksum is a two-dimensional checksum.

4. A computerized method for authenticating an electronic file, the method comprising the steps of:

receiving an electronic file having a graphical content;

generating an object level representation of the graphical content;

adding authentication information to the electronic file based on the object level representation of the graphical content, wherein the graphical content contains one bit per pixel values;

authenticating the object level representation with a text authentication algorithm; and

authenticating the object level representation with a checksum, wherein the checksum is a multi-dimensional checksum.

5. A computerized method for authenticating an electronic file, the method comprising the steps of:

receiving an electronic file having a graphical content;

generating an object level representation of the graphical content;

adding authentication information to the electronic file based on the object level representation of the graphical content, wherein the graphical content contains one bit per pixel values;

authenticating the object level representation with a text authentication algorithm; and

authenticating the object level representation with a cryptographic hash function.

6. A computerized method for authenticating an electronic file, the method comprising the steps of:

receiving an electronic file having a graphical content;

generating an object level representation of the graphical content;

adding authentication information to the electronic file based on the object level representation of the graphical content, wherein the graphical content contains one bit per pixel values;

authenticating the graphical content at a pixel level; and

adding visible authentication information to the graphical content, wherein the visible authentication information includes a bounding box.

7. A computerized method for authenticating an electronic file, the method comprising the steps of:

receiving an electronic file having a graphical content;

generating an object level representation of the graphical content;

adding authentication information to the electronic file based on the object level representation of the graphical content, wherein the graphical content contains one bit per pixel values;

authenticating the graphical content at a pixel level; and

adding visible authentication information to the graphical content, wherein the visible authentication information includes a bar code.

8. A computerized method for authenticating a binary graph, the method comprising the steps of:

authenticating the graph at a pixel level;

authenticating the graph at an object level;

encrypting the authenticated graph;

transmitting the authenticated graph to a recipient;

adding visible authentication information to the graph; and

forming a truncated image from the graph;

generating an initial message from the truncated image, the initial message defined by all bits of the truncated image;

converting the initial message into a padded message, the padded message having a size defined by a multiple of a predetermined length;

computing a hash value for the padded message;

converting the hash value into a public key encrypted message; and

converting the public key encrypted message into the visible authentication information.

9. A computerized method for authenticating a binary graph, the method comprising the steps of:

authenticating the graph at a pixel level;

authenticating the graph at an object level;

encrypting the authenticated graph;

transmitting the authenticated graph to a recipient;

adding visible authentication information to the graph; and

forming a truncated image from the graph;

generating an initial message from the truncated image, the initial message defined by all bits of the truncated image;

converting the initial message into a padded message, the padded message having a size defined by a multiple of a predetermined length;

computing a hash value for the padded message;

converting the hash value into a public key encrypted message; and

converting the public key encrypted message into the visible authentication information, wherein the visible authentication information includes a bounding box.

10. A computerized method for authenticating a binary graph, the method comprising the steps of:

authenticating the graph at a pixel level;

authenticating the graph at an object level;

encrypting the authenticated graph;

transmitting the authenticated graph to a recipient;

adding visible authentication information to the graph; and

forming a truncated image from the graph;

generating an initial message from the truncated image, the initial message defined by all bits of the truncated image;

converting the initial message into a padded message, the padded message having a size defined by a multiple of a predetermined length;

computing a hash value for the padded message;

converting the hash value into a public key encrypted message; and

converting the public key encrypted message into the visible authentication information, wherein the visible authentication information includes a bar code.

11. A computerized method for authenticating a binary graph, the method comprising the steps of:

authenticating the graph at a pixel level;

authenticating the graph at an object level;

encrypting the authenticated graph;

transmitting the authenticated graph to a recipient;

adding invisible authentication information to the graph;

forming a truncated image from the graph;

selecting a verification bit from each pixel of the truncated image;

generating an initial message from the truncated image, the initial message defined by all non-verification bits of the truncated image;

converting the initial message into a padded message, the padded message having a size defined by a multiple of a predetermined length;

computing a hash value for the padded message;

converting the hash value into a public key encrypted message; and

embedding the public key encrypted message into the truncated image.

12. A computerized method for authenticating a binary graph, the method comprising the steps of:

authenticating the graph at a pixel level;

authenticating the graph at an object level;

encrypting the authenticated graph;

transmitting the authenticated graph to a recipient;

adding invisible authentication information to the graph;

forming a truncated image from the graph;

selecting a verification bit from each pixel of the truncated image;

generating an initial message from the truncated image, the initial message defined by all non-verification bits of the truncated image;

converting the initial message into a padded message, the padded message having a size defined by a multiple of a predetermined length;

computing a hash value for the padded message;

converting the hash value into a public key encrypted message;

embedding the public key encrypted message into the truncated image; and

maximizing spread between the verification bits.

13. A computerized method for authenticating a binary graph, the method comprising the steps of:

authenticating the graph at a pixel level;

authenticating the graph at an object level;

encrypting the authenticated graph;

transmitting the authenticated graph to a recipient; and

authenticating a symbolic representation of the graph with a text authentication algorithm.

14. A computerized method for authenticating a binary graph, the method comprising the steps of:

authenticating the graph at a pixel level;

authenticating the graph at an object level;

encrypting the authenticated graph;

transmitting the authenticated graph to a recipient;

authenticating a symbolic representation of the graph with a text authentication algorithm;

defining nodes of the graph with specification symbols; and

defining relationships between the nodes of the graph with relationship symbols.

15. A computerized method for authenticating a binary graph, the method comprising the steps of:

authenticating the graph at a pixel level;

authenticating the graph at an object level;

encrypting the authenticated graph;

transmitting the authenticated graph to a recipient;

authenticating a symbolic representation of the graph with a text authentication algorithm; and

coalescing the object level of the graph with the pixel level of the graph.