Re: [MLS] Re-randomized TreeKEM

Joel Alwen <> Thu, 17 October 2019 15:18 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 74C0C1208BA for <>; Thu, 17 Oct 2019 08:18:51 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, 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 qXdes44hFqN8 for <>; Thu, 17 Oct 2019 08:18:47 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::42c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 4F9891208E9 for <>; Thu, 17 Oct 2019 08:18:43 -0700 (PDT)
Received: by with SMTP id j11so2838071wrp.1 for <>; Thu, 17 Oct 2019 08:18:43 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=subject:to:references:from:openpgp:autocrypt:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=0vPDHW8Ulsz/tw9wzWoHXCBN4NIwIBa3WM0pTTnapQY=; b=dtC/tJ5m7dXnva/SceEbOt5+4Iilmmj1EBBDzdbu8Ia+EC8uR40MoDDX9F90oGz9pd 7JiOMgk1UiIHrTdMKQnuSE8le3c8GuwpzP1/iXLuhLRBgnw3NRbRzq1I95PGDYYIxOJ+ sqYgW/lqnlkIGxR5LpwOaC9kNzt3Sc3e7mZTUg4lojfvi1kB72VqqYJECH1WOnm89sZ7 0szcGQ0bRbkYdBjDp9Vfc4ebsQxV7TY+azBoYZgOfCWLj9JY/RVEIOQWYglh0L/v1hlC q2KVfxv2iJ/DRgmHZjGVfQTKI4wLZKu6c2Y4KcjHcxPX8jtzOsJc+ZiPgwXWjbmg6uia xpbg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:subject:to:references:from:openpgp:autocrypt :message-id:date:user-agent:mime-version:in-reply-to :content-language:content-transfer-encoding; bh=0vPDHW8Ulsz/tw9wzWoHXCBN4NIwIBa3WM0pTTnapQY=; b=TJF+hrBVC0e4y8FobRdUOx1weK4Qnei3RI20jhLvgq0gsHOFurJL6mpUZuE3xnBh2p rXo4KGKw+YohfNtID3bjtUFuoVeubrZxp6LMKlbQ8oyi2ZOsiS4slLKGdeO5prjbvBGX ntN5i6Ot8/NkRO7zRKQAKkZQLR4GYBnp76xNPnCmKSIk5KE5N0bRdixasxxWcQ9DDt32 NjEMIY45C46+3jAdANOO2DZ+y2ROTyP74snxS3rPOZcfzu0BSfJCccVCbl/E4vbJTzE8 IXHrldLCnue9xJlsvnU31YUqA3zYp8eLSWA9Ux5RD1dTXyVfvpau/EjpNWFEsKwmFa6P cF0Q==
X-Gm-Message-State: APjAAAVTXehM2nQmYlAmIrHqr07g1HrCB+ew18d9Wmb1Q508b54lJZp4 zUAewZjyK/IhjCpCyeYT/DUyoEayv/8=
X-Google-Smtp-Source: APXvYqxdDUtlazqOrSTnXIxYGMXmUIETog63Gtb2iNfOmyqHMMg9t7vEqELFwfN5N8CPPTMA43O0mw==
X-Received: by 2002:adf:f40a:: with SMTP id g10mr2825301wro.228.1571325521345; Thu, 17 Oct 2019 08:18:41 -0700 (PDT)
Received: from [] ( []) by with ESMTPSA id t11sm2399202wmi.25.2019. for <> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 17 Oct 2019 08:18:40 -0700 (PDT)
References: <> <> <> <>
From: Joel Alwen <>
Openpgp: preference=signencrypt
Autocrypt:; keydata= mQENBFyIZvABCAC65JupY1w7gzhhNo41ftIk09n7Lid9p31jDR8Jefv9R5sWL+HZFGDeABAY 1J1JvV6vOaMsfdy9iUFfGS1GhMJ3+mh799SIsB3JSfPq/eq6Jut57D2yPtILmc7ZbuJyBHg0 xuYfKCQQAYikW+v2LJQU1Y+BUDbVldpzxSc8Z3PPSfunWdzhY6qAAhyCv+Y8EzJlQivMwD5B f6737krf8SoBsjsqCHQrRo/r+BSj5Wtd5/K3FkmWLOUAFoYK23+cpoFntGJKZfss27gDPhyS gX9ibXcBGQqBEF4qDPEzEHK8iQmXTxLul5Y7lQ6ADf69xH15WM4GmRBeCvR3Uanxcr2/ABEB AAG0HUpvZWwgQWx3ZW4gPGphbHdlbkB3aWNrci5jb20+iQFUBBMBCAA+FiEEYFNg9IH2SV6e 03O3FR5tDZv8eygFAlyIZvICGwMFCQHhM4AFCwkIBwIGFQoJCAsCBBYCAwECHgECF4AACgkQ FR5tDZv8eyjSywgApQNIRcL4IKTJ0I4XwcQRhICu1Bht3c2fUnG2YziJXjGf6DZ49uKKtuIu fk8mNS+vKRLoLZ7+u+Pv/Yjmk8jtrr6Saz1vnfsle3GgmXG5JaKOM5cOfeo5JnlNUP3QonR7 LMZwY1qVKg2mzNmwi0jG1zIGgQ5fiAwqe+YTNFli5bc/H1O9LcSmbrLV9OyucARq11DIiAvU fDknZ17OahQls+9mgfAXH5vZjzo296tYvzkOJQ2A6GPxdMHIXGbJM/vjuMe2QJl6C0zaqOtm JvFcx/HpNhmugYI9OsNAd7846HASDp8BKyfY5FYP7bn0/JBuCpg18Aykru6xyFjG3gv0L7kB DQRciGbxAQgA0Qx9LlxvJ0LGZlZRVyV8kPIxg8pNMmxJwJJ+JnTciW0LpfigfdAvGVf6PU0x 3V6SJKtz8D61c8KLyztxwPGRgJX2TRK3zvTlT5mqqnGYMAANttCF1+8DNpiYOMg3ibPRby46 4JPhMgWgvCJ1vHGu9cghjn1ttWIwBuKBXMc8HgACKYWsYZJiYtFEsnOdsD6aPWCg6NiImoc7 vRwNMKNNtDPxY95Yj4CRiLPVrZje3LyJlA9S+y2/p3w69R4AVLSRzAwDlupjXYs03QdNjGjP 2IR2u8RhstDgqW8+Bk3p7wjJ1kHTHgyox81/aHbnIRGKksPGPMPT3bvbpxevfqZ7ywARAQAB iQE8BBgBCAAmFiEEYFNg9IH2SV6e03O3FR5tDZv8eygFAlyIZvECGwwFCQHhM4AACgkQFR5t DZv8eygbLQf+OHSG6K9qiPdYxe61IR2kZdyogc2ArEGrl6AmcNzySXC8wlnreZo3FjfkD6xV CQWwWDxI7B0JPM86IcfCfn45ADeI8rwm6yYIs00B4ag9Mmo0GQ4kQd2aTy60/QaE2ZSrnEtt 0fuz1G8DGnhPnOnMyCnCnkSNuTNG20OlI0cn5EJSxBS4fXVeBMBaV91DEmvLU6DjL+fOBQPq CXIbFY7XffOmC4VxtAGhTadJ8WmUD8ZezXNs8c40Btpukr7j4piUshITfazPGEMXzTUTkimf fAhNX1QQBsfP9kjfjxBn6jDl+lDJY34mANWwEJ8BKjgr09P0sOz4zjjFL62GcFczQA==
Message-ID: <>
Date: Thu, 17 Oct 2019 17:18:40 +0200
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0
MIME-Version: 1.0
In-Reply-To: <>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
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 15:19:01 -0000

I think the challenge with the hash-forward approach is how to do that
homomorphically. I.e. what we need are two algorithms; one to refresh
the PK without knowing the SK (but possibly knowing a secret
rerandomizer delta if needed) and one to update SK (again possibly using
delta). So to use a hash-forward approach their must be:

 1) a way to evolve PK forward to PK' and
 2) a *one-way* method to evolve SK forward to SK' compatible PK'.

One-wayness is what gives us Forward Secrecy and "compatibility" between
the two key evolution methods is what allows for asynchronous (i.e. 1
packet) updates.

Currently we use a secret re-randomizer delta to ensure the SK update
method is one-way. That is, without the delta you cant "undo" the
update. But that would break if we (at least naively) used some public
delta, say hash(ciphertext). So I think this is the challenge that we'd
have to overcome. Basically, make sure we SK evolution is one-way but
also compatible the public evolution of PK.

Now one way sweet way to get all this (and more) would be to use a HIBE.

Initial, PK for a ratchet tree node (i.e. its "identity" since this is a
HIBE now) is simply the empty vector PK := () while the secret key is
the master public key for a fresh HIBE instance SK := MSK. We also
include, as a second component of the nodes PK, the master public key
PK_0 = MPK. To "hash forward" / "re-randomize" when sending a ciphertext
C to that node we can do:

 PK' := (PK, hash(C)).
 SK' := DeriveHIBEKey(PK, SK).

So simply append hash(C) to the identity for that node and derive the
corresponding HIBE key.

Ignoring the problems with using HIBE for a second, this is a very cool
solution. We don't need to send out the updated PK since everyone in the
group (and even the adversary) can compute it for themselves. We also
dont need a re-randomize delta as part of the plaintext because we're
using delta := hash(ciphertext) so the plaintext is shorter again.
Moreover, HIBE security means that learning SK' doesn't tell you
anything interesting about SK. In particular, we have forward security.
(In fact, FS will hold even if hash(C) were chosen *completely*
adversarially, say, as part of a malicious update in an insider attack!)

Of course, the problem with this solution is that we're using HIBE.
Worse, with unbounded depth because each new ciphertext sent to a node
results in going one depth further into the hierarchy. AFAIK all HIBE
constructions have pretty horrible (read exponential) efficiency as a
function of their depth. (And I won't mention the state of
standardization and open implementations for HIBE.)

Now there could be a totally different approach that entirly avoids
HIBE. But even with this approach there's at least some glimer of hope
to improve on it because, if we don't wory about insider attacks we can
assume C is honestly generated which means hash(C) really has a ton of
entropy. So we dont seem to need the full expresivity HIBE identities
allow us. Rather we only need HIBE for "random" identities. Still, that
seems like a pretty slim hope for major efficiency improvement. It also
doesn't do anything to address the lack of implementations and standards.

- Joël

On 17/10/2019 16:37, Karthik Bhargavan wrote:
> Thanks Yevgeniy,
> This helps a lot.
> To further my understanding, another question:
>>  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. 
> I see that in the DH-based scheme, this Delta needs to be private,
> otherwise the adversary can compute sk once it knows sk+Delta.
> But, in general, is it possible to conceive of a UPKE scheme where the
> recipient effectively “hashes forward” its symmetric key,
> where this one way hash-forward function does not have to rely on an
> externally chosen secret value?
> Best,
> Karthik
>> This is the high level, hope it makes sense.
>> Thanks for your question,
>> Yevgeniy
>> 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
>> <>
> _______________________________________________
> MLS mailing list