Oxana Poburinnaya: Fully bi-deniable interactive encryption

Friday, November 9, 2018 - 10:30am to 12:00pm
32-155 (please make note of location)
Oxana Poburinnaya, Boston University
Abstract: Deniable encryption guarantees an extremely strong level of privacy: It provides the parties with algorithmic ways to come up with fake keys and random inputs that  ``open''  the public communication to any plaintext of  the parties' choice. This allows the actual plaintext to remain hidden even in face of an after-the-fact attacker that coerces the communicating parties  to disclose all their data, keys, and local random choices.   However, to date we only have public-key encryption schemes that provide partial deniability guarantees: Either deniability only for the sender, or only for the receiver, or a weaker form of deniability where the fake keys and random input are only consistent with different algorithms than the ones used.
We construct the first encryption protocol that provides full deniability even when both the sender and the receiver are coerced, separately, with respect to the same interaction. Furthermore, our scheme satisfies an additional property which we call  off-the-record deniability: when the parties` accounts  are inconsistent with each other (i.e. the sender claims it sent m, but the receiver claims it received m'!=m), off-the-record deniability guarantees that there is no way for the coercer to tell which one is lying. Our protocol has three messages, which is tight with the known impossibility of Bendlin et al (Asiacrypt 2011) for two-message protocols. We assume sub-exponential indistinguishability obfuscation (IO) and one way functions, and work in a model where all parties have access to  public obfuscated programs (these programs can be generated in advance and then reused arbitrary polynomial number of times). 

Our construction involves program with a special hidden logic that thwarts all potential adversarial recombinations of pieces of a transcript and random inputs to the parties. To show that this logic suffices even when protected only by IO, we employ techniques which are traditionally used in the ``iterated circuits'' setting, such as the construction of garbled Turing machines from circuit-IO.
Joint work with Ran Canetti and Sunoo Park