[MLS] Adapting Hierarchical Key Derivation for Ephemeral Signatures in MLS

[Nadim Kobeissi <[e-mail]>]

Hello everyone,

I've been working on adapting Hierarchical Key Derivation (HKD) in order to
obtain some kind of ephemeral signatures that may be useful in MLS. I've
arrived at a point where I'm optimistic that this is a direction worth
pursuing and might indeed be a solution to this problem.

HKD was at some point a candidate for how signature keys are managed per
epoch in the Tor Hidden Service design [0]. HKD logic has also been
implemented in Bitcoin wallets for a while now [1]. HKD constructions can
be also derived from existing popular fast signature algorithms such as
Ed25519 with minimal changes [2], making them an easy fit for MLS. Very
simply, the functionality that HKD signature schemes bring to MLS is the
following:

   - Alice sends a public signing key to Bob during epoch n.
   - At the onset of epoch n+1, Bob is able to immediately calculate
   Alice's public signing key for epoch n+1 based purely on his knowledge of
   Alice's public signing key for epoch 0. Alice doesn't need to send new
   signing key information to Bob.
   - At this point, Bob can delete Alice's public signing key for epoch n.
   - More importantly, Alice herself can delete Alice's private signing key
   for epoch n, keeping only her private signing key for epoch n+1.

The way that this could work in MLS would be heavily based on
HDKeys-Ed25519 [2]. I'll resist paraphrasing the paper, and instead will
point out the relevant sections (which are short, well-written and worth
reading:)

   - Section 2 describes the original concept as used for Bitcoin wallet
   derivation.
   - Section 4 describes the modifications to Ed25519 to enable HKD
   constructions.
   - Section 5 describes how private and public child keys are generated
   (Fig. 1 is also helpful.)

My questions:

   - How are we deriving epoch identifiers? Are they simply counters, or
   each epoch identified by a nonce that's communicated confidentially? If you
   read [2], you'll see why this can be important.
   - Performance impact seems to be negligible for Montgomery-based signing
   primitives, but I'm interested in more insight on this.
   - Is anyone else interested in having a standard
   HDKeys-Ed25519 implementation? I've been working on one in JavaScript and
   plan to eventually also write one in Go. Perhaps Richard would like to help
   with a C++ version?
   - I'm also interested in hearing your thoughts on this generally.

During the interim meeting (as well as before it), it was frequently
discussed how ephemeral signatures may be useful for MLS. This also appears
to be slated as a discussion topic for IETF 103, so it would be great if we
could continue the discussion there as well.

References:
[0]
https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.txt#n1979
[1] https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki
[2] https://cardanolaunch.com/assets/Ed25519_BIP.pdf

Nadim Kobeissi
Symbolic Software • https://symbolic.software
Sent from office