Consider a text with $n$ words which $m$ words of it can be replaced with an equivalent word. Therefore we have $2^m$ different texts with the same meaning.

For example "You are {so/very} {keen/eager}" has 4 different combinations with the same meaning.

Is it reasonable and possible to use this property for message authentication?

More precisely, knowing a key, only one of these texts can be authenticated. Actually, I do not want to add anything (like HMAC) to the text.

  • $\begingroup$ You could use the $2^m$ bits to encode a MAC for e.g. the message with all zero bit words. $\endgroup$
    – otus
    Nov 12, 2015 at 6:23
  • $\begingroup$ @otus In this case we have to append that MAC. I do not want to send anything more than the text itself. $\endgroup$ Nov 12, 2015 at 6:31
  • $\begingroup$ No, I meant storing the MAC value in the word choices. So if M("You are so keen") = 10 (binary) then you would use the message "You are very keen". $\endgroup$
    – otus
    Nov 12, 2015 at 6:35
  • $\begingroup$ So what is the key here? Is it a database of binary representations of words? $\endgroup$ Nov 12, 2015 at 6:40
  • $\begingroup$ Sorry, I omitted the key above. The MAC algorithm would use a key. The verifying user would also need to know the word pairs to find the message that was used for the MAC. $\endgroup$
    – otus
    Nov 12, 2015 at 6:42

1 Answer 1


One solution is to use the choice of which equivalent message you send as a way to encode a MAC value.

  1. Take a "base message", where e.g. each word choice is the alphabetically first one. (Or some other known rule.)
  2. Calculate the MAC for that: MAC(key, message). The MAC should be $m$ bits or less. HMAC, possibly truncated would work fine.
  3. Encode that MAC value in the word choices, so that each bit chooses one of the words.

The recipient would need to know the possible word changes (synonym pairs). They would first use the rule to derive the same base message, then compute the MAC using the shared key, and finally check that the same value is encoded in the word choices.

A similar algorithm would work for public key signatures if you had a sufficiently long message. The recipient would decode the signature value from the word choices and use normal signature verification with the base message and a public key.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.