Re: [Cfrg] Curve25519 lacks private/public homomorphism?

[Adam Langley <[e-mail]>]

On Mon, Feb 4, 2019 at 2:21 PM Richard Barnes <[e-mail]> wrote:

> 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.
>

Setting the 255th bit is just done to avoid having to worry about infinity
in the Montgomery ladder, I believe. But if you handle infinity explicitly,
doesn't that solve the problem?

(p.s. I'm imagining that an answer would either be a) "no, we thought about
that and it doesn't work because ..." or b) "no idea, what does 'handle
infinity explicitly' mean?". If (b), then I can see about knocking up an
example tomorrow.)


Cheers

AGL

-- 
Adam Langley [e-mail] https://www.imperialviolet.org