Is it possible to have self-authenticated message?

Question

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.

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.