[MLS] Revisiting Deniability

[Brendan McMillion <[e-mail]>]

Hi @mls

In the past, the working group came to consensus that the best way to
support deniability in MLS was to make the authentication layer deniable.
That is to say, the protocol would continue using non-repudiable signatures
as normal, and however users come to associate a signature public key with
a user identity would just need to be deniable.

I don’t really like this model because deniable authentication is
incompatible with a transparent authentication mechanism like Key
Transparency. I think we definitely want the Authentication Service to
*not* be able to deniably distribute malicious public keys for users. We
want a strong guarantee that we’re actually talking to the user we think
that we are, while still not being able to prove to a third party that our
conversation actually happened. This is akin to TLS where the
authentication layer (a certificate from a CA) is transparent and
non-repudiable, while the encryption layer (TLS itself) is deniable.

There have also been several proposals for deniability in MLS that rely
crucially on users disclosing their private key after some amount of time
has passed. I don’t think this approach is great either given that MLS is
an asynchronous protocol and users are supposed to be allowed to be offline
for significant amounts of time.

In short, to resolve this, I think we should probably publish an extension
document on using the protocol with “deniable signatures”. “Deniable
signature” is in quotes because that’s not a real primitive. But roughly,
we want to authenticate messages with a value that is: 1.) a function of
the message the user is sending, 2.) publicly verifiably correct, and 3.)
computable by either the user sending the message or all other users of the
group in collusion.

There are a few options for how to construct this that come to mind:

- Pairwise Signatures/MACs. Users authenticate each message with a series
of signatures/MACs, where each signature/MAC key is known only by that user
and one other user in the group, for each recipient user.

- Verifiable Key Escrow like [1] or [2]. Users sign their messages with a
private key that is verifiably escrowed to all other users of the group.

- NIZKPOK of a Signature. Users sign their messages with a private key but
instead of revealing the signature directly, they publish a non-interactive
zero-knowledge proof of knowledge of the signature. The challenges in the
non-interactive proof are generated with a trapdoor function, where the
trapdoor can be recovered by all other users of the group in collusion.
This makes the zero-knowledge proof simulatable (and hence deniable) with
knowledge of the trapdoor. A good trapdoor function might be something like
[3].

Is there group interest in publishing such a document? Is there anyone else
that wants to help write it?

1. https://github.com/ZenGo-X/dlog-verifiable-enc
2. https://www.shoup.net/papers/verenc.pdf
3. https://eprint.iacr.org/2018/529.pdf