Suppose you would like to prove authenticity of messages where the message space is small. Suppose the meaning of the message depends highly on the context, e.g. on time but also on events that are hard to encode, like political or social events. An extreme example would be a message space of "yes" or "no" (1 Bit), which are obviously context-dependent. Consider, e.g., the answer to the question: Do you love me? It also depends on who asked the question.
If you just use digital signatures, someone could just replay a pair of a message and a digital signature in a different context, giving it a completely different meaning, but still using someone else's correct signature.
How could you prevent these replay attacks?
I first thought of randomisation/salting, but all the probabilistic encryption schemes that I know use public salt, so an attacker could just re-use the salt as well.
Disclaimer: I'm not planning to build my own crypto. I'm just wondering how this problem could be solved, since to me, it doesn't seem so far away from reality...