Assume Alice and Bob communicate over an insecure channel using one-time perfectly-secret encryption together with one-time secure message authentication code. Say Eve has the ability to eavesdrop and to inject messages into this insecure channel, but not to block or delay messages (i.e. Eve can mostly only replay authenticated encrypted messages).
Of course we can design scenario damaging to Alice and/or Bob. How can they protect themselves against such replay attacks?
