Re: [MLS] Revisiting Deniability

Natanael <> Wed, 12 April 2023 21:59 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id A0516C15154A for <>; Wed, 12 Apr 2023 14:59:47 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.096
X-Spam-Status: No, score=-0.096 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001, URI_DOTEDU=1.999] autolearn=no autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id nrfvfw-SGQxI for <>; Wed, 12 Apr 2023 14:59:43 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::636]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by (Postfix) with ESMTPS id 5DF21C15153F for <>; Wed, 12 Apr 2023 14:59:43 -0700 (PDT)
Received: by with SMTP id f26so26390331ejb.1 for <>; Wed, 12 Apr 2023 14:59:43 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20221208; t=1681336781; x=1683928781; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=eW5ndDx0efHxC+9yfnoHnV6NG7rG38PsGi8ApWbBkqs=; b=p4q6pBqTjq77lrDHpZEi61NVh//2WRRHVip1Z5YVQYsm9soS9nfCxx/+GsuwUDCKEG OwXGfQtSYeLKtVn57qVLIXFQyaS8ZIllJ8HCCCiYNjn5D9eHlNrnbiPaeEjKD3A+0KuS nY1kwJ5uy168q7DDWTl3swfsQmEFFdaC+YgzalnBWJugfA4+hPEnVk4LPYzrPN6cfZF0 BY5kNBCm2COlYmfvtkx26veP6aoGiTriynCwpq9BZT74JmVPFB9wjGN7l3COuWrH/dlE lss4oxrwe/cFdK9wfUrfSR7vckwGL3Ri9nD19wRtXFotGdslsfF8Nzt7V9HzeaZEwXEo K9gg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20221208; t=1681336781; x=1683928781; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=eW5ndDx0efHxC+9yfnoHnV6NG7rG38PsGi8ApWbBkqs=; b=SPkJPTxTQ1kx5DlEQK2M7iiMqt11aDUBb3J8bS97zfb0KyUTHUmXTOc8t0bTbkQaZI mRhLIL858NaLNj8tTXtDlHrKwDpTKjj7KqETvV8zh3HfiGuEii1O8fliKu3HUy7vj1KH teeGJgWlnGKsbLVp+DhQcAo9nfSHvwRg0wdPfR2n2ZP38+2iOM89w8kNwvwfD5zeeeL7 HoHR1sEV8NNfSRafUpe7G+urnhlypHF99SpxyzoqKagYsYNDAuT8JhrTRv6ypFlPM06Y ZRVaVDEu7U4akiLmykaNcFE39mE77eXWa+oBBj4gTysDCsk3EyQHfF8EU5svfzUstJRM ViLw==
X-Gm-Message-State: AAQBX9fqh2GG+0sHklOpr5tVjUwRg09z3xuJZw8aVDETTkzJcGlPuX81 /z9DpwWVHpGdENI6GL9QQZWow9OQJyNRS8ZSUu8=
X-Google-Smtp-Source: AKy350YJFcP8Qm9chBF2ZB8zF2zPm5v7HcBou7e6fcWqOnYN3tdZy76K9NE5+0YelOm4/JC+5aoOBpxUUKL1wPH5SLg=
X-Received: by 2002:a17:906:c455:b0:94a:5691:b12b with SMTP id ck21-20020a170906c45500b0094a5691b12bmr178470ejb.11.1681336780847; Wed, 12 Apr 2023 14:59:40 -0700 (PDT)
MIME-Version: 1.0
References: <>
In-Reply-To: <>
From: Natanael <>
Date: Wed, 12 Apr 2023 23:59:30 +0200
Message-ID: <>
To: Brendan McMillion <>
Cc: MLS List <>
Content-Type: multipart/alternative; boundary="00000000000091fdca05f92ab99e"
Archived-At: <>
Subject: Re: [MLS] Revisiting Deniability
X-Mailman-Version: 2.1.39
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 12 Apr 2023 21:59:47 -0000

Den ons 12 apr. 2023 23:41Brendan McMillion <>

> 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 other things which are close to hypothetical deniable signatures.

Cryptographically self expiring signatures, for example, where a valid
signature later becomes indistinguishable from a forged one (it's related
to your ZK idea);

Users could also create a session signing keypair and publish its private
key encrypted with a VDF to create delayed disclosure without needing to
remain active.

You can also do ring signatures such that only one user in a group needs to
disclose a private key.

> 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.
> 2.
> 3.
> _______________________________________________
> MLS mailing list