Asymmetric key derivation – Who derives the new pub key can't know the new private key?

Question

I'm looking for a peer reviewed protocol or algorithm that can do this, preferentially I need something based on elliptic-curves cryptography.

Alice know the main public key of Bob (B-PUB-1). Alice want to derive a new public key (B-PUB-2) from Bob's public key (B-PUB-1) in an asymmetric way. The new key correspond to a private key (B-PRIV-2) that only Bob can generate by deriving it from his original private key (B-PRIV-1). This is done with only one communication from Alice to Bob without reply. The only important use of (B-PUB-1, B-PRIV-1) is to generate several different instances of key pairs (B-PUB-2, B-PRIV-2), to communicate Alice and Bob can use also other keys.

In this way Bob own a new private key corresponding to the public key created by Alice.
Bob now could produce some signature of a message m with B-PRIV-2 verifiable with B-PUB-2. A fundamental request is that B-PUB-2 and the signatures produced with B-PRIV-2 couldn't be related to B-PUB-1 by no one but Alice.

The purpose is not to allow Alice to be the only one able to verify the signature of the message.
At the contrary Alice will publish B-PUB-2 so everyone will be able to verify that m has a signature corresponding to B-PUB-2 but no one will be able relate this signature to B-PUB-1 and Bob.

The idea under this is that Bob trust that Alice has no interest in reveal his identity ( the fact that B-PUB-2 was derived from B-PUB-1) but Bob can't trust Alice completely.
She could try to use the generated keys to create fake signatures. So Bob can't simply ask Alice to generate a keypair, publish the B-PUB-2 and send to him the B-PRIV-2.

A sketch of the way I think algorithm could work:

• Alice choose some Random Secret
• Alice do something with that secret and Bob's public key (B-PUB-1) to create another key (B-PUB-2)
• Alice send the Random Secret to Bob with an encrypted channel, this can be done with normal public key encryption. To send the key Alice can use B-PUB-1 or a completely different Bob's public key if the use of B-PUB-1 for encryption cause security flaw.
• Bob obtain the Random Secret and do something with B-PRIV-1 to obtain B-PRIV-2
• Alice publish B-PUB-2
• Bob create a message m and sign it with B-PRIV-2
• Bob publish the message in anonymous way
• Everyone can control the signature with B-PUB-2

Answer 1

I am afraid this answer is long overdue, but what you are asking for is actually possible. It is even easy if you use public key cryptography relying on the discrete logarithm problem to secure the private key, such as ECDSA (for signature) & ECIES (for encryption) for example. And it might probably be possible for other schemes as well, but not as easily (at least, not in a way that seems as straightforward as for the discrete logarithm).

You can go around your problem using something like the derivation of the "shared encryption key" in ECIES.

In both ECIES and ECDSA, the private key $k$ is a large integer, while the public key $P_{k}$ is a point on the elliptic curve $\mathrm{E}$ derived from $k$ by computing $P_k=k\cdot G$, for $G$ a generator of the curve with large prime order $n$ (which is generally standardized along with the curve you're using).

This means that you can actually derive another public key $k\cdot G$ just like what you are asking for by:

1. Alice picks a random secret integer $r$
2. She computes the point $R=r\cdot G$ on the curve $\mathrm{E}$
3. She can then compute the derived public key $P_{kr}$ by adding the public key point $P_k$ and the point $R$ together: $P_{kr}=P_k+R$

And now, the corresponding private key $k'$ is simply $k'=k+r$, because of the definition of the scalar multiplication, which make it distributive over the group law $+$, which means that $P_k+R = k\cdot G + r\cdot G = (k+r)\cdot G$.

So Alice can simply send $r$ to Bob, and Alice would still not be able to sign anything (in the ECDSA case) for this child public key $P_{kr}$.

Knowledge of $r$ merely allows to discover the "main" public key $P_k$. (So you might want to keep it secret, depending on your needs.)

If you want to adapt the scheme to something else than elliptic curves, you might, but you'll have to rely on the discrete logarithm problem to use the same trick. For instance, this specific method wouldn't work with RSA keys.

PS: I am also aware of a more intricate scheme used in certain Bitcoin wallets, but I haven't had time to study it yet and the scheme presented above is way simpler. But just in case, you might also want to check what's done in BIP32.

Answer 2

I am not aware of a scheme that fulfills your requirements as defined above, but:

If your goal is that Bob can sign a message such that only Alice can verify it and she can proof no one else that this message was sent by Bob then chameleon signatures aka deniable signatures are the tool you are looking for.

Schemes were proposed in Hugo Krawczyk, Tal Rabin: Chameleon Hashing and Signatures (1997) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.3262

If you are looking for schemes where the private key is changed over time you might want to have a look at forward secure signatures / encryption.

Answer 3

In Ed25519 a private key is simply a 256 bit random number, and the public key is derived easily from this. The public key can also easily be interpreted as a 256 bit number.

Bob can send Alice his public key, Alice can generate a secrete nonce, and then use a HMAC of the key and nonce to generate herself a new private key.

If she communicates the nonce back to Bob he will be able to generate Alice's private key in the same way.