[curves] To multiply or to add in HKD schemes?

[Pieter Wuille]

On Fri, Apr 7, 2017 at 3:08 PM, Oleg Andreev <oleganza at gmail.com> wrote:

> Hey there,
>
> HKD stands for Hierarchical Key Derivation, e.g. BIP32 [1] or ChainKD [2].
> Alternatively known as "blinded keys" per Tor's draft [3].
>
> All these schemes generate a scalar to be mixed with the parent public key
> P using an index or nonce i:
>
>         h(i) := Hash(P || i || stuff)
>
> The first two schemes add a derivation factor (multiplied by the base
> point)
> to the parent pubkey, while the Tor's approach is to multiply the parent
> pubkey by the factor:
>
>         Child(i) := P + h(i)*G    // BIP32, ChainKD
>         Child(i) := h(i)*P        // Tor
>
> Last time I asked Pieter Wuille (BIP32's author) a couple years ago about
> their choice,
> his reply (if I recall correctly) was that scalar multiplication for a
> base point
> is more efficient than for an arbitrary point.
>

In an earlier draft of BIP32 at the time we were using multiplication as
well. At some point, the trick that allows recovering the parent key from
the parent public and child private key was brought up, and we realized
that neither multiplication nor addition could fix this. As addition was
faster and simpler, and didn't seem to have any security downsides over
multiplication, we switched BIP32 to use addition.

I think that was the right choice. I have had a few cases where it was not
obvious to people that multiplication with a scalar can be reversed
("Doesn't that need an EC division?"), while it is very clear that addition
is always reversable.

I wonder if there's a difference in functionality if we add the factor
> (a-la BIP32) or multiply (a-la Tor).
> Maybe some weird ZK schemes benefit from blinding/derivation via
> multiplication instead of addition?
>

If there are benefits to using the multiplication form, I'd very much like
to hear about them.

Cheers,

-- 
Pieter
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170427/85765117/attachment.html>