Re: [MLS] UPKE for X25519/X448

[Benjamin Beurdouche <[e-mail]>]

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