[Cfrg] Curve25519 lacks private/public homomorphism?

[Richard Barnes <[e-mail]>]

Hi CFRG,

I'm trying to work through whether the MLS working group can use Curve25519
in a particular way, and was wondering if folks here had any insights.

MLS has a case where it would be useful to be able to be able to implement
the following:

- Given a DH key pair whose private key is held by one set of parties and
public key by another
- Have a third party (holding only the public key) be able to generate a
"delta" such that:
  - The holders the private key can use the delta to update the private key
to a new value
  - The holders of the public key can use the delta to compute the
corresponding new public key

That is, we're looking to use a certain homomorphism in the DH group action
that translates a change in private key to a change in public key.  For
example, with traditional ECDH, you could generate a random number that the
private key holders could multiply with the private key, and the public key
holders could just do a DH operation to multiply the public key by the
delta.  (A sketch in Go here [1].)

When you try to do this with Curve25519 (or Curve448), however, you run
into a problem: `k_list[31] |= 64`.  The X25519 function in RFC 7748 [2]
ensures that the second-most-significant bit of a scalar private key is
always set, but this bit is not necessarily set in the product of two such
scalars.  In other words, there are scalars `ab` such that you can arrive
at `abG` as the result of a DH computation, but never abG will never be a
public key (since `X25519(ab, 9) != abG`).  The mapping from private keys
to public keys is not a homomorphism with regard to addition or
multiplication.

This means we're out of luck with regard to our delta scheme.  If the delta
happens to result in a new private key with its penultimate bit unset, then
it can't actually be used as a private key -- and there's no way for the
delta-generating party to know this.

Is this surprising to people?  Is it a consequence of some property of
Curve25519 that is good for security, or is it just collateral damage?
(Why does the penultimate bit need to be set?)  Do folks have other ideas
for a "homomorphic" construction such as the above that would accommodate
this quirk of Curve25519?

Thanks a lot,
--Richard


[1] https://play.golang.org/p/nyiRcJUDT-p
[2] https://tools.ietf.org/html/rfc7748#section-5