Re: [MLS] TreeKEM: An alternative to ART

Peter Saint-Andre <stpeter@mozilla.com> Wed, 30 May 2018 16:30 UTC

Return-Path: <stpeter@mozilla.com>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id A66F312E8E4 for <mls@ietfa.amsl.com>; Wed, 30 May 2018 09:30:53 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.001
X-Spam-Level:
X-Spam-Status: No, score=-2.001 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=mozilla.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 2m1yTGLU4ewN for <mls@ietfa.amsl.com>; Wed, 30 May 2018 09:30:49 -0700 (PDT)
Received: from mail-io0-x244.google.com (mail-io0-x244.google.com [IPv6:2607:f8b0:4001:c06::244]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 4BA3F12E8DE for <mls@ietf.org>; Wed, 30 May 2018 09:30:49 -0700 (PDT)
Received: by mail-io0-x244.google.com with SMTP id o185-v6so22366292iod.0 for <mls@ietf.org>; Wed, 30 May 2018 09:30:49 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=mozilla.com; s=google; h=subject:to:cc:references:from:openpgp:autocrypt:message-id:date :user-agent:mime-version:in-reply-to; bh=GdslYENRsJz64Wu/TrqQviUYQzX2Jz7eoZ9WJER2xto=; b=OJYSGnMMEHEhrjruhvu2m9V4Oi+ddSYXvDP9LCvROSDVn1HccrKlWyquGJ0utQNGpw wGY/L4GLpo11FEdTuliOQtJpWLJGmMpvFd261Kc0uQgzckkxQfhcZx5O2rNfsM0uwTmf mWbo9P/quLeo+HDWJdFS5Ddg1Y8Pharh9rHcU=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:openpgp:autocrypt :message-id:date:user-agent:mime-version:in-reply-to; bh=GdslYENRsJz64Wu/TrqQviUYQzX2Jz7eoZ9WJER2xto=; b=Ws9aM6BJ946UM37kZW7J/dxaC7OyIvkwJQHnXZlJvBI64pN7KpWWxwJ0vJbVgkVgsK ZsgvnArCQmuFNBqma9TitWEvl8yVEsy9C9E+zyOOxQRCoVgRKFQJhxp2oThuhc974vQJ HnZpdsVhgC9zXEYsk9Sk6a01+pThKL3brioYmq37Of+afLGg/w0Fk/AiowF2jZp0Z2VJ wcmacznFFSqTU8NoLSzK9VU5ybc9Uklx55/GIRyBWqO4iBrTKhOXbXmc9tg2ppGhj/wr 45hclZM0BPcG5sJ/hXpmVFqwIvRXFxSHGGDsrBj0s02VEAfpGs6qhBug8Y6Ukpkro0Me HAbw==
X-Gm-Message-State: ALKqPweEJ8glXwrOwNOFJvxb/G+AR7LEc6HHiOrrscDUws9GPeZden2t HHVlyPSc4GanCe5Hrv05xY5kgjHM4+M=
X-Google-Smtp-Source: ADUXVKLop4YitoDoRKnMaw/++T8tebjt5x6xX+u2Ap6bFPY4S1KysSwQKdfgEMeRWAgO8YysuBpqAQ==
X-Received: by 2002:a6b:284b:: with SMTP id o72-v6mr2906366ioo.168.1527697848492; Wed, 30 May 2018 09:30:48 -0700 (PDT)
Received: from dragon.local ([76.25.3.152]) by smtp.gmail.com with ESMTPSA id u83-v6sm8736437itf.44.2018.05.30.09.30.47 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 30 May 2018 09:30:47 -0700 (PDT)
To: Richard Barnes <rlb@ipv.sx>
Cc: mls@ietf.org, Nick Sullivan <nick@cloudflare.com>, Sean Turner <sean@sn3rd.com>
References: <CABcZeBOGJTYTGqYLhqafM=yE9hCZP06KbjKfBqMVTr=yoUYUrw@mail.gmail.com> <CABcZeBOTTe=8mw3q7FXNLWD7pe=XTuKj3P3C1=-GXHZSFQybzw@mail.gmail.com> <CAL02cgRn6wHMDoCL+UCaHtD8GV30=+aSrvCY+Jf64tKtqkfV2Q@mail.gmail.com> <70623E37-4A6D-4B73-A97B-DF754D9DBBCE@vigilsec.com> <CAL02cgQwv4owGnoUHwY2s9fdiQNnusD3KGYP-yDru1XjLeYKPQ@mail.gmail.com> <CAL02cgRsUFvVr-a8FiUXb3YRff81rVUgQv5V8RYiBMjUDkswxA@mail.gmail.com> <29aeba9b-2b9d-76b9-72fd-20112d4e39b5@mozilla.com> <CAL02cgTip-cs=nhqdJ5vUMYLwAKGPfidwAedDuZJf95Bfqf=EQ@mail.gmail.com>
From: Peter Saint-Andre <stpeter@mozilla.com>
Openpgp: preference=signencrypt
Autocrypt: addr=stpeter@mozilla.com; prefer-encrypt=mutual; keydata= xsFNBFonEf4BEADvZ+RGsJoOyZaw2rKedB9pBb2nNXVGgymNS9+FAL/9SsfcrKaGYSiWEz7P Lvc97hWH3LACFAHvnzoktv+4IWHjItvhdi9kUQ3Gcbahe55OcdZuSXXH3w5cHF0rKz9aYRpN jENqXM5dA8x4zIymJraqYvHlFsuuPB8rcRIV9SKsvcy14w9iRqu770NjXfE/aIsyRwwmTPiU FQ0fOSDPA/x2DLjed/GYHem90C5vF4Er9InMqH5KAMLnjIYZ9DbPx5c5EME4zW/d648HOvPB bm+roZs4JTHBhjlrTtzDDpMcxHq1e8YPvSdDLPvgFXDcTD4+ztkdO5rvDkbc61QFcLlidU8H 3KBiOVMA/5Rgl4lcWZzGfJBnwvSrKVPsxzpuCYDg01Y/7TH4AuVkv5Na6jKymJegjxEuJUNw CBzAhxOb0H9dXROkvxnRdYS9f0slcNDBrq/9h9dIBOqLhoIvhu+Bhz6L/NP5VunQWsEleGaO 3gxGh9PP/LMyjweDjPz74+7pbyOW0b5VnIDFcvCTJKP0sBJjRU/uqmQ25ckozuYrml0kqVGp EfxhSKVqCFoAS4Q7ux99yT4re2X1kmlHh3xntzmOaRpcZsS8mJEnVyhJZBMOhqE280m80ZbS CYghd2K0EIuRbexd+lfdjZ+t8ROMMdW5L51CJVigF0anyYTcAwARAQABzSdQZXRlciBTYWlu dC1BbmRyZSA8c3RwZXRlckBtb3ppbGxhLmNvbT7CwZQEEwEIAD4WIQQ1VSPTuPTvyWCdvvRl YYwYf2gUqQUCWicR/gIbIwUJCWYBgAULCQgHAgYVCAkKCwIEFgIDAQIeAQIXgAAKCRBlYYwY f2gUqdaREAChG8qU1853mP0sv2Mersns8TLG1ztgoKHvMXFlMUpNz6Oi6CjjaMNFhP7eUY4T D43+yQs7f4qCkOAPWuuqO8FbNWQ+yUoVkqF8NUrrVkZUlZ1VZBMQHNlaEwwu1CGoHsLoRohP SiZ0hpmGTWB3V6cDDK4KN6nl610WJbzE9LeKY1AxtePdJi2KM281U0Fz8ntij1jWu0gF2xU4 Sez46JDogHLWKgd0srauhcCVzZjAhiWrXp1+ryzSWYaZO8Kh8SnF1f4o6jtYikMqkxUaI5nX wvD3kNX4AMSkCAZfG7Jcfj/SLDojTcREgO87g7B9bcOOsHN4lj3lHoFV0aXpgPmjfIvAjJHu fHkXZAQAH8w0u9bgJqRn703+A4NPfLopnjegyhlNi7fQ3cMQV1H7Oj7WrB/pCcprx+1u/6Uq oTtDwWh1U5uVthVAI0QojpNWR08zABDX19TlGtVoeygaQV3CAEolxTiYQtCfVavUzUplCZ/t 3v4YiRov+NylflJd+1akyOs1IAgARf444BnoH1fotkpfXNOpp9wUXXwsQcFRdP7vpMkSCkc0 sxPNTVX3ei0QImp4NsrFdaep7LV3zEb3wkAp6KE5Qno4hVVEypULbvB0G6twNZbeRfcs2Rjp jnPb2fofvg2WhAKB20dnRfIfK8OKTD/P+JDcauJANjmekM7BTQRaJxH+ARAApPwkbOTChAQu jMvteb/xcwuL5JZElmLxIqvJhqybV7JknM+3ATyN0CTYQFvPTgIrhpk4zSn0A6pEePdK8mKK 5/aHyd7pr7rLEi1sI/X3UE8ld/E83MExksKrYbs0UX1wSQwYXU6g64KicnuP2Abqg+8wrQ18 1nPcZci9jJI75XVPnTdUpZD5aaQWGp7IJ06NTbiOk30I50ORfulgKoe4m3UfsMALFxIx3pJk oy76xC2tjxYGf+4Uq1M0iK3Wy655GrcwXq/5ieODNUcAZzvK5hsUVRodBq0Lq3g1ivQF4ba7 RQayDzlW6XgoeU49xnCr9XdZYnTnj4iaPmr2NtY6AacBwRz+bJsyugeSyGgHsnVGyUSMk8YN wZHvUykMjH21LLzIUX5NFlcumLUXDOECELCJwewui4W81sI5Sq/WDJet+iJwwylUX22TSulG VwDS+j66TLZpk1hEwPanGLwFBSosafqSNBMDVWegKWvZZVyoNHIaaQbrTIoAwuAGvdVncSQz ttC6KkaFlAtlZt3+eUFWlMUOQ9jxQKTWymyliWKrx+S6O1cr4hwVRbg7RQkpfA8E2Loa13oO vRSQy/M2YBRZzRecTKY6nslJo6FWTftpGO7cNcvbmQ6I++5cBG1B1eNy2RFGJUzGh1vlYo51 pdfSg0U1oPHBPCHNvPYCJ7UAEQEAAcLBfAQYAQgAJhYhBDVVI9O49O/JYJ2+9GVhjBh/aBSp BQJaJxH+AhsMBQkJZgGAAAoJEGVhjBh/aBSpAw0P/1tEcEaZUO1uLenNtqysi3mQ6qAHYALR Df3p2z/RBKRVx0DJlzDfDvJ2R/GRwoo+vyCviecuG2RNKmJbf1vSm/QTtbQMUjwut9mx6KCY CyKwniqdhaMBmjCfV2DB2MxxZLYMtDfx/2mY7vzAci7AkjC+RkSUByMEOkyscUydKC/ETdf9 tvI8GhTY/8Q7JSylS3lQA5pMUHiIf+KpSmqKZeBPkGc7nSKM1w1UKUvFAsyyVsiG6A/hWrTr 7tTQAl7YfjtOGE8n4IKGktvrT99bbh9wdWKZ5FdHUN9hx2Q8VP8+0lR1CH2laVFbEwCOv1vM W4cgQDLxwwpo1iOTdHBVtQDxlQ9hPMKVlB1KP9KjchxuiLc24wLmCjP3pDMml4LQxOYB34Eq cgPZ3uHvJZG309sb2wTMTWaXobWNI++ZrsRD5GTmuzF3kkx3krtrq6HI5NSaemxK6MTDTjDN Rj/OwTl0yU35eJXuuryB20GFOSUsxiw00I2hMGQ1Cy9L/+IW6Dvotd8O3LmKh2tFArzXaKLx /rZyGNurS/Go5YjHp8wdJOs7Ka2p1U31js24PMWO6hf6hIiY2WRUsnE6xZNhvBTgKOY6u0KT V6hTevFqEw7OAZDCWUoE2Ob2/oHGZCCMW5SLAMgp7eihF0kGf2S2CmpIFYXGb61hAD8SqSY7 Fn7V
Message-ID: <9e84956f-df55-ce70-3a8f-d601170c86fe@mozilla.com>
Date: Wed, 30 May 2018 10:30:46 -0600
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.13; rv:52.0) Gecko/20100101 Thunderbird/52.8.0
MIME-Version: 1.0
In-Reply-To: <CAL02cgTip-cs=nhqdJ5vUMYLwAKGPfidwAedDuZJf95Bfqf=EQ@mail.gmail.com>
Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="JYlTUzWYZPsT7zZPC0Rs2tpUnAUlMLe8O"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/6mLJwnjTsc_FMXbkYi76sjV49C0>
Subject: Re: [MLS] TreeKEM: An alternative to ART
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Messaging Layer Security <mls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/mls>, <mailto:mls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/mls/>
List-Post: <mailto:mls@ietf.org>
List-Help: <mailto:mls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/mls>, <mailto:mls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 30 May 2018 16:30:54 -0000

WFM. :-)

On 5/30/18 10:26 AM, Richard Barnes wrote:
> I'll claim that this isn't an official WG meeting, just a tutorial on
> the side.  We're not going to make any decisions anyway.
> 
> --Richard
> 
> On Wed, May 30, 2018 at 10:45 AM Peter Saint-Andre <stpeter@mozilla.com
> <mailto:stpeter@mozilla.com>> wrote:
> 
>     Yet this is no longer true...
> 
>       > Fortunately, we're not a WG yet, so we're not bound by the rules for
>       > virtual interims :)
> 
>     The tutorial would be beneficial, though!
> 
>     Peter
> 
>     On 5/30/18 7:43 AM, Richard Barnes wrote:
>     > Sorry, I dropped the ball on this, and now we're in the midst of these
>     > dates.  Based on the responses, I propose we do tomorrow at 11:00
>     ET ==
>     > 15:00 UTC.
>     >
>     >
>     https://www.timeanddate.com/worldclock/fixedtime.html?msg=TreeKEM+overview+%2F+discussion&iso=20180531T11&p1=263&ah=1
>     >
>     > The below Webex details should work:
>     >
>     > Join from a video conferencing system or application
>     > Dial https://cisco.webex.com/meet/richbarn
>     > Join by Phone
>     > Toll free: +1-866-432-9903 Toll: +1-408-525-6800 Access code:
>     201006237
>     >
>     >
>     >
>     > On Thu, May 10, 2018 at 3:05 PM Richard Barnes <rlb@ipv.sx> wrote:
>     >
>     >     Fortunately, we're not a WG yet, so we're not bound by the
>     rules for
>     >     virtual interims :)  Here's a Doodle to see if there's a time that
>     >     looks good to folks:
>     >
>     >     https://doodle.com/poll/u84kpg2i4vfvnmsz
>     >
>     >     On Thu, May 10, 2018 at 2:01 PM Russ Housley
>     <housley@vigilsec..com
>     >     <mailto:housley@vigilsec.com <mailto:housley@vigilsec.com>>>
>     wrote:
>     >
>     >         I think that a virtual interim to go through a tutorial of
>     >         TreeKEM would be very useful.
>     >
>     >         Russ
>     >
>     >
>     >>         On May 3, 2018, at 10:36 AM, Richard Barnes <rlb@ipv.sx
>     >>         <mailto:rlb@ipv.sx <mailto:rlb@ipv.sx>>> wrote:
>     >>
>     >>         Just for context: Note that TreeKEM, like ART, is an "inner
>     >>         loop" / "subroutine" for MLS.  It handles the
>     establishment of
>     >>         a key that's confidential to the group members.  There's
>     still
>     >>         a need for more mechanism to provide authentication.
>     >>
>     >>         Speaking of protocol, in protocol terms, TreeKEM, while we
>     >>         haven't elaborated a precise protocol, if you look at the
>     very
>     >>         basic sketch that's in the repo EKR linked, the protocol
>     looks
>     >>         very similar to what we have for ART now.  Basically, where
>     >>         ART sends public keys, TreeKEM needs to send (public key, PKE
>     >>         ciphertext) pairs.  So there's a bit of additional
>     >>         communications overhead, but not a dramatic reworking of the
>     >>         messages.
>     >>
>     >>         Having spent some time with this approach, I appreciate that
>     >>         it can be kind of hard to digest; it has a few more moving
>     >>         parts than ART.  I would be happy to set up a call
>     sometime if
>     >>         people wanted to talk this through.
>     >>
>     >>         --Richard
>     >>
>     >>         On Thu, May 3, 2018 at 10:33 AM Eric Rescorla
>     <ekr@rtfm.com <mailto:ekr@rtfm.com>
>     >>         <mailto:ekr@rtfm.com <mailto:ekr@rtfm.com>>> wrote:
>     >>
>     >>             Oops. I forgot to attach the paper.
>     >>
>     >>
>     >>             On Thu, May 3, 2018 at 7:26 AM, Eric Rescorla
>     >>             <ekr@rtfm.com <mailto:ekr@rtfm.com>
>     <mailto:ekr@rtfm.com <mailto:ekr@rtfm.com>>> wrote:
>     >>
>     >>                 Hi folks,
>     >>
>     >>                 Several of us (Karthik, Richard, and I) have been
>     >>                 working on an
>     >>                 alternative to ART which we call TreeKEM. TreeKEM
>     >>                 parallels ART in
>     >>                 many ways, but is more cryptographically
>     efficient and
>     >>                 is much better
>     >>                 at handling concurrent changes. The most common
>     >>                 behaviors (updating
>     >>                 ones own key) can be executed completely
>     concurrently,
>     >>                 merging all the
>     >>                 requested changes.
>     >>
>     >>                 We've attached a draft technical paper describing the
>     >>                 details, and
>     >>                 some slides, but here's a brief overview of TreeKEM.
>     >>
>     >>                 Code: https://github.com/bifurcation/treekem,
>     >>                 https://github.com/bifurcation/treekem
>     >>                 Explainer slides:
>     >>               
>      https://docs.google.com/presentation/d/1myiQ22ddxHAcF8uCJBXk9cdJMvAQfAw9nmKiqE5seJc/edit?usp=sharing
>     >>
>     >>                 As with ART, TreeKEM addresses the scaling problem by
>     >>                 arranging nodes
>     >>                 in a binary tree. In the steady state, each node
>     i has
>     >>                 a key pair but
>     >>                 instead of having two siblings do DH to determine
>     >>                 their shared key, we
>     >>                 derive the shared key by hashing the key of the last
>     >>                 node to update.
>     >>                 As before, each node knows all the keys to its
>     parents.
>     >>
>     >>                 Imagine we have the four node tree a, b, c, d which
>     >>                 was constructed
>     >>                 in that order. The private keys at each vertex are
>     >>                 shown below.
>     >>
>     >>                        H^2(d)
>     >>                       /     \
>     >>                     H(b)    H(d)
>     >>                     / \     / \
>     >>                    a   b   c   d
>     >>
>     >>
>     >>                 UPDATES
>     >>                 Now say that b wants to update its key to b', giving
>     >>                 us the tree:
>     >>
>     >>                        H^2(b')
>     >>                       /     \
>     >>                     H(b')   H(d)
>     >>                     / \     / \
>     >>                    a   b'  c   d
>     >>
>     >>                 This requires providing
>     >>
>     >>                   - a with H(b') -- note that a can compute H^2(b')
>     >>                 for itself.
>     >>                   - c and d with H^2(b')
>     >>
>     >>                 Recall that you can encrypt to any subset of the tree
>     >>                 by just
>     >>                 encrypting to the appropriate set of parent
>     nodes. So,
>     >>                 we can
>     >>                 do this by sending:
>     >>
>     >>                   - E(pubkey(a), H(b'))
>     >>                   - E(pubkey(H^2(d)), H^2(b'))
>     >>
>     >>                 Where pubkey(k) gives the public key derived from
>     >>                 private key k.
>     >>
>     >>                 As with ART, you then mix the new tree root (H^2(b'))
>     >>                 into the current
>     >>                 operational keys and use the result to derive the
>     >>                 actual working keys.
>     >>
>     >>
>     >>                 CONCURRENT UPDATES
>     >>                 The big win in TreeKEM is that you can handle an
>     >>                 arbitrary number
>     >>                 of concurrent updates, just by applying them in
>     order.
>     >>                 Again,
>     >>                 consider our starting tree, but assume that b and c
>     >>                 both try to
>     >>                 update at once. a thus receives two updates
>     >>
>     >>                   - E(pubkey(a), H(b'))       [b's update]
>     >>                   - E(pubkey(H(b)), H^2(c'))  [c's update]
>     >>
>     >>                 If we apply these in order b, c we get the tree:
>     >>
>     >>                        H^2(c')
>     >>                       /     \
>     >>                     H(b')   H(c')
>     >>                     / \     / \
>     >>                    a   b'  c   d
>     >>
>     >>                 a can easily compute this.
>     >>
>     >>                 In order to make this work, we need two things:
>     >>
>     >>                 1. a needs to keep a copy of its current tree around
>     >>                 until it has
>     >>                    received all updates based on that tree
>     >>                 2. there needs to be an unambiguous ordering of
>     updates
>     >>
>     >>                 The way to handle (1) is probably to have some
>     defined
>     >>                 "window"
>     >>                 of time during which an update can be received. The
>     >>                 node needs
>     >>                 to hold onto its old key until that window has
>     passed.
>     >>                 (2) can
>     >>                 be handled by having the messaging system provide a
>     >>                 consistent
>     >>                 order and then agreeing to apply updates
>     >>                 consecutively. If we
>     >>                 want to concurrently apply other changes, we may need
>     >>                 to sort
>     >>                 based on change type within the window.
>     >>
>     >>
>     >>                 ADDS
>     >>                 In order to add itself to the group (USERADD), a node
>     >>                 merely puts
>     >>                 itself at the right position in the tree and,
>     >>                 generates a random key,
>     >>                 and then sends the appropriate keying material to
>     >>                 everyone in its path
>     >>                 to the root.
>     >>
>     >>                 In order to add another node to the group (GROUPADD),
>     >>                 the adding
>     >>                 node does exactly the same thing as with a USERADD,
>     >>                 but also sends
>     >>                 a copy of the new key to the node being added.. Note
>     >>                 that this creates
>     >>                 a double-join, which we will cover later.
>     >>
>     >>
>     >>                 REMOVAL
>     >>                 In order to remove another node from the tree, the
>     >>                 removing node
>     >>                 sends the same message that the evicted node would
>     >>                 have sent if
>     >>                 it had sent an update, but with a new key not
>     known to
>     >>                 the evicted
>     >>                 node (note that this naturally omits the evicted
>     node,
>     >>                 because you
>     >>                 encrypt to the co-path). This also creates a
>     >>                 double-join, where the
>     >>                 removing node knows the dummy key.
>     >>
>     >>
>     >>
>     >>                 STATE
>     >>                 In order to receive messages, a node need only keep
>     >>                 its secret keys,
>     >>                 which range between 1 key (if it was the last to
>     >>                 update) and log(N)
>     >>                 keys (in the worst case).
>     >>
>     >>                 In the best case, in order to update, a node needs to
>     >>                 also know
>     >>                 the public keys for everyone on its co-path. However.
>     >>
>     >>                 In order to be able to do deletes, a node also needs
>     >>                 to be able
>     >>                 to get the public key for any node in the tree (leaf
>     >>                 or internal).
>     >>                 It's easy to see this by realizing that to delete a
>     >>                 node you need
>     >>                 to encrypt a new key to its sibling, and so to delete
>     >>                 any node,
>     >>                 you need to be able to access every node's public
>     key.
>     >>                 However,
>     >>                 a node need not store this information, but can
>     >>                 retrieve it
>     >>                 on demand when it needs to delete another node.
>     >>
>     >>
>     >>                 EFFICIENCY
>     >>                 The paper contains more details. but generally
>     TreeKEM
>     >>                 is somewhat
>     >>                 more efficient in terms of asymmetric crypto
>     >>                 operations than ART.
>     >>
>     >>
>     >>                 DOUBLE JOINS
>     >>                 Like ART, TreeKEM has double-join problems whenever
>     >>                 one group member
>     >>                 provides a service (or a disservice, in the case of
>     >>                 remove) for another
>     >>                 group member. In the case of GROUPADD, the double
>     join
>     >>                 will resolve itself
>     >>                 as soon as the added node updates its key. However in
>     >>                 the case of
>     >>                 REMOVE, this cannot happen, and so double join
>     needs to be
>     >>                 dealt with in some other way.
>     >>
>     >>                 One option is to have selective updates: each node
>     >>                 keeps track of
>     >>                 extra tree state and uses it to control its updates.
>     >>                 For instance,
>     >>                 if we never send updates to deleted nodes, than as
>     >>                 soon as a deleted
>     >>                 node's sibling sends an update, the double-join will
>     >>                 be resolved.
>     >>                 In a more sophisticated -- but also more expensive to
>     >>                 implement --
>     >>                 version, we track which nodes control the keys of
>     >>                 other nodes and
>     >>                 REMOVE all affected nodes when we do a delete.
>     >>
>     >>                 -Ekr
>     >>
>     >>
>     >>         _______________________________________________
>     >>         MLS mailing list
>     >>         MLS@ietf.org <mailto:MLS@ietf.org> <mailto:MLS@ietf.org
>     <mailto:MLS@ietf.org>>
>     >>         https://www.ietf.org/mailman/listinfo/mls
>     >
>     >         _______________________________________________
>     >         MLS mailing list
>     >         MLS@ietf.org <mailto:MLS@ietf.org> <mailto:MLS@ietf.org
>     <mailto:MLS@ietf.org>>
>     >         https://www.ietf.org/mailman/listinfo/mls
>     >
>     >
>     >
>     > _______________________________________________
>     > MLS mailing list
>     > MLS@ietf.org <mailto:MLS@ietf.org>
>     > https://www.ietf.org/mailman/listinfo/mls
>     >
> 
>     _______________________________________________
>     MLS mailing list
>     MLS@ietf.org <mailto:MLS@ietf.org>
>     https://www.ietf.org/mailman/listinfo/mls
>