Abstract:
Embodiments of the present invention are capable of hiding a message, such as, for example, a copyright notice or other indicium of authorship, in an electronic document. An illustrative embodiment of the present invention comprises encoding an electronic document with a plurality of tags from a case insensitive markup language; and modulating the case of at least one tag character in at least one of said plurality of tags with a binary string, wherein the binary string represents a message to be hidden in the electronic document.

Description:
FIELD OF THE INVENTION 
     The present invention relates to steganography in general, and, more particularly, to a method for hiding a message in an electronic document. 
     BACKGROUND OF THE INVENTION 
     The copyright law grants an author of an original work limited rights to assist the author in harvesting the rewards of his or her labor and creativity. These rights include the right to preclude others from reproducing and distributing the copyrighted work. Although both electronic and paper documents are copied by infringers, the ease with which electronic documents can be copied, edited and reproduced exacerbates the problem of providing evidence that an accused infringer has, in fact, copied the accused infringing work from the original work. 
     In some cases, the subject matter of the original work is new (e.g., a novel, a song, a painting) and evidence of copying can be shown by comparing the similarity between the original work and that of the accused infringing work. When, however, the subject matter underlying an original work is not new because it is in the public domain, the author may have difficulty providing evidence of copyright infringement because the original work and the accused infringing work should be similar (since both works are representative of the same underlying subject matter). Examples of original works whose underlying subject matter is in the public domain include, for example, a map of Virginia, a telephone directory of businesses in Arlington, a compilation of trigonometric tables, a compilation of government documents, etc. 
     Several techniques are used to help authors and publishers show copyright infringement in works whose underlying subject matter is not new. The first technique is commonly used by publishers of maps and involves &#34;seeding&#34; the map with errors. The theory being that if an accused infringer copies the original map, the infringer&#39;s map will contain the seeded errors, which it would not had the accused infringer created his or her map from original research. Similarly, the publishers of telephone directories and other compilations often seed their directories with fictitious entries, under the same theory. A problem with these approaches, however, is that they affect the fidelity of the original work. 
     SUMMARY OF THE INVENTION 
     Embodiments of the present invention are capable of hiding a message, such as, for example, a copyright notice or other indicium of authorship or ownership, in an electronic document without some of the costs and restrictions associated with methods in the prior art. In particular, a message can be hidden in an electronic document: (1) without affecting the fidelity of the document&#39;s subject matter, (2) without increasing the number of bytes in the document, (3) without affecting the formatting of the document when printed or viewed through a browser, and (4) such that a copyright infringer is likely to unknowingly copy the hidden message into the infringing work when he or she copies the original work. If the copyright infringer copies the hidden message into the infringing work, the original author can provide evidence of copyright infringement by retrieving, in court if necessary, the hidden message from the accused infringing work. 
     An illustrative embodiment of the present invention comprises encoding an electronic document with a plurality of tags from a case insensitive markup language; and modulating the case of at least one tag character in at least one of said plurality of tags with a binary string, wherein said binary string represents a message to be hidden in said electronic document. 
    
    
     BRIEF DESCRIPTION OF THE FIGURES 
     FIG. 1 depicts a flowchart of an illustrative embodiment of the present invention. 
     FIG. 2 depicts the contents of an electronic document. 
     FIG. 3 depicts the contents of the electronic document in FIG. 2 after it has been encoded with HTML, wherein all of the tag characters are in uppercase. 
     FIG. 4 depicts how the encoded electronic document of FIG. 3, FIG. 5, FIG. 6 and FIG. 7 appears when printed or viewed through a browser. 
     FIG. 5 depicts the contents of the electronic document in FIG. 2 after it has been encoded with HTML, wherein all of the tag characters are in lowercase. 
     FIG. 6 depicts the contents of the electronic document in FIG. 2 after it has been encoded with HTML, wherein the case of the tag characters is arbitrarily chosen. 
     FIG. 7 depicts the contents of the electronic document of FIG. 2 after it has been encoded with HTML and the case of the tag characters has been modulated in conformance with a binary string in accordance with an illustrative embodiment of the present invention. 
     FIG. 8 depicts a flowchart of a method of recovering a hidden message from an electronic document that was hidden in accordance with an embodiment of the present invention. 
     FIG. 9 depicts the contents of the electronic document of FIG. 7 after it has been copied by a copyright infringer and slightly modified in an attempt to conceal the infringement. 
    
    
     DETAILED DESCRIPTION 
     FIG. 1 depicts a flowchart of the steps performed by an illustrative embodiment of the present invention that is suitable for implementation in custom hardware, as an appropriately programmed general purpose processor, or as a combination of the two. It will also be clear to those skilled in the art that many of the depicted operations can be parallelized. 
     The method begins at step 101 with the encoding of the electronic document with a &#34;case insensitive markup language.&#34; The electronic document can comprise text, graphics, photographs or other multimedia elements, and it will be clear to those skilled in the art how to make and use such an electronic document. 
     For the purposes of this specification, a &#34;markup language&#34; is a collection of tags that are used to format an electronic document, usually for printing on a printer or for viewing with a &#34;browser&#34;. Markup languages are well known to those skilled in the art and include nroff, troff, T E  X, SGML, HTML, RTF, Word 6.0 and WordPerfect 6.0. 
     For the purposes of this specification a &#34;case insensitive markup language&#34; is a markup language in which the case of one or more of the characters in the language&#39;s tags are irrelevant to the syntax of the language. For example, HTML is a case insensitive markup language because the HTML tag &lt;P&gt; with a capital &#34;P&#34; creates exactly the same effect (starting a new paragraph) as does the HTML tag &lt;p&gt; with a small &#34;p&#34;. Furthermore, the HTML tags &lt;BR&gt;, &lt;Br&gt;, &lt;bR&gt; and &lt;br&gt; all cause a line break. It will be clear to those skilled in the art how to determine which markup languages are case insensitive. 
     Typically, the electronic document resides in a computer&#39;s memory and the encoding is performed by a text editor (e.g., ed, vi, emacs, etc.), word processor (e.g., Microsoft Word, WordPerfect) or markup editor (e.g., Adobe Pagemill, HoTMetaL Pro, Netscape Navigator Gold, etc.) under the direction of a human user. Alternatively, the encoding of the electronic document can be partially or totally automated and performed by an appropriately programmed general purpose computer. 
     For pedagogical purposes, the illustrative embodiment in FIG. 1 is presented as it operates on a illustrative electronic document. FIG. 2 depicts the text of the illustrative electronic document before it is encoded with a markup language. Although this document comprises only text, it will be clear to those skilled in the art how, using a markup language, to construct documents or &#34;pages&#34; that also comprise graphics, photographs, motion pictures and other multimedia elements. 
     FIG. 3 depicts how the illustrative document of FIG. 2 appears after it has been encoded with HTML. Note that all of the tag characters are in uppercase in the document of FIG. 3. 
     FIG. 4 depicts how the encoded document of FIG. 3 appears when viewed through an HTML browser such as the Netscape Navigator or the Internet Explorer. 
     FIG. 5 depicts how the document of FIG. 2 has been encoded with HTML, but with all of the tag characters in lowercase. Because HTML is case insensitive, FIG. 4 also depicts how the encoded document of FIG. 5 appears when viewed through an HTML browser. Furthermore, FIG. 6 depicts how the document of FIG. 2 has been encoded with HTML but with some of the tag characters in uppercase and some in lowercase. Again, because HTML is case insensitive, FIG. 4 also depicts how the encoded document of FIG. 6 appears when viewed through an HTML browser. 
     In step 103, a message is composed to be hidden in the document. The message can comprise text, a number, a graphic, a photograph or any other multimedia element that can be mapped to a binary code. For the purposes of this illustration, the message shall be the text string &#34;© 1996 JPD&#34;. Typically, the message is stored electronically in the same computer that holds the electronic document into which it is to be hidden. 
     In step 105, the message is reduced to a binary code. Typically, this step is performed by the same computer that holds the electronic document as the message to be hidden. According to the illustrative embodiment, each of the 10 characters in the message is converted to an 8-bit binary ASCII string, which are concatenated to form one 80-bit binary string: 
     1010100100100000001100010011100100111001 
     0011011000100000010010100101000001000100 
     Table 1 illustrates how each character is mapped to ASCII. 
     
                       TABLE 1______________________________________         ASCII      ASCIICharacter     (Hexadecimal)                    (Binary)______________________________________©     A9         10101001(SPACE)       20         001000001             31         001100019             39         001110019             39         001110016             36         00110110(SPACE)       20         00100000J             4A         01001010P             50         01010000D             44         01000100______________________________________ 
    
     It will be clear to those skilled in the art how to reduce a message to other binary codes. 
     In step 107, the binary string is advantageously augmented with an error correcting code, such as a Hamming Code, to increase the probability that the message can be recovered should the electronic document be edited by a copyright infringer. It will be clear to those skilled in the art how to augment the binary string with an error correcting code. For pedagogical purposes, the binary string in this illustrative example is not augmented with an error correcting code. 
     In step 109, the case of some or all of the tag characters in the document are modulated with the binary code. For example, because the case of a tag character can be set to either upper or lowercase, the case of that tag character can be modulated to carry one bit of information of the message to be hidden. In the illustrative embodiment, a tag character is modulated to uppercase by a &#34;1&#34; in the binary string and modulated to lowercase by a &#34;0&#34;. Alternatively, the tag characters could be modulated according to other systems. 
     It will be clear to those skilled in the art that there must be at least as many tag characters in the document as there are bits in the binary code if the document is to hold the entire message. If there are more tags characters in the document than in the binary code, then not all of the tag characters need to be modulated. For example, in documents with hundreds of tag characters, into which it is desired that messages of dozens of bits are to be hidden, a nonempty subset of those tag characters is advantageously chosen to be modulated such that the subset reduces the likelihood that a potential infringer will notice the variation in the case of the tag characters. Alternatively, the nonempty subset of tag characters could advantageously be chosen so as to reduce the likelihood that an infringers editing of the document would inexorably destroy the possibility of recovering the hidden message from the document. In yet another alternative embodiment, the message could be hidden multiple times in the document on the theory that the infringers editing is unlikely to destroy all of the copies of the hidden message. In still another alternative embodiment, two or more tag characters can be modulated by a single bit in the binary string. 
     For example, in an alternative embodiment of the present invention only the paragraph tag characters are modulated while all other tag characters in the document are set to lowercase or are given an arbitrary case. In yet another alternative embodiment, only the first alphabetic character of each tag is modulated. It will be clear to those skilled in the art how to select a subset of tag characters to be modulated such that those tag characters can be unambiguously identified for demodulation. 
     Returning to the illustrative example, there are 80 bits in the binary code and 84 tag characters in the electronic document. In the illustrative embodiment, the first 80 tag characters in the electronic document will modulated in order (and, therefore, when demodulation occurs, the first 80 tag characters will be demodulated in order). Because the first tag character in the document is the letter &#34;H&#34; in the tag &lt;HTML&gt; and the first bit in the binary string is a &#34;1&#34;. Therefore, the tag character is set to an uppercase &#34;H&#34;. The second tag character in the document is the letter &#34;T&#34; in the tag &lt;HTML&gt; and the second bit in the binary string is a &#34;0&#34;. Therefore, the tag character is set to a lowercase &#34;t&#34;. This continues until each of the bits in the binary string have modulated the case of a tag character. The text of the finished electronic document appears in FIG. 7. 
     If a copyright infringer copies the electronic document of FIG. 7, the hidden message is copied too. And even if the copyright infringer changes the text of the document slightly, as shown in FIG. 9, perhaps even adding or subtracting some tags, the hidden message might still be recoverable, depending on the robustness of the error correction used in step 107. Furthermore, even if the copyright infringer examines the electronic document, it is possible that he or she will either not notice the variation in the case of the tag characters, or will not recognize their significance. This is particularly true if only a small percentage of all of the tag characters in the document are modulated. 
     When an author or publisher of a copyrighted work encodes an electronic document according to an embodiment of the present invention, the author can provide evidence of copyright infringement by revealing, in court if necessary, the hidden message from the accused infringing work. 
     FIG. 8 depicts a flowchart of an illustrative method for recovering a hidden message from an electronic document. It will clear to those skilled in the art how to recover a hidden message from an electronic document given an embodiment of the present invention. For example, given the illustrative embodiment above, it will be clear to those skilled in the art how to demodulate the first 80 tag characters in the electronic document shown in FIG. 9 to recover the string: 
     1010100100100000001100010011100100111001 
     0011011000100000010010100101000001000100 
     For example, the first bit is a &#34;1&#34; because the &#34;H&#34; in the tag &#34;&lt;HtMl&gt;&#34; is in uppercase. The &#34;t&#34; in &#34;&lt;HtMl&gt;&#34; is lowercase and, therefore, the second bit is a &#34;0&#34;. The remainder of the 80 bits are recovered in the same manner. Table 2 illustrates how each 8 bit string is grouped and converted to its ASCII character equivalent. 
     
                       TABLE 2______________________________________ASCII         ASCII(Binary)      (Hexadecimal)                    Character______________________________________10101001      A9         ©00100000      20         (SPACE)00110001      31         100111001      39         900111001      39         900110110      36         600100000      20         (SPACE)01001010      4A         J01010000      50         P01000100      44         D______________________________________ 
    
     The result is the extraction of the message &#34;© 1996 JPD&#34;, which serves as evidence that the document in FIG. 9 was copied from that in FIG. 7.