[messaging] Deniable authenticated group messaging

[Ximin Luo]

On 17/04/15 19:37, Ben Laurie wrote:
> 
> On 17 April 2015 at 11:54, Michael Rogers <michael at briarproject.org <mailto:michael at briarproject.org>> wrote:
> 
>     Members should be able to send messages to the group, such that any
>     member of the group can verify that a message was written by the owner
>     of a particular signature key, but can't prove it to anyone outside the
>     group.
> 
> 
> Isn't this a fantasy requirement? That is, if I am a member of the group and I want to prove it to someone outside the group, don't I just have them look over my shoulder?
> 

Under lesser attacks, ciphertext deniability is achievable and useful. The problem can basically be reduced to a zero-knowledge proof [1]:

Peggy the Prover wants to convince to Victor the Verifier that message M was written by her, without Judge Judy being similarly convinced (using information from the protocol run *only*, e.g. ciphertext transcript, ignoring real-world other events).

Whether this is achievable depends on the security assumptions you make. Off the top of my head (might be inaccurate; reader please do your own research):

- If Victor and Judy co-operate[2] during the session ("deniability vs online judge") as you say, then the strongest we can achieve is "deniability with incriminating abort" [3] which means if the protocol succeeds, then Peggy can be assured that she has ciphertext deniability, but if it fails, then this may have been compromised.

- If Victor and Judy do not co-operate during the session, then ciphertext deniability is achievable fairly easily as per usual ZKP protocols.

The "rough reason" this works (and how many ZKPs work) is that after the protocol finishes, the information on *dependencies between the ordering of messages* [4] is unrecoverable. Victor saw the actual protocol run, so he knows this information, but Judy doesn't and there is no way for Victor to prove this information to Judy - since good protocols are constructed such that fake runs can be generated. (The ZKP term is "simulator".)

Note that even in your scenario, "have them look over my shoulder" can be faked by photoshop / video editing.

Please let's not get into yet another discussion between ciphertext deniability (cannot prove to third parties) and plausible deniability (cannot give any extra confidence to third parties, even from non-ciphertext information such as metadata records).

X

[1] though this is *not* how OTR does things, and consequently achieves a lesser kind of ciphertext deniability
[2] gives Judy the private key, or else if Victor doesn't want to reveal his key, he can run some sort of interactive protocol with Judy such that Judy doesn't need to have the key but is still convinced Victor executed the protocol correctly, and gains the same amount of knowledge that Victor does - http://phrack.org/issues/68/14.html
[3] Composability and On-Line Deniability of Authentication http://link.springer.com/chapter/10.1007%2F978-3-642-00457-5_10
[4] e.g. the fact that a hash commitment was made *before* it was revealed

sorry for non-https links, secure ones weren't available

-- 
GPG: 4096R/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git