Families of public/private keys in elliptic curve cryptography

I'm looking for a related key scheme for elliptic curve cryptography. The basic idea would be that there would be a master public key and a master private key. From the master public key, you could generate a series of public keys. From the master private key, you could generate the corresponding series of private keys.

Ideally, without the master public key, even given a number of public keys in the series, it would be impractical to determine any other public keys in the series or the master public key.

I've been told that it's possible, and have just the following description of how it would be implemented:

S = Random number
RootPrivateKey = Random number
RootPublicKey = RootPrivateKey*point

Master Private Key = RootPrivateKey, S
Master Public Key = RootPublicKey, S

PrivateKey(n) = RootPrivateKey + Hash(n|S)
PublicKey(n) = RootPublicKey + Hash(n|S)*point

I understand the first five lines. But I am, unsure about the implementation details in the last two lines. Is the + supposed to be addition? If so, is it modular? In the public key, is + adding the two EC points? If anyone knows of any example code, ideally using OpenSSL, that would be the most helpful.

The typical use case for this kind of thing is creating deterministic wallets for crypto-currencies like Bitcoin.

I would assume that all the operations are to be done in the elliptic curve group (viewed as a module over $\mathbb Z/k\mathbb Z$, where $k$ is the order of the group), so that addition is the group operation and multiplication is elliptic curve point multiplication.

That is to say, assume we have an elliptic curve $E$, equipped with the point addition operator $+$ so that $(E,+)$ is a group. We can define a scalar multiplication operation on $E$ simply as $$n \cdot P = \underbrace{P+P+\dotsb+P}_{n \text{ times}},$$ where $n$ is an integer and $P$ is a point in $E$. Let $G$ be a point in $E$ which generates a cyclic subgroup of $E$ of order $k$: that is, $k \cdot G = 0_E$ (and $0 < j < k \implies j \cdot G \ne 0_E$), where $0_E$ is the group identity of $(E,+)$. All these are public parameters shared by all users of the group.

In ordinary ECDSA, we would choose a random private key $x \in \mathbb Z/k\mathbb Z$ (that is, a random integer such that $0 \le x < k$) and compute the public key $Q = x \cdot G$.

However, if we also had a function $H$ mapping integers to (pseudo)random values in $\mathbb Z/k\mathbb Z$, we could define a sequence of private keys and corresponding public keys as $$x_i = x + H(i)$$ $$Q_i = x_i \cdot G = Q + H(i) \cdot G$$ where the $+$ on the first line stands for ordinary addition (modulo $k$) and the $+$ on the second line is elliptic curve point addition. (A consequence of the way we defined scalar multiplication above is that addition distributes over it: $(a + b) \cdot P = a \cdot P + b \cdot P$.)

There are various ways in which we could define $H$. For example, we could use a hash function as in your example, possibly with a salt $S$, or we could perhaps pick a block cipher $B$ and a random key $K$, and let $H(i) = E_K(i)$. In fact, assuming that $H$ and $Q$ are indeed truly public, I'm not even sure that there's any reason not to just use $H(i)=i$. (Indeed, I can't even prove off the top of my head that this scheme is secure for any $H$.) But the salted hash certainly seems as good as any other choice for $H$.

Edit: I just noticed that you wrote:

"Ideally, without the master public key, even given a number of public keys in the series, it would be impractical to determine any other public keys in the series or the master public key."

I'm not sure if you wanted that to be impractical with or without knowledge of $H$ and of the indices $i$ corresponding to the known public keys $Q_i$.

If with, we have a problem: anyone who knows $H$, $i$ and $Q_i$ can calculate $Q = Q_i + (k-H(i)) \cdot G$.

If $i$ and/or $H$ can be treated as secret, things get trickier. Obviously, $H(i)=i$ is a bad choice in this case, since anyone who knows $Q_i$ could then calculate $Q_{i+j} = Q_i+j \cdot G$ for any $j$, but using a hash or a block cipher for $H$ would eliminate that simple weakness.

Also, regardless of $H$, someone who knows $Q_i$ and $Q_j$ can calculate $Q_i - Q_j = (H(i)-H(j)) \cdot G$; but I'm not sure what, if any, good that would do them, assuming that $H(i) - H(j)$ is not likely to equal $H(k)$ for any valid index $k$.

Anyway, it would be helpful to know just what parties are supposed to be involved in this scheme and what they're supposed to know. In my original answer, I'd been implicitly assuming that the public keys were, well, public and known to everybody. If that's not supposed to be the case, that could complicate things a lot.

• Note that here from one private sub-key you can easily get back to the master private key, though this is not that easy for the public keys. Not sure if this might be a problem. Dec 25 '11 at 11:37
• The public keys are public, but they're lost in a sea of public keys. The idea is that someone should not be able to tell, given some of your public keys, whether a given public key is one of yours or not. But using a secure hash function and keeping S secret should do that. Dec 25 '11 at 18:46