Algorithm to securely exchange identities

Question

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.

Answer 1

The Simple Protocol:

1. 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.

2. 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.

3. (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.

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].

5. 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.

6. 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.

Answer 2

One quick idea. I didn't analyze it thoroughly, especially concerning active attacks by the participants.

1. Everybody creates a new RSA keypair, signs it with the old private key and publishes it.
2. Everybody creates their new key pair
3. Everybody uses the new public key as message and creates the hash and signature padding for each of the Step 1 RSA keys. Then he blinds them. And finally he signs them with his old keypair and publishes them.
4. Everybody textbook signs the blinded messages with his RSA private key from step 1. They can see which are valid, because they were signed with the original key.
5. Everybody unblinds his own public key messages

Now those new public keys are valid that have a valid signature of everybody's step 1 RSA key.

Answer 3

Would TOR-like onion routing work for this problem?

• On Monday, each person posts a "package" -- Alice's address (Alice's public encryption key) (one of the original 4 keys), a blob of data encrypted by Alice's public encryption key, the whole thing signed by his own private signing key (one of the original 4 keys).
• Alice verifies the signature, then decrypts the blob. Inside she finds a "exchange identities protocol" message, and a smaller blob (encrypted with Bob's public encryption key).
• On Tuesday, Alice attaches Bob's address (Bob's public encryption key) (one of the original 4 keys) and signs(*) each of those smaller blobs, and posts the signed messages in some random order.
• Bob verifies Alice's signature on those 4 messages, decrypts, finds the standard message and a smaller blob (encrypted by Charley's public encryption key).
• On Wednesday, Bob attaches Charley's address (Charley's public encryption key) and signs(*) each of the smaller blobs, and posts the signed messages in some random order.
• Then the same thing -- Charley verifies Bob's signature, decrypts, finds the standard message and an unsigned smaller blob.
• By the time next Tuesday rolls around, the initial 4 packages have been routed in order through all 4 people twice, and have had practically all the onion-layers peeled off.
• The final person in the chain, after peeling off the last layer, sees that the now-tiny package contains only a fresh new never-seen-before-in-public public encryption key.
• The final person in the chain posts a message saying "here's the new anonymous public encryption key" with that never-seen-before-in-public public encryption key, and signs it with his (old) signing key, and posts it Wednesday.
• By Thursday, there should have been 4 new anonymous public encryption keys posted.
• On Friday, each of the 4 people signs (with their old key) a message that includes "Yes, one of the 4 following keys is mine", and also includes the 4 new keys in sorted order.

Since all 4 packages go to the same person on the same day, then the randomness that person introduces makes it impossible to track which of the 4 incoming messages matches up with the 4 outgoing messages that person signs.

(*) Rather than blindly signing these small blobs sight-unseen, it's better to form a larger package that contains the original contents of the larger blob -- the "exchange identities protocol" message and the smaller blob encrypted by the "next address", then encrypt that whole package with the same "next address" public encryption key, and then attach the same "next address" to the outside and sign the whole thing with his private signing key.

It's not possible for an attacker who can post additional messages to disrupt this protocol, since every message posted in this protocol is signed by one of the old original 4 private signing keys that the attacker doesn't know, and so any message posted by the attacker will fail verification and be rejected.