I am currently writing my Bachelor's thesis on steganography and stumbled across a hashing algorithm linearizing a paraphrasing problem. I understand the first (and much easier) part of it but cannot make any sense of the second part (in bold):
For a given tweet, the value is determined by getting a keyed hash digest for each individual word (here using 4 Bits from a hash generated using the MD5 algorithm), bitwise rotating each value according to its position in the tweet, then exclusive-or-ing these values together. Partial hash values are calculated for each index of the tweet. A table is constructed, mapping an index and a possible hash value to paraphrase substitutions that will result in the given hash value up to this index in the tweet; these substitutions are paired with the partial hash value required up to the previous index in the tweet.
Explanatory background needed for understanding the paragraph above:
The idea of this algorithm is to linearize the search for valid paraphrases of I like Twitter a lot regarding their hashes, e.g. all of the following sentences could be deemed valid in a 'language correctness' sense, but only some of them produce the desired hash (which is known in beforehand)
- I like Twitter lots
- I like Twitter really much
- I love Twitter a lot
- I like Twitter very much
Therefore, my current programmatical approach involves backtracking through paraphrasing rules, getting every grammatically and meaningwise valid sentence and then hashing all of them in order to get a collection of the paraphrases I am actually looking for (i.e. grammatically and sensical tweets producing the desired hash).
The described algorithm claims to linearize my approach by somehow only generating the paraphrases which are guaranteed to produce the desired hash, but I can't wrap my head around how it achieves this.
I came as far as exclusive-or-ing the different values together, as can be seen in this example using made up bit values for each word
| Step | |||||
|---|---|---|---|---|---|
| Original Tweet | I | like | a | lot | |
| Extracted 4 Bits | 0000 | 1010 | 0111 | 1100 | 1001 |
| Rotated bitwise | 0000 | 0101 | 1101 | 0110 | 1001 |
The exclusive-or-ed value would then be 0000 XOR 0101 XOR 1101 XOR 0110 XOR 1001 = 0111
I would now need to understand the structure and functionality of this 'table' approach and would appreciate any help or insights very much!