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?