Discussion:
To multiply or to add in HKD schemes?
(too old to reply)
Oleg Andreev
2017-04-07 22:08:15 UTC
Permalink
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.

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?


[1] https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki
[2] https://chain.com/docs/protocol/specifications/chainkd
[3] https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.txt#n1979
Pieter Wuille
2017-04-27 17:45:26 UTC
Permalink
Post by Oleg Andreev
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
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
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
Post by Oleg Andreev
(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
Loading...