If a pseudonym is reused often, then correlation could be used to link all inputs with the pseudonym that provided them. This could the be further used to see if outputs from mixed transactions that the pseudonym in question has been part in often has some outputs in common, thus deanonymizing users who use this frequently for the same outputs (assuming the recipient has repeating or non-individual payment/donation addresses, which is common).
Ah okay, yes the anti-dos pseudonym tracking is why I had suggested the method of using the input coin itself as the identity.
I've read that SMPC has been used IRL successfully for auctions for farms selling their goods. Can't remember the source. SMPC should be possible to run on most hardware. There's multiple implementations of it, some in Java and some in C.
A specialized for doing a meet in the middle auction (e.g. a few comparison operations and an arithmetic average) is a whole other of magnitude less complex than running a complete transaction processing program in it. Going and figuring out where the state of the art is in that space has been on my todo list.
How would a homomorphic mix work?
Every participants has a key for a homomorphic encryption scheme (which can be decrypted or encrypted in arbitrary order). Each party encrypts their signature with everyones key, the signatures are grouped up and passed around, with each peer permuting their order and applying a re-encryption operation. At the end they all decrypt in sequence and you get a mixed output. The downside is that people can silently jam the mix by replacing or corrupting data during reencryption. To prevent this you need to do cut and choose (e.g. mix 10000 times, commit to all of them, one gets picked as the real mix output and you reveal the rest) and that takes a lot of bandwidth.
As an aside I hope the cryptowizardy for the decenteralized versions of this aren't scaring people off. Part of the merit of CoinJoin as an idea is that there are braindead simple ways of using these ideas that don't require cryptomagic and are only somewhat compromised compared to what you can do with maximal magic. I personally find the magic very exciting, but I find actual systems that people can use even _more_ exciting. I hope people will work at this space from both ends.