Fully Bideniable Interactive Encryption | Hacker News Reader

Fully Bideniable Interactive Encryption

eprint.iacr.org

114 pointslainon36 comments

That's some dedication from Ran Canetti. The abstract gives the two bits of information, but it never connects them explicitly (writing is very formal): he was the author of the original paper that presented the problem in '96, and now he finally managed to find a valid solution for it, 22 years later. Well, I only understand the basics of crypto, but props to the man.

In this field (theoretical computer science / math), authors are always listed in alphabetical order. Ran Canetti was alphabetically first on both the paper that introduced the notion of deniable encryption, as well as on this paper. The main contributor for the current paper was Oxana Poburinnaya. This is not "officially" listed anywhere, but I know all three authors personally, have talked to them about this paper, and I got the impression that Oxana wrote > 200 of these 250 pages.

See also: the long history in science of the women who did the work getting second billing or none at all.

Sources? This will be great to motivate daughters.

Hackaday did a whole series on historical scientists, most of them women. I'd start there.

Edit: Here's a direct link https://hackaday.com/category/biography/

Just Google "women that did not get the nobel prize".

Marie Curie only got her first Novel Prize because Pierre Curie refused to accept it unless it was shared with his wife.

Off the top of my head, Rosalind Franklin made major contributions to the discovery of DNA, but Watson, Crick, and Wilkins got the Nobel Prize.

Yes, but if I remember correctly, it was because she died before they gave the prize and they have the rule not to give it to dead scientists. To date there should have been only one exception were they gave the prize to someone that died only a few days earlier and they didn't knew it, once they knew they didn't felt like taking the prize back so this should be the only exception.

It wasn't just the Nobel, though. Her contribution was largely ignored until quite recently.

That's interesting, thanks for sharing. Anyway, didn't mean to diminish anyone else's work, and I know it's very hard to tell from the outside how much each person contributed.

I should have added that, more importantly, she also had the key technical "eureka" moment; her contribution was not only to do the writing.

The authors of the 1996 paper that introduced the notion of Deniable Encryption are, alphabetically, Ran Canetti, Cynthia Dwork, Moni Naor, and Rafail Ostrovsky. It’s not correct to call any one of them “the author”.

http://www.wisdom.weizmann.ac.il/~naor/PAPERS/deniable.pdf

> deniable encryption [Canetti et al., Crypto’96] provides the additional guarantee that the plaintext remains secret even in face of authoritative entities that attempt to coerce (or bribe) communicating parties to expose their internal states, including the plaintexts, keys and randomness. To achieve this guarantee, deniable encryption is equipped with a faking algorithm which allows parties to generate fake keys and randomness that make the ciphertext appear consistent with any plaintext of the parties’ choice.

Does the faking algorithm for the scheme proposed in the paper require any of the private information as input? In other words: given a ciphertext only, can I come up with keys and randomness to provide an arbitrary plaintext?

OTP for example does have this property, I can just simply XOR the plaintext I want to have with the ciphertext and claim that this is the key.

Edit: this question is relevant as if the private information is needed, it might limit your options once you do give them fake stuff. If some party can prove that the fake plaintext/key pair you gave them is indeed fake, then you should be able to walk back on your claims and say that you never had the plaintext or forgot the password or whatever.

The idea of "bideniability" is defined early in the paper as meaning that there is no way for an adversary to distinguish between real and fake (key, randomness, message) sets, even when they receive one of those from both the sender and the receiver. So, by that definition, no plaintext can be proven to be fake in a bideniable system. It doesn't matter whether sender and receiver both lie, or whether only one of them does.

I haven't read far enough to be able to answer the first part of your question (does faking require access to the real ciphertext) but based on the symmetry of the definition of bideniability, that would be surprising.

So I've had a little look at the paper and the first part of my question is addressed by their term "public deniability". Apparently they have public denyability for the receiver side, but not the sender side. So everyone can claim that they were the recipient of the message with X being its content, but only someone who knows the sender secrets can claim authorship.

I wrote a program, stes[1], back in 2000 which did something similar (but less complex): it created a ciphertext C which could be decrypted to different plaintexts dependent on key, so K1 produces P1, K2 produces P2, etc, and there was no way of proving there were or weren't any more keys.

[1] see https://github.com/cabalamat/stes/blob/master/SPECIFICATION

I must read too much about politics, I took the title as a dig against former VP Biden, rather than "bi-deniable". :-)

I see potential for application in Australia, given the new "mandatory backdoor" thing they've got going. Just claim you've made a back door for the government, then use a scheme like this and provide them only bogus keys.

It goes without saying that you can't provide a key in advance that will result in convincing "fake" plaintexts for every encrypted message you send. The content of the fake plaintexts has to be fully encoded in the key+any "randomness" value (it can't come from anywhere else).

Awesome maths.

A practical problem I see is that even if everyone used this everywhere, an attacker has no reason to believe any forceably decrypted plaintext.

The disclosing party would have had to beforehand craft a fake plaintext that was credible enough to trick an alerted attacker based on its contents alone.

If an adversary demands the key to decrypt a given ciphertext, what stops the sender or receiver from claiming that it was encrypted by a onetime pad (i.e., a bitwise exclusive-or with the encryption key) and then furnishing the "key" that "decrypts" it to some unrelated plaintext of his choice? Not to diminish the authors' work, but if this is the problem of deniable encryption, I don't get why it isn't trivial. Any advice?

From the article:

"When the communicating parties have common secret key, deniable encryption can be simple. For instance, the one-time pad (OTP) scheme is perfectly deniable: having sent c = k ⊕ m, the parties can claim that they sent any plaintext m0 by claiming that k0 = c ⊕ m0 is their true key. In fact, it turns out that the key size in any deniable encryption scheme has to be at least as large as the size of a plaintext (since there should exist a different key for any possible fake plaintext), and in this sense OTP is “the best possible” symmetric-key deniable encryption.

But what if no pre-shared secret key is available? Is it possible to communicate fully deniably even in this case?"

It probably comes down to a question of specifying whether the treat model includes an adversary who can coerce both parties and check that their plaintexts agree. Otherwise, I wouldn't see any need for a shared secret key because the ciphertext can be encrypted by any method at all. The onetime pad is used only by the person under coercion and only for the purpose of misleading the adversary.

Yeah, they've got that covered too. The second paragraph of the paper says that they're working with the notion of "deniable encryption" introduced in a paper by Canetti et al: http://www.wisdom.weizmann.ac.il/~naor/PAPERS/deniable.pdf

Here's the abstract of the Canetti paper:

"Consider a situation in which the transmission of encrypted messages is intercepted by an adversary who can later ask the sender to reveal the random choices (and also the secret key, if one exists) used in generating the ciphertext, thereby exposing the cleartext. An encryption scheme is deniable if the sender can generate ‘fake random choices’ that will make the ciphertext ‘look like’ an encryption of a different cleartext, thus keeping the real cleartext private. Analogous requirements can be formulated with respect to attacking the receiver and with respect to attacking both parties. Deniable encryption has several applications: It can be incorporated in current protocols for incoercible (“receipt-free”) voting, in a way that eliminates the need for physically secure communication channels. It also underlies recent protocols for general incoercible multiparty computation (with no physical security assumptions). Deniable encryption also provides a simplified and elegant construction of an adaptively secure multiparty protocol. In this paper we introduce and define deniable encryption and propose constructions of such schemes. Our constructions, while demonstrating that deniability is obtainable in principle, achieve only a limited level of it. Whether they can be improved is an interesting open problem."

I'm not sure how the paper under discussion relates to those applications, if at all.

I'm not sure I buy the argument you appear to be making that a single principal can use a fake OTP to achieve deniability with any encryption scheme, but that this breaks down when both sender and receiver are coerced. If the fake plaintexts don't match it comes down to one person's word against another. The consequences of that scenario are outside the scope of "deniable encryption". It sounds a bit like a prisoner's dilemma situation.

But the key defining feature of "deniable encryption" is of deniability within a specified encryption scheme.

Remembered me of the fun "Angecryption", where you can decrypt the ciphertext with AES or decrypt it with DES and get different plaintexts depending on the scheme: https://github.com/indrora/corkami/blob/master/src/angecrypt...

From the paper:

> To address this issue, Canetti et al. introduced the notion of deniable encryption, in which a party may send a ciphertext c which is an encryption of message m, and later, for any plaintext m2!=m, the party can reveal fake keys and randomness with respect to which c appears to be an encryption of m2

This is only really possible if your key is as big as m2, which in practise for many applications it would not be.

What does Bidenable mean? Google thinks I'm asking about Joe Biden, and that just makes me think there's an XKCD connection in there somewhere that would be super hilarious if we could just find it.

It's in the abstract. It says that prior to the paper you had to choose between one of two kinds of "deniability", now you can have both of them at the same time (bi-deniability).

It means both the sender and the receiver of the message, if coerced, can without coordination have a degree plausible deniability for the contents of the message.

For example, I send you the message "CIA" encrypted using this scheme. Theoretically, it should be impossible for any third party to prove that I send "CIA", because I can give up a different decryption key that decodes the ciphertext to, say, "NSA". Similarly, on the receiving end, you can give up a different decryption key that decodes the ciphertext to, say, "FBI".

This scheme also means it is impossible for a third party to discover who is giving up the 'truth' in such scenarios (for example if I told the truth and decrypted the ciphertext into "CIA", while you lied and decrypted the ciphertext into "FBI", the third party has no way to know which one is correct, or if either of them are fake).

Can you make sure the 'alternate' decoded version of the messages will actually decode into something legible? Is there some way to explicitly craft the alternate decoded message, or is it random?

Aha, thanks!

So it's effectively a duress code you might punch into a security system?

Two duress codes--one for you, and one for your counterparty. Thus, the bi- in bi-deniable.

Mono-deniable gives a duress code only to the sender, or only to the recipient.

The paper claims an additional category of bi-deniability, such that your duress code and your counterparty's duress code produce different plaintexts, rather than the same plaintext. It is unclear from the abstract whether it is possible to have a bi-deniable scheme without this property (which does not also require prior coordination between parties).

You misspelled bi-deniable (compare this to your biden-able). See the sibling comments for an explanation.

Heh, I actually thought the same thing, and it's not necessarily irrelevant.

As others note, it parses as bi-deniable -- it can decrypt on both ends into two plaintexts with plausbility.

But yes, I initially parsed it as Biden-y-able, which is surprisingly fitting [1] given Biden's ability to get away with any gaffe[2], which is analogous to what bideniable encryption gets you. So, a good mnemonic at least...

(Relatedly, I used to think git reflog parsed as re-flog "because you're only using this if you did something so stupid you want to flog yourself twice".)

[1] I hate the word "apropos".

[2] https://www.theatlantic.com/politics/archive/2014/09/why-joe...

This reminds me of Asimov’s observation that chemists tend to read “unionized” as “un-ionized” and not “union-ized”.

Reply on news.ycombinator.com