Algorithm to securely exchange identities 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.
The Simple Protocol:



Alice generates a signature key pair (to sign in step 4, all other signatures in the protocol will be from the original key pairs), calculates its encryption under each of the other participant's public keys, indicates which encryption corresponds to which key, and then signs and posts the result.
The other three participants each decrypt the message encrypted with their public key, calculate the encryption of that under the public keys belonging to the other two of those three participants, indicate which encryption corresponds to which key, and then sign and post the result.
(With signed messages) Those three participants confirm that they got the same signature key pair from all three sources, and then all four participants agree on a time period for step 4.
Each participant generates a new key pair, and posts the public key along with its signature under [the signature key pair from step 1].
Once four posts with a public key and its signature under [the signature key pair from step 1] have appeared, each participant posts a signed confirmation, with the lexicographically sorted list of those four messages, that their public key was the public key in one of those messages.
After each participant has confirmed in step 5 (and made sure the lists of messages match), use the public keys from step 4.




The potential problem is that a participant can trivially force an abort with zero chance of getting

caught. $\:$ Every way I can think of for this loses the property that the [honest participant]-[key pair] relations will be forever hidden from an attacker who doesn't break the cryptosystem before

the protocol ends (long-term security for all participants). $\:$ The best way I can think of is:

(With all messages signed),
Use generic multi-party computation to compute the lexicographically sorted list of a new public key from each party. $\:$ This requires oblivious transfer, and I have no idea how many of them it will need. $\:$ This does not need any anonymous posts, and works against any number of disruptive participants.  Depending on what oblivious transfer protocol is used, this might provide long-term security for one of the participants.