2
$\begingroup$

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)?

$\endgroup$
12
  • $\begingroup$ 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. $\endgroup$ – Daan Bakker Jun 23 '16 at 18:42
  • $\begingroup$ @DaanBakker That would require Eve to trust at least one of Alice and Bob, otherwise they can agree to lie to Eve. $\endgroup$ – fkraiem Jun 23 '16 at 19:15
  • 2
    $\begingroup$ (Moreover, Eve obviously cannot trust Alice; otherwise Alice can always prove to Eve that $b$ was sent, just by telling her "$b$ was sent".) $\endgroup$ – fkraiem Jun 23 '16 at 19:21
  • 1
    $\begingroup$ This task looks like it would be quite tricky to define in the first place, even before going into whether it is achievable. $\endgroup$ – fkraiem Jun 23 '16 at 19:24
  • 1
    $\begingroup$ @dandavis : ​ ​ ​ If indistinguishability obfuscation is theoretically possible then what the OP is asking about is theoretically possible. ​ (See my answer.) ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user991 Jun 26 '16 at 2:59
1
$\begingroup$

By this paper, indistinguishability obfuscation is enough for that.

$\endgroup$
6
  • 2
    $\begingroup$ 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? $\endgroup$ – SEJPM Jun 24 '16 at 12:24
  • $\begingroup$ 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." $\endgroup$ – TLW Jun 24 '16 at 15:03
  • $\begingroup$ @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)? $\endgroup$ – Daan Bakker Jun 24 '16 at 15:24
  • $\begingroup$ 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. $\endgroup$ – TLW Jun 24 '16 at 15:43
  • 1
    $\begingroup$ @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". ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user991 Jun 24 '16 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.