I think it might in theory be possible to create an anonymous id from a non-anonymous id. First you’d create the public non-anonymous id from a central registry, basically creating a decentralized version of the central registry, or maybe via web of trust. All public keys would be stored in a decentralized register of non-anonymous public keys.
Then you have a public non-anonymous id that consists of a public/private keypair. Can you then create a new id, i.e. a new public/private keypair, from the non-anonymous keypair, that would have the property that each non-anonymous private key could be used to create one and only one new private key, which couldn’t be linked back to the other key? Sounds like a hash function doesn’t it.
If you hash your private key, you would have achieved one of these, getting a new private key that can’t be linked to the private key used to generate it, and this new private key could again be used to generate a public key.
The second property is the more tricky one. How can I verify that your new public key corresponds to one, and only one, of the keys in the set of known non-anonymous public keys, without being able to figure out which one?
Not sure how to solve the second part, but I’m sure there is some clever way to do it.
Of course there would be lots of issues to make this work, like ways to protect against timing attacks to prevent ids being linked, ways to revoke an id and create a new one in case someone managed to link the id to a person etc. Tricky issues, but I don’t think they’re insolvable, though it could be that some parts might require things that are not yet really feasible, like fully homomorphic encryption.