How to deniably send a value

Alice has a single bit of information, b, that she wants to send to Bob (over an unalterable but possibly-monitored channel) but in such a way that without the cooperation of Bob she cannot prove to anyone else (Eve) besides Bob after-the-fact that she sent b and not 1-b.

Is this possible? I am thinking perhaps not, because in any protocol Eve could step through the inputs Alice receives from Bob with both b and 1-b, and check which one of those the output she sends back to Bob matches. Even if the protocol is non-deterministic Alice could record the random values for Eve - but perhaps there is some way in which the random values could be set up to be trivially spoofed to indicate the other value to Eve after-the-fact (and hence Eve would not be able to trust Alice)?

• Would a simple one-time-pad suffice? Unless both bob & alice would confirm they were both using the same key, it will always be possible for bob to easily claim that a different key was used resulting in another valid message. Jun 23, 2016 at 18:42
• @DaanBakker That would require Eve to trust at least one of Alice and Bob, otherwise they can agree to lie to Eve. Jun 23, 2016 at 19:15
• (Moreover, Eve obviously cannot trust Alice; otherwise Alice can always prove to Eve that $b$ was sent, just by telling her "$b$ was sent".) Jun 23, 2016 at 19:21
• This task looks like it would be quite tricky to define in the first place, even before going into whether it is achievable. Jun 23, 2016 at 19:24
• @dandavis : ​ ​ ​ If indistinguishability obfuscation is theoretically possible then what the OP is asking about is theoretically possible. ​ (See my answer.) ​ ​ ​ ​ ​ ​ ​ ​
– user991
Jun 26, 2016 at 2:59

By this paper, indistinguishability obfuscation is enough for that.

• As it stands this is pretty much a link-only answer. Would you mind expanding it a bit to give people an idea on how this works/ how this notion does what the OP needs? Jun 24, 2016 at 12:24
• I'd like an elaboration, but this certainly seems to be exactly what I'm after: "In deniable encryption, a sender who is forced to reveal to an adversary both her message and the randomness she used for encrypting it should be able to convincingly provide “fake” randomness that can explain any alternative message that she would like to pretend that she sent. We resolve this question by giving the first construction of deniable encryption that does not require any pre-planning by the party that must later issue a denial."
– TLW
Jun 24, 2016 at 15:03
• @TLW That seems impossible to me. If the exact same ciphertext can be created by using 2 different messages how will the receiver ever be able to differentiate between the two (without pre-shared information)? Jun 24, 2016 at 15:24
• I don't know - that's a direct quote from the paper, and I'm still reading through it. I suggest you do the same.
– TLW
Jun 24, 2016 at 15:43
• @DaanBakker : ​ ​ ​ ​ ​ ​ ​ ​ The "simplest" way would be if for each possible ciphertext c, the probabilities of ​ [encrypting 0 gives c] , [encrypting 1 gives c] ​ differ by at least an exponential factor and the receiver can tell which case is more likely. ​ ​ ​ (I don't know if they actually achieve that or instead get an exponentially-small error probability in a different way.) ​ ​ ​ See section 4, "Our Deniable Encryption System". ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​
– user991
Jun 24, 2016 at 23:32