[MLS] Idea for Issue #33

[Nick Sullivan <[e-mail]>]

Hello all,

Relaying some ideas that I posted in the Github issue that allow a
participant that was maliciously removed from the group by a bad update
message to publicly prove that it was given an inconsistent update. This is
an idea based on lightweight zero-knowledge proofs.

https://github.com/mlswg/mls-protocol/issues/21

Recall the following from ECIES:
Say that you are encrypting a ciphertext *X* to a user with private key *a*,
public key *A* (= aP) and elliptic curve base point *P*. The ECIES
ciphertext is the pair *(rP, c)* where *r* is a randomly-chosen scalar and
*c* is the encryption of X with a key derived from *k*=KDF(rA)=KDF(raP).

The key to this mechanism is revealing enough to prove to a third party
that an update received by the user is decrypted to an inconsistent X than
an update received by another participant, but without revealing the
private key *a *(which would compromise the confidentiality of previous
messages).

Proposed modifications of the protocol:
1) Add a mechanism that allows a party with access to a supposed secret
value of a node to validate the consistency of the chain of hashed derived
from that secret. This could be implemented by creating a public value that
consists of a KDF of the secret value with a known public value for every
node that is being updated. To check a secret value, the validating party
needs to compute the KDF for every node up the tree to the root and compare
with the published values.

The KDF acts as sort of a public integrity hash of to the node's secret
value.

2) Add a Schnorr NIZK of knowledge (RFC 8235) of the random value r with
every ECIES ciphertext. This proves that the r used in the ECIES encryption
is known to the updater and rP is not trivially derived from some other
previously sent r'P.

For one participant to prove that they were given an update message that
did not include the correct node secret, that participant can reveal the
following:
arP, DLEQ(arP:rP :: P:aP)

Where a is the node's private key, and DLEQ is a discrete log equivalence
proof that shows that arP is rP multiplied by the private key *a* of the
user.


So in summary, we would add:
- Proof of knowledge of the randomness used in ECIES
- Public KDF of each node's secret value
and then a member could prove to an auditor that it was given the wrong
secret by revealing:
- an intermediate calculation of the ECIES decryption, a DLEQ proof that
the right key was used


I'm eager for this proposal to have some holes shot in it.


Nick