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

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
-
@fgrieu Thanks for comment. I edited the question to clarify. Random secret is confidential, only Alice and Bob know it. The only fundamental purpose of (B-PUB-1, B-PRIV-1) is to generate different instances of secondary keys. – Kazuo K Mar 25 '14 at 21:55
I modified the title and the question to better explain what I need. – Kazuo K Apr 9 '14 at 11:12

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.

-
I didn't know the chameleon hashing. I understand that the purpose of my question seems to be finding a way to allow only Alice to verify a signature, but it is very different. Alice must publish the key B-PUB-2 so everyone could verify a signature created by B-PRIV-2 but no one except Alice could know that the message was signed by Bob. Bob decide to trust Alice on the fact that she will not reveal his identity but he don't want that Alice could sign a message with the new key. – Kazuo K Mar 26 '14 at 15:41

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.

-
If I correctly understood your answer you suggest to use B-PUB-1 to generate the new key pair (B-PUB-2,B-PRIV-2) but in this way Alice know the private key B-PRIV-2 so she can generate fake signatures with this key. In your example Bob use his public key B-PUB-1 and the nonce generated by Alice to create the new key with the HMAC, but in this way there isn't asymmetry, Alice use the same parameters as Bob. – Kazuo K Mar 26 '14 at 15:17
I think I originally misinterpreted your aim. – Ivo Mar 26 '14 at 18:17