Re: [MLS] Re-randomized TreeKEM

Yevgeniy Dodis <> Thu, 17 October 2019 11:47 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id DE7BF120271 for <>; Thu, 17 Oct 2019 04:47:20 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Status: No, score=-1.997 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 71i9evJfpDCe for <>; Thu, 17 Oct 2019 04:47:18 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::12b]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 1D48A1200C5 for <>; Thu, 17 Oct 2019 04:47:18 -0700 (PDT)
Received: by with SMTP id f13so1686427ils.11 for <>; Thu, 17 Oct 2019 04:47:18 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=WuQjGzqUHroahUNV021g+6Mg7m8RxsTNIdZZ07NidQI=; b=JOLLy7XUzr/lueS4dYJsiaRo+u9s4SUb8/APHmGR61kU7yDzdU7gtgTY2OesVWGhUM nyUYEVnC8YP1UqIL0+7tchlSX0ne59RkwezWjhlxwbuL7QVnU1t/HyOggf2JC+ljjVfa pLKYZs9nYX/fB9xcUbKYsfrlVPB074UAXdTbkgvvC969L/WD47NkcxLuQCIYfXohK8Ah uYtJOgo+xbshJSZJJ6p2pMNtSG/x8gSSahGpnfpBoNG51gkL2vGyDzS3ywx/CeLMJeV9 xMCDlA1r+HE442DFuBxAaJpErL58jSmlf/4QtGt/B/4+XK+SnmQKaXmlgGeX1V5NXwYj pf1g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=WuQjGzqUHroahUNV021g+6Mg7m8RxsTNIdZZ07NidQI=; b=NVM+U73w4AXjs+fnMrXBy+7TaMVNOkxZUbvBsMWxNyMDTBJxJEYphOkdeh5eMNeheQ cLehs4NoO2xwlmgOAeBm9cxMkZIg+QjhETq3cEAFL4mSG+7t7CJCsvwbe3pbmTanIiiE LzKAA7mamuG3a2t7ADVio9cPvF0+uPcvYc+BtiA9Idp7nnGA5Pb8KQKbkbJyGi3cCKqF f3avHacu7GfhK7F92rm3RP4RvdHQFwo+tV3X2CKRIczNKTTyCSzUj0Vi+tSqnVK1BdP+ f4mR7VM6yfN5lGIOS27qStqXMLSXDSsTACPFLR6hFxX1ieJ+p0FfXNDwYF0T8LpD1qm7 jb4w==
X-Gm-Message-State: APjAAAWPDs3hint6odo9nbUsx1zxcXZ8si2Ekr03tmTF14oZw9QzSQNT hl7lp8VWCZtEx7wRWzd8zBjxW5ZKs2m4r9ZaD/I=
X-Google-Smtp-Source: APXvYqxTCM7p8pz6biKRKOL6fXwosIgf+1MgW0hM+keBSARyAn93YUU/VRA8Qtdtr2xRxhEYOTy/hLYVbDDd/kZgvvM=
X-Received: by 2002:a92:8941:: with SMTP id n62mr3073079ild.20.1571312836938; Thu, 17 Oct 2019 04:47:16 -0700 (PDT)
MIME-Version: 1.0
References: <> <>
In-Reply-To: <>
From: Yevgeniy Dodis <>
Date: Thu, 17 Oct 2019 07:47:05 -0400
Message-ID: <>
To: Karthik Bhargavan <>
Content-Type: multipart/alternative; boundary="0000000000007a1254059519c7c8"
Archived-At: <>
Subject: Re: [MLS] Re-randomized TreeKEM
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Thu, 17 Oct 2019 11:47:21 -0000

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,

On Thu, Oct 17, 2019, 1:43 AM Karthik Bhargavan <> 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 <> wrote:
> >
> > <FS-TreeKEM.pdf>
> _______________________________________________
> MLS mailing list