# Overview

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?

# Applications

• 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?
• I think you need to split this up into two questions: 1. is there such a construct (possible) and 2. a question if your construction matches the security requirements of a MAC. Asking questions in answers isn't allowed. – Maarten Bodewes Jun 16 '17 at 11:38
• Moved the protocol idea to crypto.stackexchange.com/questions/48360/… – edggy Jun 16 '17 at 14:23
• Are you assuming Eve can use the real-looking "fake" key to verify the original message sent? The issue I see is that Eve can always check to see whether the key is valid relative to the message and tag pair it already knows. – pg1989 Jun 19 '17 at 1:36
• Found this paper on deniable authentication: eprint.iacr.org/2005/046.pdf – pg1989 Jun 19 '17 at 1:39
• @pg1989, that is about a different problem: how to get deniability in a public key context. – otus Sep 16 '17 at 11:00

This is actually available widely to programmers: NaCl has crypto_onetimeauth which uses Poly1305 (a polynomial evaluation MAC) with the latter half of the single use key used as a one-time pad. To get the same MAC value for another message you can just compute the MAC, then modify the pad part to match your target.
Not all uses of Poly1305 give you perfect deniability, however. The ones where the key or pad comes from AES (Poly1305-AES) or another cipher (e.g. crypto_secretbox) likely do not because you cannot freely choose the value of it without affecting message decryption or the authentication of other messages.