Key derivation of public key without knowledge of private key
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.