One feature that is often underlooked of the One-Time Pad is its perfect deniability. i.e. If Alice sends a message to Bob that is seen by Eve then if Eve later goes to Alice with the ciphertext and tries to force Alice to disclose her key Alice can "make up" a key and Eve can't prove that the key Alice provided was the real key or not.
One downside of the OTP is its malleability. So a common suggestion is to append a MAC so Bob can see if the message was tampered or not.
I am curious if it was possible to construct a MAC such that if Eve tries to retrieve the key from Alice, Alice can "make up" a key for the MAC and Eve can't prove that that was the real key. i.e. Given a plaintext and MAC Alice can construct a real looking "fake" key in polynomial time. For example HMAC will not satisfy this property because otherwise it would be prone to preimage attacks.
Is this a good definition for perfect deniability of a MAC?
- Realistically none since the OTP is impractical.
- If Alice and Bob are on an anonymous network (example TOR) then Eve cannot prove who sent the message, but Bob can confirm it was sent from Alice and if it was tampered with
- If Alice posted this in a public place (like a forum, blockchain or public bulletin board) nobody can prove Alice posted it (assuming she posted it anonymously) but Bob can confirm it was sent from Alice and if it was tampered with
- Can you think of other applications?