Re: [MLS] Re-randomized TreeKEM

[Joel Alwen <[e-mail]>]

> - Every time a member A sends an update, it generates fresh node secrets
> for nodes on the path from A to the root
> - From each node secret, A generates a large number K (= 100)
> private-public encryption keypairs and sends the public keys with the
> update.
> - On receiving the update, each member B stores all K public keys for
> each node in its co-path
> - Each of these public keys can be used only once for sending an update,
> after which the private key is deleted from all recipients.
> - The last public key at each node is not deleted; it can only be
> replaced when one of the members under that node sends a new update
> (with a fresh batch of public keys).
> 
> As far as I understand, the above scheme can be seen as an (inefficient)
> implementation of UPKE, right?

I think your right. I think its similar to UPKE with the caveat that
only K ciphertext can be sent per call to UPKE-KeyGen. (In other words,
as you point out below, after K nodes encrypted to a ciphertext it
effectively becomes blank.)

But I think it does achieves the same properties for TreeKEM as the UPKE
constructions based on re-randomization, at least for the corruption
model we've been looking at.

> Of course, it increases the size of each update by K, and only provides
> FS for K updates, after which some member has to send an update.
> Conversely, it does not require any new crypto algorithm. Is this a good
> baseline to compare UPKE schemes against?

Well, its close but but has the limit on how many ciphertexts can be
sent to any given key-pair which UPKE normally doesnt have. On the other
hand if sender knows the old SK and then they can compute the new SK in
UPKE which is not the case in your construction. So I'd say its (at
least formally speaking) incomparable to UPKE.

- Joël