Content-based authentication of graph presented in text documents

1. Technical Field

The present invention relates generally to document authentication. More particularly, the present invention relates to the authentication of graphs at the object level as well as the pixel level.

2. Discussion

For as long as humans have communicated with one another, there has been concern over maintaining confidentiality. As a result, verbal, written, and electronic messages have all been the subject of substantial technological efforts to maintain security. For example, document authentication techniques are commonly used to ensure the integrity of a wide variety of electronic documents such as, presentations, contracts, military orders, and databases. Authentication involves the task of making the determination that the document has not been tampered with and that it originated with the presumed transmitter. Authentication using digital watermarks is a particular technique that has been studied by many researchers in the last ten years. For example, digital watermarking has been successfully applied to digital documents such as digital color/gray scale images and plain text. While electronic document authentication efforts have experienced considerable success, it is important to note that these efforts have typically centered around the protection of textual documents and images.

Recently, however, more and more documents are using graphs in addition to images and text for system and idea illustration. In contrast to images, graphs are more difficult to watermark because of low capacity of additive noise. This is due to the binary nature of graphs. The term “binary nature” relates to the fact that most graphs have one bit per pixel, whereas most images have multiple bits per pixel to indicate varying shades and colors. Binary pixels make it particularly hard to insert watermarks due to the low capacity for perceptual invisible noise. In other words, a minimal alteration of bits in a binary graph can result in a substantial change in the appearance and content of the graph. Furthermore, the critical information of a graph is often contained at the object level rather than the pixel level. For example, a useful application for document copying and copyright protection is to provide different levels of access to different users. In such a case it would be very desirable to detect alteration of the original document as well as localize the alteration on the object level. For example, it is more important to detect a substantive change in a document, such as “10%” to “70%”, than it is to detect an increase in the size of an arrow by one pixel. Thus, the sensitive information in a document is often contained on the object level rather than the pixel level.

Pixel level authentication may also result in less flexibility. For example, if the annotation font of a graph changes but the content of the graph does not, pixel level authentication will alert the owner that the annotations have been altered. The owner has no way of determining, however, that the content of the graph matches the original. Object level authentication, on the other hand, would assure the owner that the “content is authentic” in such a case. If the font is marked as sensitive information, object level authentication could also alert the owner to font alterations. In many applications, however, it would be highly desirable to provide a mechanism for returning an “authentic” determination if the font is not marked as sensitive information.

Conventional methodologies for content-based text authentication mainly rely on altering the word/line spacing or the length of character vertical serif strokes. While text documents are often referred to as binary images and share the same binary nature of graphs, these methodologies can hardly be extended to authentication of graphs. This is because even on the pixel level graphs generally do not exhibit the same characteristics as text. For instance, in a graphical flowchart the shape of each node may be very important, whereas the nodes often have substantially fewer characters as compared to a paragraph of text. In such a flowchart the number of objects that exhibit a vertical serif can be as low as a few percent of the total number of objects. Here, an object is referred to an alterable line, character, or curve. In fact, other kinds of graphs may not exhibit alterable line spacing or vertical serif at all. It is therefore desirable to bridge text-based authentication techniques to the authentication of graphs.

The above and other objects are provided by a computerized method for authenticating a document. The method includes the step of partitioning the document into graphical content and textual content. The graphical content is then converted into a symbolic representation of the graphical content. The method further provides for authenticating the symbolic representation with a text authentication algorithm.

The present invention also provides a computerized method for authenticating a binary graph. The graph is authenticated at the pixel level as well as the object level. The method includes the step of encrypting the authenticated graph.

As a further aspect of the invention, a graph authentication system has an object level authenticator for authenticating a graph at an object level. The authentication system further includes a pixel level authenticator for authenticating the graph at a pixel level and an encryption system for encrypting the authenticated graph.

It is to be understood that both the foregoing general description and the following detailed description are merely exemplary of the invention, and are intended to provide an overview or framework for understanding the nature and character of the invention as it is claimed. The accompanying drawings are included to provide a further understanding of the invention, and are incorporated in and constitute part of this specification. The drawings illustrate various features and embodiments of the invention, and together with the description serve to explain the principles and operation of the invention.

The various advantages of the present invention will become apparent to one skilled in the art by reading the following specification and appended claims, and by referencing the following drawings in which:

FIG. 1 is a block diagram of a graph authentication system according to the present invention;

FIG. 2 is a block diagram of an object level authenticator according to the present invention;

FIG. 3 is a block diagram of a pixel level authenticator according to the present invention;

FIG. 4 is a flowchart of a computerized method for authenticating a document according to the present invention;

FIG. 5 is a flowchart of the process of authenticating a graph at the object level according to the present invention;

FIG. 6 is a flowchart of the process for authenticating a graph at the pixel level according to the present invention;

FIG. 7 is a flowchart for the process of adding visible authorization information according to the present invention;

FIG. 8 is a flowchart for the process of adding invisible authorization information according to the present invention;

FIG. 9 is a sample illustration of graphs which can be authenticated with the present invention;

FIG. 10 is an illustration of a graphical flowchart which can be authenticated with the present invention;

FIG. 11 is a block diagram of a one-party owned document authentication process according to the present invention;

FIG. 12 is an illustration of a key set according to the present invention;

FIG. 13 is a table of relationship and specification symbols according to a preferred embodiment of the present invention;

FIG. 14 is a symbolic representation of the graphical flowchart of FIG. 10 ;

FIG. 15 is a graphical flowchart authenticated at the pixel level using a bounded box according to the present invention;

FIG. 16 is a graphical flowchart authenticated at the pixel level using a bar code according to the present invention;

FIG. 17 is an enlarged view of textual and graphical content containing invisible authentication information; and

FIG. 18 is a table comparing graph authentication algorithms.

Turning now to FIG. 1 , the preferred embodiment of the graph authentication system 20 includes an object level authenticator 30 , a pixel level authenticator 40 , and an encryption system 50 . The graph authentication system 20 provides for content-based authentication of graphs contained in a host document 51 . The result is protected document 52 . As part of the following discussion, I is defined to be the host document 51 , such as a contract, which will be authenticated by owner O 1 or owners O 1 , O 2 to On. The authenticated copy of host document I is denoted as Ĩ. In correspondence, G and {tilde over (G)} are defined to be the original and the authenticated copy of a graph respectively. Furthermore, R is defined as an authorized receiver, whereas A is an attacker, i.e., unauthorized receiver. The following scenarios illustrate potential applications and objectives of graph authentication system 20 .

The first scenario is the situation in which I 1 ε O 1 , O 1 wants to determine whether her document I 1 is authentic. The content of the document contains sensitive information, such as a price of $1,000 or a deadline of Jun. 1, 1999. Another scenario occurs when I 1 ε O 1 , O 1 needs to send I 1 to R and wishes to grant R “read” permission but not “write” permission. A variation on this scenario is the situation in which O 1 wants to prevent alteration of any kind and to localize the alterations made by an attacker A who gets I 1 from O 1 and then sends it to R. Or, O 1 may want everyone to be able to read I 1 while only herself and R can make modification on the document. Another scenario occurs when I 1 ε O 1 ∩O 2 , i.e., I 1 , is a contract between O 1 and O 2 . If the copy in O 1 's hand is different from that of in O 2 's, O 1 wants to prove that O 2 's copy is a tampered copy of the original contract by checking the authenticity of O 2 's copy. In addition, O 1 may want to point out where exactly O 2 altered the original contract.

Turning now to FIG. 11 , it can be appreciated that the present invention provides a fully functional content-based authentication system for text documents including binary graphs. By building a bridge from graph to text on the character level, the present invention allows authentication of graphs using suitable text document authentication algorithms. When pixel level precision of a graph is required, a pixel level authentication can be added. This layer lets the owner detect as well as localize changes in the graph on the pixel level. The hierarchical layout allows the application of the present invention to the aforementioned scenarios as well as other scenarios.

The first level of the hierarchy is the pixel level authentication which is followed by an object level authentication. These are done with owner O 1 's private key. Notice here, either the pixel level or the object level protection is optional depending on the application. For ultimate protection, however, a dual-layer protection with a pixel protection layer plus an object protection layer is recommended since the two layers are orthogonal. Additionally, a meaningful watermark, such as a company logo, can be inserted, if desirable, into the document. Furthermore, the authenticated documents, including text and graphs can be encrypted with a public key encryption algorithm for secure transmission. Here the watermarking layer can be done either before or after the authentication layer. This again, depends on different applications. Access authorization can then be granted by distributing different keys to different users. For example, in the case of “read” only access, R will be given the public decryption key K 4 only. In the case of a multi-party owned document authentication, each party has a private key, the authentication is done by generating a key set with the private key from every party (see FIG. 12 ). Attempted modifications of the document without a key will therefore be unsuccessful.

Returning to FIG. 1 , it will be appreciated that the object level authenticator 30 authenticates the graph at an object level, whereas the pixel level authenticator 40 authenticates the graph at a pixel level. The encryption system 50 encrypts the authenticated graph for transmission to the recipient. As seen in FIG. 2 , it will be appreciated that the object level authenticator 30 converts the graph into a symbolic representation of the graph via a specification module 31 and a relationship module 32 . The specification module 31 defines nodes of the graph with specification symbols. Similarly, the relationship module 32 defines relationships between the nodes of the graph with relationship symbols. This allows a text authentication module 33 to authenticate the symbolic representation with a text authentication algorithm.

FIG. 9 demonstrates the various types of graphs which can be authenticated via the present invention. The operation of the object level authenticator 30 can be better understood through the graphical flowchart of FIG. 10 . It can be appreciated that the important information contained in graphical flowchart 34 is the annotation of each node and the connections between nodes that illustrate the relationship of nodes. Whether the drawing of each box is slightly smaller or slightly larger, the length of a line is longer or shorter, or the position of a node is tilted to the left or right is generally not as important. Consequently, the authentication process is mainly concerned with the object level instead of the pixel level of the graphical flowchart 34 . It is important to note that the important characteristics of an object depend on the type of graph. Thus, in the case of the bar chart of FIG. 9( c ), the important information is contained in the relative height of each individual bar rather than the overall height of the graph. For example, if the height of the second bar is changed to half its original height, the value of the second bar is thereby altered. It will be appreciated that the concern with most text documents is at the object level, or character level.

Graphical flowchart 34 therefore includes various nodes and lines and can be represented with a series of relationship symbols along with the node annotations as follows: “<N 1 {‘Process A’, #1, &reg, @mid}→N 2 {‘Process B’, #1, &reg, @mid}→N 3 {‘If C’, #3, &reg, @mid}→<N 4 {‘End’, #2, &reg, @mid}|yes; N 2 |no>>”, wherein FIG. 13 illustrates the relationship and specification symbols for the above symbolic representation. The result is shown in FIG. 14 . In the above symbolic representation, N 1 N 2 . . . are node names with the property of each node contained in { }, < > is a tuple, and → and | are relationship symbols. It will be appreciated that the properties of nodes and lines, the shape, size, color, and position, can be described with the specification symbols. For those specification insensitive graphs, the symbols between each pair of { } can be simply ignored whereas in specification sensitive graphs, the specification symbols in each pair of { } provide different levels of details. This hierarchical representation provides additional flexibility.

After defining the nodes of the graph with specification symbols, and the conditions and familial relationships with relationship symbols, the text authentication module 33 can authenticate the symbolic representation. For example, well known two- or multi-dimensional checksum techniques can be used to verify authenticity. For the following discussion, let T(p,q) represent the (p,q)th character. S(p,q)=s 1 (p,q) s 2 (p,q) . . . s J (p,q)=f(T(p,q)) is the coded representation of T(p,q) via map f, wherein s 1 (p,q) s 2 (p,q) . . . s J (p,q) represent the first, the second, . . . and the Jth bit of S(p,q) that are in the order of the most significant bit to the least significant bit. Furthermore, let Sum p j =Σ P p=1 s j (p,q) and Sum q j =Σ Q q=1 s j (p,q), where P & Q are dimensional sizes. Thus, the position (p,q) of any alteration Sum p ′≠Sum p , Sum q ′≠Sum q can be localized.

It will be appreciated that utilizing well known content-dependent one way hash functions provides a higher level of security. For the following discussion, let B denote the block size and K denote a private key. In the case of a multi-party document, K is a function of K O1 , K O2 , . . . , i.e., K=f1(K O1 , K O2 , . . . ). FIG. 12 illustrates a key set for the present example. For the purpose of discussion, we may assume each key in the set, K o1 , K o2 , . . . to be encrypted with its owner's private key, and an arbitrator (a trusted third party) is used to generate the key set K. It is important to note, however, that other suitable cryptography protocols may also be used. Assume K is a Jbits coding with the 1 st to (J−1) th bits being the code bits and the lowest bit, J th bit, being the verification bit. The document paragraph I shown in FIG. 14 can use 9 bits coding. Choosing the one way hash algorithm MD 5 , the encoding procedure is as follows. Pad the source text I to an exact multiple of 512 in length. For each 128-length set, I o , choose its neighborhood set, I o =512 characters with I o ⊂ I o . Assume

S o ={S o ( i ), i ε [1,128 ]}={s 1 o ( i ) s 2 o ( i ) . . . s J o ( i )}= f ( I o )

and

S o ={ S o ( i ), i ε [1,512 ]}={ s 1 o ( i ) s 2 o ( i ) . . . s J o ( i )}= f ( I o )

are coded representation of I o and I o respectively.

1. Concatenate the code bits of the neighborhood set I o , 2. Calculate the 128bits hash value of it, h o =H( S o ), 3. Generate message h o ′=Sgn(K, h o ) by signing h o with public cryptography method, and 4. Put h o ′ into the J th bit, the lowest bit, of S o (i), i.e., let s J o (i)=h o ′(i), i ε [1,128].

The above algorithm is discussed in the context of image authentication in the article “Fragile imperceptible digital watermark with privacy control”, C. W. Wu, D. Coppersmith, F. C. Mintzer, C. P. Tresser, and M. M. Yeung, IS&T/SPIE Conference on Security and Watermarking of Multimedia Content, SPIE 3657, January, 1999, incorporated herein by reference. The decoding process is similar to the encoding process with the verification done through an XOR operation. Such that Auth o (i)={tilde over (h)} o ′(i)⊕s J o (i).

If Auth o (i)=1 for ∀i ε [1,128], the I o set has been altered.

Turning now to FIG. 3 , the pixel level authenticator 40 of the graph authentication system 20 is shown in greater detail. It can be appreciated that a visible watermarking module 41 adds visible authentication information to the graph at the pixel level, whereas an invisible watermarking module 42 adds invisible authentication information to the graph at the pixel level. The preferred embodiment further includes a coalescing module 43 for embedding a hash value from the object level of the graph at the pixel level of the graph. Dual level authentication with coalescing has been found to yield optimum results. To authenticate I with N symbols, we compute the one way hash of I on the character level first. Therefore, if N=248 characters this is done by putting all the bits of the 248 characters together, pad the result to an exact multiple of 512 in length, and calculate the hash value of the padded message. Then, the 128 bits hash value is embedded at the pixel level.

Operation of the graph authentication system of the present invention will now be described in greater detail for programming purposes. Turning to FIG. 4 , a computerized method for authenticating an electronic file (or document) is shown generally at 100 . Step 102 demonstrates receipt of the electronic file. At step 101 , the file is partitioned into graphical content and textual content. The partitioning of graphs from text regions in a document has been the subject of considerable study. For example, U.S. Pat. No. 5,465,304, and U.S. Pat. No. 5,335,290 to Cullen, et al., incorporated herein by reference, discuss the segmentation of text, pictures, and lines of a document image. Furthermore, U.S. Pat. No. 5,073,953 to Westdijk, incorporated herein by reference, discloses a system and method for automatic document segmentation. The separation of body text from other regions of a document is taught in U.S. Pat. No. 5,892,843 to Zhou, et al., incorporated herein by reference. Also, in U.S. Pat. No. 5,379,130 to Wang, et al., a method and system that separates images from text is disclosed. Any of these techniques or other well known approaches can be readily adapted to perform partitioning step 101 .

At step 110 , it is determined whether the object level is a level of concern. If so, the graph is authenticated at the object level at step 111 by adding authentication information the electronic file based on an object level representation. Similarly, at step 130 it is determined whether the pixel level is a level of concern. If so, the document is authenticated at the pixel level at step 131 . It will be appreciated that object level authentication and pixel level authentication are both optional and can be performed in any order. The graph can then be encrypted at step 150 and transmitted at step 160 to an authorized recipient.

FIG. 5 shows step 111 in greater detail. It can be appreciated that nodes of the graph are defined with specification symbols at step 112 . Relationships between the nodes are then defined with relationship symbols at step 113 . The result is a symbolic (or object level) representation of the graphical content contained in the electronic file. It will be appreciated that other approaches to object level representation can be taken without parting form the scope of the invention. At step 114 , the symbolic representation is authenticated with a text authentication algorithm.

Turning now to FIG. 6 , step 131 is shown in greater detail. At step 132 , it is determined whether transparency is required based on the content of the graph and the host document. If so, invisible authorization information is added at step 133 . Otherwise, visible authorization information can be added at step 134 .

As seen in FIG. 7 , a relatively robust approach for adding visible authorization information is shown in greater detail. Specifically, at step 135 a truncated image of the graph is formed. For the following discussion, let X×Y=128 be the defined block size. Graph G can therefore be cut into X×Y blocks. Assuming the number of blocks is L, we concatenate the bits of the (x,y)th pixel of every block to the 1 st block and form an Lbits truncated image TrunG. Therefore, a Lbits/pixel image TrunG, with image size X×Y, of graph G is generated. Let TrunG(x,y) t denote the l th bit of pixel (x,y) of TrunG. Notice here, it is desirable to form the truncated image TrunG in such a way that TrunG(x,y)≠0. Also note that to get a higher level of protection, a random number generator should be used to cut the graph.

At step 136 , an initial message is generated from the truncated image. The initial message is defined by all bits of the truncated image. Thus, step 136 collects all bits of all X×Y pixels into a X×Y×L bits message M 1 . At step 137 , the initial message is converted into a padded message, wherein the padded message has a size defined by a multiple of a predetermined length. Thus, M 1 is padded into an exact multiple of 512 in length with as many zeros as needed to obtain message M 1 ′.

At step 138 , a hash value for the padded message is computed. Thus, step 138 computes the 128 bits hash value of M 1 ′ using MD 5 , M 2 =h(I)=H(M 1 ′). At step 139 , the hash value is converted into a public key encrypted message by signing the hash value with a public key cryptography method such that M 3 =h′(i)=Sgn(K, M 2 ). The public key encrypted message is then converted into visible authentication information at step 140 . The visible authentication information can be in many different formats. For example, FIG. 15 illustrates an authenticated graph using a bounding box, whereas FIG. 16 illustrates an authenticated graph using a bar code.

When invisible authentication is required or desirable, a less robust scheme that modifies the graph itself can be used. Thus, as shown in FIG. 8 , a truncated image is formed from the graph at step 135 ′. At step 141 , a verification bit is selected from each pixel of the truncated image. Thus, at step 141 1bit TrunG(x,y) I =1 out of the Lbits of each pixel (x,y) in TrunG to be the verification bit. For better imperceptibility and a higher lever of security, the verification bits should be picked in a way to maximize spread.

At step 136 ′ an initial message is generated from the truncated image, wherein the initial message is defined by all non-verification bits of the truncated image. Step 136 ′ therefore collects the remaining (L−1) bits of all X×Y pixels into a X×Y×(L−1) bits message M 1 . Message M 1 is padded into an exact multiple of 512 in length with as many 0s as needed and get message M 1 ′. The initial message is therefore converted into a padded message at step 137 ′. Preferably, the padded message has a size defined by a multiple of a predetermined length of 512.

At step 138 ′, the hash value is computed for the padded message. The hash value is then converted into a public key encrypted message at step 139 ′. The public key encrypted message can then be imbedded into the truncated image at step 142 in the following fashion:

If h′(i)=h′((y−1)*X+x))=0 and |TrunG(x,y)|=odd, let TrunG(x,y) I =0. If h′(i)=h′((y−1)*X+x))=1 and |TrunG(x,y)|=even, let TrunG(x,y) I =1.

Where |TrunG(x,y)| denotes the cardinality of TrunG(x,y), i.e., the number of bits that are ‘1’s among the Lbit of TrunG(x,y).

Turning now to FIG. 17 , two sample results can be seen. The lower result is cropped from the graphical flowchart in FIG. 10 . To give a better view, each result is enlarged to at least 400 percent of the original size.

Conventional space-shifting methods and serif-modification methods are proposed in “Electronic Marking and Identification Techniques to Discourage Document Copying”, J. Brassil, S. Low, N. Maxemchuk, and L. O'Gorman, IEEE Infocom 94, and in “Document Marking and Identification using Both Line and Word Shifting”, S. H. Low, N. F. Maxemchuk, J. T. Brassil, and L. O'Gorman, Infocom '95, both incorporated herein by reference. Comparing these techniques to the present invention, it can be seen in FIG. 18 that clear improvement has been achieved. Notice that when the hash value is prepended to the document, special coding is not needed for object level authentication. Otherwise, such coding is needed. Similarly, in the case of pixel level or coalesced authentication, special coding is not needed with visible authentication information, whereas it is needed for invisible authentication information. Here, special coding means a new code other than commonly accepted codes, such as ASCII Code and Unicode.

The foregoing discussion discloses and describes exemplary embodiments of the present invention. One skilled in the art will readily recognize from such discussion, and from the accompanying drawings and claims, that various changes, modifications and variations can be made therein without departing from the spirit and scope of the invention as defined in the following claims.