Re: [MLS] Re-randomized TreeKEM

Hi Karthik.

Sorry for the short answer, about to drive for 4 hours ;).

Each user still stores at most log n secret keys on the path to the root
(and all public keys, unless retrieving them as needed). During each
operation where this user is not initiator, there will be precisely one
ciphertext this user needs to decrypt using one of these log n keys,  just
like before. In the original TreeKEM, after decrypting this ciphertext, the
public and secret
key for this encryption stays the same. In RTreeKEM, --- and this is the
main (and effectively only) difference, --- the public and secret keys for
this encryption change. In a way that the new secret key will be able to
decrypt ciphertexts encrypted under NEW public key, not not OLD public key.
In particular, new secret key will not be able to decrypt the ciphertext
that the user just decrypted. Given our global ordering assumption, this
does not get users out of sync, even if some and offline for long periods
of time.

So think of this as public key analog of a steam cipher. Where after each
decryption the steam cipher state changes to ensure forward secrecy. Here
the cute part is that the public key will be effectively changed by the
sender (who does not know neither new or old secret key), but in a way that
the recipient (and only the recipient!) can recover the matching secret
key. Intuitively, the sender will not only encrypt the message, but also a
random Delta value. It will change public key using homomorthism by
multiplying with g^Delta (in specific DH based scheme), while the recipient
will decrypt Delta (using old secret key), and add it to the old secret key
to get there new one. So now corrupting (old sk plus Delta) will not help
decrypting the ciphertext just decepted, emailing forward secrecy. So very
small cost compared to the original TreeKEM (see our earlier email for more
details). And really the same scheme, modulo PKE  being stateful ala a
steam cipher.

This is the high level, hope it makes sense.
Thanks for your question,
Yevgeniy

On Thu, Oct 17, 2019, 1:43 AM Karthik Bhargavan <
karthikeyan.bhargavan@inria.fr> wrote:

> Hi Joel,
>
> This looks very interesting. It is new to me since I was not at the
> interim.
> After reading the paper and the slides, I am still a bit fuzzy about what
> the recipient of an update needs to do.
>
> For example, for the running example in your slide deck, it would help if
> I could see:
> - what secret keys does each leaf need to keep
> - how do these secrets change when an update from some other node is
> received.
> Just working this out for one update is enough.
>
> I know that this is made precise in the eprint, but it would be faster if
> you could help us understand it :)
>
> Best,
> Karthik
>
> > On 16 Oct 2019, at 23:51, Joel Alwen <jalwen@wickr.com> wrote:
> >
> > <FS-TreeKEM.pdf>
>
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls
>