Device and method for hiding information and device and method for extracting information

• US 7,167,825 B1
• Filed: 03/10/2000
• Issued: 01/23/2007
• Est. Priority Date: 03/10/1999
• Status: Expired due to Term

• Current Assignee: Thomas Potter
• Original Assignee: Thomas Potter
• Inventors: Potter, Thomas
• Primary Examiner(s): Dorvil; Richemond
• Assistant Examiner(s): Han; Qi
• Application Number:
  US09/936,853
• Time in Patent Office: 2,510 Days
• Field of Search: 704/9, 704/1, 380/42
• US Class Current: 704/9
• CPC Class Codes: H04L 2209/16 Obfuscation or hiding, e.g. involving white box
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 2209/84 Vehicles
• CPC Class Codes: H04L 9/065 Encryption by serially and continuously modifying data stream elements, e.g. stream cipher systems, RC4, SEAL or A5/3

Abstract

A device for hiding information in a text comprises a mechanicanism for providing the text, means for linguistically analyzing the text to produce text components, for determining a plurality of formulation alternatives for the text by varying the order of the text components and, optionally, in addition by using synonyms for text components, determining every formulation alternative is grammatically correct for the text and has essentially the same meaning as the text. Certain partial information is allocated to every sequence and/or to every synonym or to every paraphrase.

Claims

1. A device for hiding information in a text having at least one sentence, comprising

means for linguistically analyzing the text to produce linguistic text components, the linguistic text components being components of the sentence and the sentence, in addition to at least one additional linguistic text component, having exactly one predicate as a linguistic text component;

means for determining a plurality of formulation alternatives for the text, wherein the means for determining is operative to determine the plurality of formulation alternatives

by varying the order of the linguistic text components itself,

by ascertaining synonyms for the linguistic text components and varying the order of the synonyms for the linguistic text components, or

by ascertaining synonyms for at least one linguistic text component and varying the order of a synonym for the at least one linguistic text component and/for another linguistic text component of the sentence,

wherein the means for determining is adapted to generate the formulation alternatives such that every formulation alternative is grammatically correct for the text and has essentially the same meaning as the text, and that every order of linguistic text components and every synonym ascertained have specific partial information allocated thereto,

wherein the partial information allocated to the simultaneously possible formulation alternatives for a sentence result in an overall probability of 1.0 such that arbitrary information can be hidden in the text,

wherein the means for determining is operative to use, for the allocation of partial information to the simultaneously possible formulation alternatives, an existing probability distribution or a probability distribution generated in accordance with specific rules known to a device for extracting hidden information from a text;

means for selecting a formulation alternative from the plurality of formulation alternatives in such a manner that the partial information that is allocated to the selected formulation alternative corresponds at least to a part of the information to be hidden; and

means for outputting a selected formulation alternative forming a modified text, with said information to be hidden being hidden in said modified text,

wherein the means for linguistically analyzing includes a parser, wherein the parser is operative to recursively break down the sentence into the text components using a hierarchical tree structure, wherein the parser is further operative to determine the predicate and remaining elements of the sentence and to recursively search a linguistic head within the remaining elements of the sentence until the text components of the sentence are obtained,

wherein the parser includes a dictionary/grammar stage having an entry for the predicate or the linguistic head,

wherein the means for determining is operative to use the entry for the predicate and the linguistic head to exclude parsing alternatives resulting in grammatically incorrect formulation alternatives, and

wherein the means for determining is operative to leave a sentence unchanged when valid formulation alternatives can not be found.

2. A device according to claim 1,

wherein the means for linguistically analyzing is a parser, in particular a highly lexicalized, unification-based parser and specifically an HPSG parser.

3. A device according to claim 1,

wherein the means for determining a plurality of formulation alternatives is arranged to output only that formulation alternative from the plurality of formulation alternatives that is selected by the means for selecting on the basis of the information to be hidden.

4. A device according to claim 1,

wherein the dictionary/grammar stage has stored therein synonyms for linguistic text components as well as unequivocal partial information for each synonym, as the partial information including syntactic, semantic, contextual and statistic information.

5. A device according to claim 1,

wherein each sequence of the linguistic text components and each synonym ascertained has a weighting allocated thereto as partial information, said weighting being determined such that all weightings for the sequence and the synonyms together, respectively, yield a probability of 1, and

wherein the means for selecting is arranged to select one formulation alternative each in accordance with the rules of arithmetic decoding, controlled by the secret data that are understood as coded data.

6. A device according to claim 1,

wherein the partial information is in the form of Huffman code words, wherein the following equation holds:

$\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br><br><br>2^{-\mathrm{li}}=1.0$

in which li is the length in bit of the i^th Huffman code word and n is the number of Huffman code words of a context, wherein all synonyms for a linguistic text component, inclusive of the linguistic text component, together constitute a context of their own, wherein all different sequences of linguistic text components, inclusive of the sequence of the linguistic text components in the text, constitute a context of their own, such that any arbitrary information to be hidden constitutes a stream of valid Huffman code words.

7. A device according to claim 5,

wherein the information to be hidden comprises a bit sequence, wherein the means for selecting is arranged to take as many bits from the beginning of the bit sequence until the number constituted by these bits is unequivocally within a specific one of the probability intervals determined by said weightings, whereupon said means for selecting selects that formulation alternative that corresponds to the weighting allocated to the specific probability interval, whereupon said means for selecting carries out additional interval interleaving in order to select the next formulation alternative.

8. A device according to claim 6,

wherein the means for selecting is arranged to perform Huffman decoding, said means successively accessing various Huffman code contexts selected by the linguistic text components from a number of formulation alternatives provided by said means for determining a plurality of formulation alternatives, with the input to Huffman decoding being the information to be hidden and with the output from Huffman decoding being the modified text.

9. A device according to claim 1,

wherein each linguistic text component comprises at least one word, and wherein the synonyms for each word are stored in the dictionary/grammar stage together with the corresponding partial information, whereas the partial information for each different sequence of linguistic text components is predetermined in accordance with modelling of real linguistic laws by declarative rules, constraints or fixed implementations in software.

10. A device according to claim 9,

wherein the means for selecting is arranged to utilize a first section of the information to be hidden for the selection of the sequence of the linguistic text components and the subsequent sections for the selection of the synonyms, and wherein the sequence of the selected synonyms is a sequence selected from one or several linguistically possible sequences and is independent of the sequence of the linguistic text components in the text.

11. A device according to claim 1, further comprising:

means for encrypting or for compressing the information to be hidden, whereby encrypted and/or compressed information to be hidden is produced which is adapted to be fed to said means for selecting.

12. A device according to claim 1,

wherein the means for linguistically analyzing is arranged to deliver no linguistic text components for which the correctness of the reformulation cannot be guaranteed and/or wherein the means for determining formulation alternatives is arranged to offer only such formulation alternatives for which it is ensured that the analysis thereof can yield again the same sentence of formulation alternatives.

13. A device according to claim 1,

wherein there is public text and secret data, the device comprising a control means arranged to supply the information of the secret data to said means for selecting, such that the same are hidden in the public text by modification of the public text.

14. A device according to claim 13,

wherein the statistics used for compression or encryption are dependent on the public text so that conformities of data fragments in the public text and the secret data are utilized for efficient compression.

15. A device according to claim 1,

wherein the means for determining the formulation alternatives is controllable via the partial information in order to maintain a specific style, in particular to prefer or exclude certain formulation alternatives, the certain formulation alternatives including at least one of certain words, specific lengths of sentences, the kind of language complexity, the language level, the kind of syntax and word position models, the perspective of narration, the ethnic focus with respect to the origin of the words the modified text is supposed to have, which list of words to be avoided should be used, how presumed errors in the text are to be handled and whether new errors may be built in.

16. A device according to claim 1,

wherein the means for determining is operative to have a predetermined similarity threshold, and

wherein the means for determining is operative to determine similar formulation variants for the text, when semantic differences of the formulation alternatives with respect to an original alternative are above the similarity threshold, and

wherein the means for determining is operative to reject formulation alternatives having semantic differences with respect to the original alternative which are below the similarity threshold.

17. A device according to claim 15,

wherein the amount of text is limited, with the similarity threshold being dimensioned such that just the entire information to be hidden can be accommodated in the limited amount of text.

18. A device according to claim 1,

wherein the means for determining a plurality of formulation alternatives is arranged to dynamically determine the formulation alternatives and to dynamically produce the partial information allocated to each formulation alternative.

25. A device according to claim 1 or 20,

wherein said means for determining formulation alternatives or said means for producing partial information is arranged to utilize a word memory in the form of a tree or graph consisting of (a) full word forms, i.e. inflected words which then are correlated to other inflected words or (b) morphologic syntactic breaking down of the words in accordance with inflection classes, and in particular splitting into word prefixes, radices and suffixes, in which only the word radices or word prefix/word radix combinations are explicitly correlated as synonyms and the respective inflected forms are analyzed in accordance with the current demand in the respective word present on the basis of inflection data, and are generated correspondingly for a selected synonym.

26. A device according to claim 25,

wherein references to synonyms are organized either as (a) chain of synonymous meanings of a word that firstly make reference to each other in ring-like manner and secondly are ordered implicitly by an order regulation, such as the lexical sequence or arrangement in accordance with the probability of occurrence, or explicitly by a characterization of the rank of one or more elements, or (b) as group of words considered to be synonymous or as references to the synonyms with the property that reference is made inversely to this group as well from the synonyms concerned or that this group is stored as value of a synonym.

27. A device according to claim 1 or 20,

wherein the means for determining formulation alternatives is adapted to have a person-specific or generally found linguistic probability of a formulation alternative which has influence on the modeled probability or partial information used for compression.

28. A device according to claim 1 or 20,

wherein the means for determining formulation alternatives is operative to identify grammatically correct formulation alternatives and thus limiting a range of choices of formulation alternatives when recursively parsing by fully respecting the dependencies through levels of the parsing process guaranteeing correctness of an entire sentence.

29. A device according to claim 1 or 20, wherein the means for determining formulation alternatives and the means for selecting are operative to recursively search a linguistic head or select a formulation alternative, wherein a number of grammatically correct formulation alternative in a subsequent step is reduced compared to an earlier step so that a cumulative probability of all formulation alternatives for that step is such that probabilities for the formulation alternatives sum up to one and so that choices made before do not lead to grammatically incorrect or improbable sentences.

19. A method for hiding information in a text having at least one sentence, comprising:

linguistically analyzing the text to produce linguistic text components, the linguistic text components being components of the sentence and the sentence, in addition to at least one additional component, having exactly one predicate as a linguistic text component;

determining a plurality of formulation alternatives for the text

by varying the order of the linguistic text components itself,

by ascertaining synonyms for the linguistic text components and varying the order of the synonyms for the linguistic text components, or

by ascertaining synonyms for at least one linguistic text component and varying the order of a synonym for the at least one linguistic text component and of another linguistic text component of the sentence,

with every formulation alternative being grammatically correct for the text and having essentially the same meaning as the text, with every order of linguistic text components and every synonym ascertained having specific partial information allocated thereto, wherein the partial information allocated to the simultaneously possible formulation alternatives for a sentence result in an overall probability of 1.0 such that arbitrary information can be hidden in the text,

wherein, for the allocation of partial information to the simultaneously possible formulation alternatives, an existing probability distribution or a probability distribution generated in accordance with specific rules known to a device for extracting hidden information from a text is used;

selecting a formulation alternative from the plurality of formulation alternatives in such a manner that the partial information that is allocated to the selected formulation alternative corresponds to the information to be hidden; and

outputting the formulation alternatives that form a modified text, with said information to be hidden being contained in said modified text,

wherein the step of linguistically analyzing includes a step of parsing by recursively breaking down the sentence into the linguistic text components using a hierarchical tree structure, by determining the predicate and remaining elements of the sentence and by recursively searching a linguistic head within the remaining elements of the sentence until the text components of the sentence are obtained,

wherein the step of parsing furthermore using a dictionary/grammar stage having an entry for the predicate and the linguistic head,

wherein the step of determining comprises using the entry for the predicate and the linguistic head to exclude parsing alternatives resulting in grammatically incorrect formulation alternatives, and

wherein the step of determining leaves a sentence unchanged when valid formulation alternatives can not be found.

20. A device for extracting information hidden in a modified text, the modified text having at least one sentence, comprising:

means for linguistically analyzing the modified text to produce linguistic text components of the modified text, the linguistic text components being components of the sentence and the sentence, in addition to at least one additional component, having exactly one predicate as a linguistic text component;

wherein the means for linguistically analyzing includes a parser, wherein the parser is operative to recursively break down the sentence into the text components using a hierarchical tree structure, wherein the parser is further operative to determine the predicate and remaining elements of the sentence and to recursively search a linguistic head within the remaining elements of the sentence until the text components of the sentence are obtained,

wherein the parser includes a dictionary/grammar stage having an entry for the predicate and the linguistic head,

wherein the means for determining is operative to use the entry for the predicate and the linguistic head to exclude parsing alternatives resulting in grammatically incorrect formulation alternatives, and

means for producing partial information allocated to the sequence of the linguistic text components and, in case the modified text has information hidden in linguistic meanings of the linguistic text components, to the linguistic meanings of the linguistic text components, said means for producing partial information producing the same partial information which, in hiding the information to produce the modified text, was allocated to the sequence of linguistic text components and optionally to the linguistic meanings of the linguistic text components,

wherein the partial information allocated to the simultaneously possible formulation alternatives for a sentence result in an overall probability of 1.0 such that arbitrary information can be hidden in the text,

wherein the means for producing is operative to use, for the allocation of partial information to the simultaneously possible formulation alternatives, an existing probability distribution or a probability distribution generated in accordance with specific rules known to a device for extracting hidden information from a text,

wherein the means for producing is operative to not produce partial information from a sentence when valid formulation alternatives can not be found by the means for linguistically analyzing,

means for combining the partial information that was produced for the modified text by said means for producing partial information, in order to obtain the information hidden in the modified text; and

means for outputting the hidden information.

21. A device according to claim 20,

wherein the partial information is in the form of weightings, with said means for combining the partial information carrying out arithmetic coding for extracting the hidden information.

22. A device according to claim 20,

wherein said partial information is in the form of simple or canonical, in particular prefix-free, Huffman code words, wherein said means for combining the partial information is operative to carry out Huffman coding, in which code contexts used for Huffman coding are selected by said means for producing and correspond to the code contexts that were utilized when hiding information.

23. A device according to claim 20,

wherein the partial information that was used in hiding first relates to the sequence of the linguistic text components and thereafter to the synonyms of the linguistic text components in a predetermined sequence, and wherein said means for combining the partial information is arranged to derive from the sequence of the linguistic text components of the modified text firstly the partial information relating to the sequence and then, on the basis of a predetermined sequence of the linguistic text components, to successively derive the partial information allocated to the individual linguistic text components.

24. A device according to claim 20,

wherein said means for producing partial information further comprises:

means for determining a plurality of formulation alternatives for the modified text by varying the sequence of the linguistic text components and/or by using synonyms or paraphrases for the linguistic text components, each formulation alternative being grammatically correct for the text and having substantially the same meaning as the text, with each sequence and/or each synonym or each paraphrase having specific partial information allocated thereto,

wherein said means for producing partial information is arranged to access said means for determining a plurality of formulation alternatives, in order to retrieve the partial information relating to the sequence and/or the linguistic meaning of the linguistic text components of the modified text.

30. A method for extracting information hidden in a modified text, the modified text having at least one sentence, comprising:

linguistically analyzing the modified text to produce linguistic text components of the modified text, the linguistic text components being components of the sentence and the sentence, in addition to at least one additional component, having exactly one linguistic head as component;

wherein the step of linguistically analyzing comprises parsing by recursively breaking down the sentence into the text components using a hierarchical tree structure, and by determining the predicate and remaining elements of the sentence and by recursively searching a linguistic head within the remaining elements of the sentence until the text components of the sentence are obtained,

wherein the step of parsing furthermore comprises using a dictionary/grammar stage having an entry for the predicate and the linguistic head,

wherein the means for determining is operative to use the entry for the predicate and the linguistic head to exclude parsing alternatives resulting in grammatically incorrect formulation alternatives;

producing partial information allocated to the sequence of the linguistic text components and to the linguistic meanings of the linguistic text components, with the same partial information being produced which, in hiding the information to produce the modified text, was allocated to the sequence of linguistic text components and, in case the modified text has information hidden in linguistic meanings of the linguistic text components, was allocated to the linguistic meanings of the linguistic text components;

wherein the partial information allocated to the simultaneously possible formulation alternatives for a sentence result in an overall probability of 1.0 such that arbitrary information can be hidden in the text,

wherein the step of producing comprises using, for the allocation of partial information to the simultaneously possible formulation alternatives, an existing probability distribution or a probability distribution generated in accordance with specific rules known to a device for extracting hidden information from a text,

wherein the step of producing comprises to not produce partial information from a sentence when valid formulation alternatives can not be found in the step of linguistically analyzing,

combining the partial information that was produced for the modified text by said step of producing partial information, in order to obtain the information hidden in the modified text; and

outputting the hidden information.