4
$\begingroup$

I'm looking to identify the EC key derivation method used in Hyperledger Fabric. I can't find anything in the docs or the protocol specs, but the functions' code is here for the private key and the public key.

The derivation function seems to be very simple, DerivedPrivate = MasterPrivate + (k+1) and DerivedPublic = MasterPublic + (k+1) * G all mod N with k being a random derivation data. And yet, I don't seem to be able to find the name or the source of this method.

I'd like to know about the patent and copyright status of this derivation method, and to do that I need something to google for. I'm also looking for a more formal description of this method.

$\endgroup$
  • 2
    $\begingroup$ Homomorphic addition property of scalar multiplication over elliptic curves. $\endgroup$ – Youssef El Housni Jan 30 at 20:09
  • $\begingroup$ @YoussefElHousni Right, would you say this is something commonly used in EC key derivation? I would love to see a link / hint where this is described in that context. $\endgroup$ – Fozi Jan 30 at 20:21
  • $\begingroup$ Generally we don't consider questions about patents and copyright status on topic here, see for instance this meta question / answer. I'll leave it in the question, however I would say that answers do not need to cover the patents / copyright status part of it. Otherwise a fine question by the way. $\endgroup$ – Maarten Bodewes Jan 30 at 20:45
  • 1
    $\begingroup$ Related question that essentially proposes the same scheme. I don't think there's a name for this scheme, it's simply a consequence of $(a+b)G = aG + bG$ i.e. the distributive property. $\endgroup$ – puzzlepalace Feb 14 at 19:34
  • 1
    $\begingroup$ Yeah, I guess some schemes are too simple to gain their own name. E.g. PKCS#7 padding means "the only padding scheme mentioned somewhere in PKCS#7". I guess Youssef had a good descriptive name for it, so I thought it was a good idea to have this question set to "answered" none-the-less :) $\endgroup$ – Maarten Bodewes Feb 15 at 14:38
4
+50
$\begingroup$

Common terms for this include hierarchical key derivation, hierarchical deterministic keys, and key blinding. It is sometimes called ‘hierarchical’ because you can repeatedly derive subkeys $Q = [k_1]G + P$, $R = [k_2]G + Q$, etc., and the process is a deterministic function of the tags $k_1$ and $k_2$ and the initial point $P$. It is sometimes called ‘blinding’ because knowledge of $Q = [k]G + P$ and the standard base point $G$ without the blinding $k$ gives no information about $P$.

You can find practical examples in Bitcoin's BIP32 and related protocols, in the Tor v3 onion service protocol, and in the PrivacyPass protocol.

The two common variants are additive and multiplicative blinding: $[k]G + P$ vs. $[k]P$, both of which are invertible, by $Q - [k]G$ or $[k^{-1} \bmod n]Q$ where $n$ is the order of the group. The additive variant has the advantage that it always uses fixed-base scalar multiplication, and only a single curve addition, which may or may not make a difference in your protocol.

The analogues in the finite field setting are, of course, $G^k\cdot P$ and $P^k$ with inverses $Q/G^k$ and $Q^{k^{-1} \bmod n}$, but while you'll see this notation in the PrivacyPass paper nobody verbalizes talk of this because while we can say ‘multiplicative’, who can bring themselves to verbalize ‘exponentiative’ without getting distracted wondering whether the word even exists?

$\endgroup$
  • $\begingroup$ Thanks for the answer, it pointed me to the right direction. I see differences in how k is dealt with in the examples. Looks like here k is limited to 1..n by doing k = (DerivData + 1) mod n. This eliminates k=0, but it does not seem to deal with the special case where k = n - d where the derived key would be zero. I'm not sure why there is a check whether the public key point is on the curve. At least on the private key derivation side a `d' == 0' check should be all that is needed? I think my question is answered though, it seems like it's a proprietary spin on a EC curve property. $\endgroup$ – Fozi Feb 16 at 18:23
  • $\begingroup$ @Fozi If $n$ is the order of the base point, it will be near $2^{256}$ in any reasonable system. Then a uniform random scalar modulo $n$ has probability near $2^{-256}$ of being zero, or of being $d$. It also has probability near $2^{-256}$ of being 81209715721608798040795492854713186617949497074300142088404940059431870078213. If any of these happened, it would be devastating to security because the adversary immediately knows these numbers. Maybe DerivData isn't uniform random modulo $n$, but as long as it's uniform random with, say, ${\gg}2^{200}$ bits, edge cases like that don't matter. $\endgroup$ – Squeamish Ossifrage Feb 16 at 21:01
  • $\begingroup$ @Fozi As for whether to check whether the point is on the curve: depends on more context—give the additional context in a separate question. As for ‘patent’, and ‘copyright’, ‘proprietary’: can't patent a mathematical formula, can't copyright an abstract concept outside a fixed medium, and definitely can't own an idea. I'm not a soul-eating vulture like a patent attorney—I just eat bones—but I'd be rather surprised if anyone asserted a patent claim on the concept of homomorphisms. Even if you add a $\cdots + 1$ too. $\endgroup$ – Squeamish Ossifrage Feb 16 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.