Re: CoinShuffle: Practical Decentralized Coin Mixing for Bitcoin

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

Aha, ok. I suspected something like this had been baked in at a low level. I was just surprised when I didn't see something like your "enc(ek, m, r)" in Section 5.2, or a note in Section 5.1 explaining that this was included in the definition of "Enc", or even a note about this in the otherwise quite verbose Section 6.1 - Unlinkability.

I think I was thrown off the scent a little by the use of "the ciphertext" from Section 5.1.

Quote

We denote by Enc(e_k; m) the ciphertext that encrypts the message m with the encryption key e_k.

Anyway, thanks for the explanation. I was sure it wasn't a problem; I just wanted to understand.