Quote from: TierNolan on April 24, 2014, 12:29:30 PM

How do you handle a case where a participant refuses to send on a message to the next person?

Does each of the communications have to kept secret?

When you say Bob -> Charlie, do you mean it is a broadcast?

The communication does not have to be secret. And you already indicate a possible answer to your first question: In the case that a participant, say Charlie, claims not to have received a message from his predecessor, broadcasts are a possibility to find out which of the parties really failed. Without going into details, the PeerReview protocol is one possible fully-fledged solution that we mention in our paper but explaining the whole idea would be too much for this thread. To demonstrate that those problems are solvable, I can sketch a simpler (but probably not so efficient) solution later if you are interested.

Quote from: TierNolan on April 24, 2014, 12:29:30 PM

Are the messages digitally signed too?

Yes, all messages are signed using the private signing key belonging to the input address. I added that to the posting. (Sorry, I simplified too much with respect to that aspect. Wink

)

Quote from: TierNolan on April 24, 2014, 12:29:30 PM

You should explain the blame stage too.

Your example is already quite nice. It shows the most interesting case, namely what happens if something goes wrong during the shuffling. Then the participants publish their private decryption keys and everybody is able to replay every step of the shuffling to find out who misbehaved. (Publishing the decryption keys is not a problem, because the participants have to restart the protocol anyway. Somebody may be able to link, e.g., A and A', but no transaction involving A' is generated. The output address A' is just discarded and in the subsequent run, the users will create fresh output addresses and fresh encryption/decryption keys.)

Things can also go wrong in other phases too. Let me give one example, namely for phase 1: Somebody could send different encryption keys to different users in phase 1, e.g., Dave sends ekD1 to Bob and Charlie, but ekD2 to Alice. (This is called equivocation.) Dave will then learn that A' is Alice's output address: It's the only output address encrypted with ekD2. And if Charlie colludes with Dave, Charlie would not report that he obtained ciphertexts encrypted with different keys during the encryption. To exclude this attack, the full protocol contains an additional equivocation check between phase 2 and 3: Everybody signs the list of all encryption keys and broadcasts the list together with the signature. Only if everybody has the same view on the encryption keys, the protocol continues normally. (I did not include this step the posting above for simplicity, the goal of the posting was rather to get the core idea across.)
If the participants have different views on the list of keys, this will be detected in this additional step. In the example above: Alice would publish the signed list (ekB, ekC, ekD1) but Bob would publish (ekB, ekC, ekD2). In that case, the blame phase would be entered too. From the point of view of the users, there are two possible cases now: Either Dave has really equivocated, or one of Alice and Bob is claiming to have received a key from Dave that he/she actually has not received. To find out who is malicious, Alice and Bob can just publish the signed messages that have they received from Dave in phase 1. That will clarify if they have published a wrong list of keys or if Dave has equivocated by sending different keys. So one malicious user is exposed at the end of the blame.

---

Quote from: teukon on April 24, 2014, 07:56:25 PM

Quote from: wladston on April 24, 2014, 07:06:31 PM

@teukon's observation seems relevant. However if Alice includes some random data along with her address, but Dave only publishes a list of addresses (without the extra random data) them Bob couldn't determine Alice's address.

This was my first thought. I checked out the paper to see if something along these lines had been included but found nothing. I'd add to this and suggest that all participants add some random data to each level of the layered encryption. If they add random data just to their address at the beginning, then Bob and Dave, working together, could determine Alice's (and therefore also Charlie's) address.

There seems to be a misconception about encryption in general. Every secure* encryption scheme always uses randomness for the encryption to make sure that encrypting the same message twice does not yield the same ciphertext. This is exactly to exclude attacks like the one described above; such attacks are a general problem in cryptography, not only in this protocol. The added randomness is built in the encryption algorithm itself, one does not have to add randomness manually to the message before giving it to the algorithm. One typically leaves the randomness implicit: When I write enc(ek, m), I actually mean enc(ek, m, r), where r is fresh randomness.
Try it: Take any encryption tool and try to encrypt the same message twice. Wink

* This holds for every standard cryptographic definition of "secure". In particular, it holds for IND-CCA, the security definition that we require to be achieved by the used encryption scheme.

---

@BitcoinDream:
A trusted third party does not help here! (That's why we would like to avoid it.) Mixing is not possible if you are the only honest user. You need at least one other user that is also honest.
Assume you are Bob. Further assume that Alice, Charlie and Dave are malicious and collude. No matter how you organize the mixing with a trusted third party or not, Alice, Charlie and Dave can observe the output of the mixing (e.g., by looking at the blockchain). Thus they observe four output addresses A', B', C', D'. Because they know that A', C' and D' are their own addresses, they can determine that B' is your address.