Key derivation of public key without knowledge of private key I'm looking for a convenient way to share a set of public keys across multiple services, while preserving privacy by preventing these services from tying the identity of these public key sets together across services.

E.g. If I share my public key set with both Service 1 and Service 2, Service 1 and Service 2 should not be able to work together to discover that I have an account on both services.

Note that I don't want to simply generate a new set of key pairs for each service, as the private keys are distributed across multiple devices for security reasons (to avoid a single point of failure), and generating a new key pair on each of these devices every time I want to set up authentication for a new service would be inconvenient for the user.

While considering the best way to satisfy these requirements, I believe I've reduced the problem to the following:


  Given a public key Kpub and some other bit of information x, I want to derive a public key K'pub such that the holder of Kpriv, and only that keyholder, given x, can find K'priv, and such that it is hard to find Kpub given K'pub and x.


So basically, it seems I want a key derivation function that can derive a public key, but which can't derive the corresponding private key without knowing some additional, secret information.

Is this possible? Is there any existing solution which satisfies the above requirements? Or am I breaking new ground here?
For public key encryption, there's an easy solution using a variant of Elgamal. (If you want to do authentication, you can use standard algorithms. If you specifically want signature schemes, say so.)

Recall that the security of Elgamal is equivalent to DDH, which is talking about indistinguishability of certain subgroups, namely given a cyclic group $G$, a (arbitrary) generator $g$ and an element of the group $y$, decide if the pair $(x,z)$ lies in the subgroup of $G \times G$ generated by the pair $(g, y)$.

We can phrase Elgamal as follows: To encrypt using the public key $(g,y)$, choose a random number $r$, compute $x=g^r$, $z=y^r$ and $w = zm$. The ciphertext is the pair $(x,w)$.

Deciding if $(x,w)$ is an encryption of $m$ is equivalent to deciding if $(x,w/m)$ lies in the subgroup.

Now observe that if $(g,y)$ is a public key, then $(g',y') = (g^b,y^b)$ is just as good a key.

Finally, to decide if $(g',y')$ and $(g'', y'')$ represent the same public key is equivalent to deciding if one lies in the subgroup generated by the other.

Most tricks you would use to improve the security of Elgamal would work for this variant as well, even with randomized keys.

With a bit of thinking, I am sure you can come up with lots of variations of this general idea.