Say four people each have a public/private key pair that they can use to encrypt or sign messages. They have an anonymous way to post messages such that the others can see them. Malicious entities can post messages as well, but they can't forge the signatures these four can make.
I'm looking for an algorithm so that the four can, by exchanging posted messages, agree on a new set of four public keys such that each of them knows exactly one corresponding private key. But here's the hard part: None of the four of them can know which private key any of the other three parties know.
If they had a trusted intermediary, they could do it this way: Each of them submits the full set of four public keys to the intermediary, signed with their key. The intermediary confirms the key sets are identical and one set is signed with each key in the set. Each of them submits a new public key, signed with their existing public key, encrypted with the intermediary's public key. The intermediary decrypts these messages and publishes only the list of new public keys in random order, signed with his key.
Of course, I need to do it without a trusted intermediary.
It is okay if observers know the new set of public keys (they're public after all) so long as they don't know which new public key belongs to the same entity as each public key from the start.
It is critical that an attacker who can post messages not be able to slip his public key in. This is a challenging requirement because any message that contains a new key can't be signed with an old key or you can tell which old key corresponds with which new key.