Ran Canetti Provides Proof of Fully Deniable Encryption and Computation

Boston University Computer Science Professor Ran Canetti gave a presentation at the recent Upgrade 2020 NTT Research Summit summarizing his recent paper that proves deniable encryption is possible even if both parties to a communication are compromised.

Back in 1997 Canetti and his collaborators published a paper (Canetti et al., Crypto 1996) proving the concept of deniable encryption, where the secrecy of a communication is protected even if one of the parties is coerced or bribed into giving up their encryption keys. Left open was the question of whether deniable communication is still possible if both parties are coerced.

With his latest paper, co-authored with Sunoo Park and Oxana Poburinnaya, Canetti provides an answer: yes.

In his talk, Canetti likened the concept of deniable encryption to two siblings ­– Violet and Jack-Jack Parr of The Incredibles – talking to one another through a lead pipe. They can say whatever they like to each other and their mother won’t know what they’re saying because the lead pipe acts as a secure channel. That’s a form of encryption, something we’ve been able to do in software for decades, Canetti noted.

Say Violet tells Jack-Jack she doesn’t want to do her homework and would rather watch a movie. Their mother asks Violet what she said to Jack-Jack. Violet tells her she said she was studying. The mother then asks Jack-Jack what Violet said and he also says Violet said she was studying. The mother has no way of knowing whether that’s actually what was said – it’s deniable communication. In fact, even if Violet said she was studying and Jack-Jack said something else – like that Violet wanted to watch a movie – the mother would have no way of knowing who was telling the truth, or if either of them were.

The question is whether a similar kind of deniable communication can be implemented in software and used for encryption. Further, the encryption scheme has to provide privacy even when both the message sender and receiver have been compromised.

It does so by creating multiple messages, some of which are fake. That means the intruder, or coercer, can’t know for sure which message is the “real” one.

The same concept can be used for computations, Canetti noted. Suppose Violet and Jack-Jack want to compute together but don’t fully trust each other. Say they both know some students who vape in school and want to determine if there’s one they both know. The deniable communication scheme would give them each a space to do their computations securely, so they could determine whether one student was on both of their lists without learning who else is on each respective list.  

Further, if the mother were to enter the picture and ask them if they know anyone who vapes in school, they could each say no – or whatever they wanted – and the mother would have no way of knowing whether they’re telling the truth.

Implementing such a scheme in software requires coming up with a shared key in a deniable way, Canetti said, so you can have a deniable key exchange. His team came up with a protocol for two parties to exchange a key with messages and a “faking algorithm” that will hide the real decryption key from an intruder.

In his talk, Canetti goes into the details and formulas that demonstrate how the encryption scheme works.

For the full transcript of Ran Canetti’s presentation, click here.

Watch Ran Canetti’s full presentation below.