Re: [MLS] UPKE for X25519/X448

[Yevgeniy Dodis <[e-mail]>]

Thank you Benjamin.

We hope there will be no more surprises, like the lack of additive
homomorphism for the X-curves. So we would certainly love to get
guidance from other people on the list, in case we missed something else.

There is definitely some cost involved, but we hope it is small, and we
believe using UPKE in place of PKE gives a substantial security
enhancement to justify the (small) cost.

We could also follow Karthik's nice suggestion to compare our scheme with
"naive" UPKE, where for each updated tree node one prepares K (say, 100)
public-secret key pairs, and erases them one-by-one as they get used on
various co-paths. If one runs out of fresh pairs, the last key pair is not
erased, and gets used until the update happens. Ironically, K=1 corresponds
to the current scheme, so in this sense the naive scheme -- call it
K-TreeKEM -- is a natural generalization of TreeKEM. However, we believe
already for small K (like 3 or 4), K-TreeKEM will start becoming less
efficient overall than RTreeKEM, while still offering inferior security.
But this is a good thing to test if people are interested.

Thank you in advance for your comments,
Yevgeniy

On Mon, Oct 21, 2019 at 5:57 PM Benjamin Beurdouche <
[e-mail]> wrote:

> That look excellent !
> If that works as expected, that would indeed be very nice… : )
>
> B.
>
> > On Oct 21, 2019, at 11:20 PM, Joel Alwen <[e-mail]> wrote:
> >
> > Hey,
> >
> > This is a follow up to the earlier Re-Randomized TreeKEM email. (Its a
> > separate thread as it changes whats in that first email and I didn't
> > want it getting lost in the other thread when people evaluate whether to
> > adopt RTreeKEM for MLS.)
> >
> > In short, after some very helpful back and forth with Mike Hamburg, it
> > is looking like we have a reasonable way to do Re-randomizable TreeKEM
> > (RTreeKEM) based on the X25519/X448 ciphersuits. That would mean we no
> > longer have to choose between RTreeKEM and those suits. IMO that removes
> > the biggest barrier to using RTreeKEM.
> >
> > To be clear, we're still doing a some coding & testing to build
> > confidence. And we will also run it past the CFRG / a few more ECC
> > experts besides Mike, to make absolutely sure it works as intended.
> > But at this point we are pretty optimistic already.
> >
> > The rest of this email contains the details for how RTreeKEM can be made
> > to work with the X* groups.
> >
> > - Joël
> >
> > -----------------------------------------------------------
> >
> >
> > Essentially, all we really need for RTreeKEM is to build "Updateable
> > Public Key Encryption" (UPKE) as defined in [1].
> >
> > Rather than the construction in [1] which is based additive
> > key-homomorphism we can use the following construction based on a
> > multiplicative key-homomorphism. (It turns out the later is easier to
> > implement for X* groups than the former.)
> >
> > To minimize the diff between current TreeKEM and this new variant of
> > RTreeKEM, the new construction is formulated it to use HPKE and HKDF as
> > black boxes.
> >
> > Inherited from Cipher Suite
> > ---------------------------
> > - sksize = # of bits for secret key scalars. (e.g. 32 for X25518)
> > - order = order of prime-order subgroup (e.g. as in RFC 7748)
> > - DH(A,b) : A Diffie-Hellman function. (E.g. X25519 or X448)
> > - Mult(a,b) : Multiplication of secret keys. See below.
> >
> >
> > Multiplication
> > --------------
> > - NIST curves : Mult(a,b) = a*b mod order.
> > - X25519 : let Clamp(k) = decodeScalar25519(k) as in RFC 7748.
> > - X448 : let Clamp(k) = decodeScalar448(k) as in RFC 7748.
> >
> > For both X25519 & X448 use
> > Mult(a,b) {
> >   c = (Clamp(a) - Clamp(b)) mod order
> >   if msb(c) = 0
> >     c = (order - c) mod order
> >   return c
> > }
> >
> >
> > UPKE Construction (from HPKE & HKDF)
> > ------------------------------------
> > - UPKE-KeyGen = HPKE-KeyGen
> >
> > - UPKE-Encrypt(pk, m):
> >  d'  <-- {0,1}^secpar
> >  d   := HKDF(sksize, d', "", "derive UPKE delta")
> >  c1, context := HPKE.SetupBaseI(pk, "")
> >  c2  <-- context.Seal("", d' || m)
> >  pk' := DH(pk, d)
> >  return ((c1, c2), pk')
> >
> > - UPKE-Decrypt(sk, (c1, c2)):
> >  epk, context := HPKE.SetupBaseR(c1, sk, "")
> >  d' || m := context.Open("", c2)
> >  d := HKDF(sksize, d', "", "derive UPKE delta")
> >  sk' := Mult(sk, d)
> >  return (m, sk')
> >
> >
> > References
> > ----------
> > [1] http:\\ia.cr\2019\1189.
> >
> > _______________________________________________
> > MLS mailing list
> > [e-mail]
> > https://www.ietf.org/mailman/listinfo/mls
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>