A couple minutes ago Phantomcircuit directed me to this writeup, which I'd not see before. It's a great proposal and does better from a privacy perspective of my earlier suggestions of ZC + TOR or Cham+Tor. And it's not especially new either! here we see the problem with just pumping out theory and not implementations: The activity in this thread is already more practically useful than that year old blog post.
In any case, they propose using multi-party computation to SORT a list of pubkeys provided by the participants. This accomplishes two things: Blinds the participants to whos keys is whos but makes sure that everyone knows that the pubkeys all came from the participants. Using chaum accomplishes only the latter but would depend on using tor (or the like) to prevent participants from learning the mapping. This is somewhat non-ideal if we want to be super paranoid about such things since tor is very vulnerable to timing analysis.
I'd looked into using MPC for this before but I was overthinking it and expecting the MPC to do too much and it didn't seem practical. It did not occur to me that we only needed a _sort_ to hide the correspondence.
So to make this real you need a multi-party computation system that can implement a sort: Here you go: http://viff.dk/ to use it build it then run
./apps/generate-config-files.py 127.0.0.1:10001 127.0.0.1:10002 127.0.0.1:10003
then
./apps/sort.py --no-ssl player-1.ini
./apps/sort.py --no-ssl player-2.ini
./apps/sort.py --no-ssl player-3.ini
(It appears to be a bit python bitrotted and doesn't actually work for me ATM)
The sort.py script is setup for three players providing inputs, and they pick random values to sort (with an array of size
.. all of this can easily be adjusted.
The protocol requires log2^2(N) communications between all the participants. You'd have every player provide a pubkey, at the end they all get a sorted list and learn nothing about who sent what.
Downsides:
* Thats a boatload of communication for a lot of participants, especially since you'd still run this over tor to hide the inputting parties IPs. This means that you probably have to have all parties online and communicating in realtime... if people are only logging on once per day, an 8 party operation would take 10 days I think. (log2^2(N))
* The MPC implementation in viff only has security against passive attackers e.g. they might snoop but they follow the protocol. VIFF has some code for a different kind of MPC which is secure against active attackers but I've never been able to get it to work before (in particular, it doesn't seem to have a comparison operator... which.. uh. sort really needs).
* Also, this is all expensive enough that it's probably not helpful for preventing DOS even if the activity model does let you detect which party is misbehaving.
Upside: no depending on TOR for hiding the mapping between parties, and stronger fundamental security than tor, to keep players identity secret from each other.
(Also downside will take work to go implement this in an actual system
)
In any case, they propose using multi-party computation to SORT a list of pubkeys provided by the participants. This accomplishes two things: Blinds the participants to whos keys is whos but makes sure that everyone knows that the pubkeys all came from the participants. Using chaum accomplishes only the latter but would depend on using tor (or the like) to prevent participants from learning the mapping. This is somewhat non-ideal if we want to be super paranoid about such things since tor is very vulnerable to timing analysis.
I'd looked into using MPC for this before but I was overthinking it and expecting the MPC to do too much and it didn't seem practical. It did not occur to me that we only needed a _sort_ to hide the correspondence.
So to make this real you need a multi-party computation system that can implement a sort: Here you go: http://viff.dk/ to use it build it then run
./apps/generate-config-files.py 127.0.0.1:10001 127.0.0.1:10002 127.0.0.1:10003
then
./apps/sort.py --no-ssl player-1.ini
./apps/sort.py --no-ssl player-2.ini
./apps/sort.py --no-ssl player-3.ini
(It appears to be a bit python bitrotted and doesn't actually work for me ATM)
The sort.py script is setup for three players providing inputs, and they pick random values to sort (with an array of size
.. all of this can easily be adjusted.The protocol requires log2^2(N) communications between all the participants. You'd have every player provide a pubkey, at the end they all get a sorted list and learn nothing about who sent what.
Downsides:
* Thats a boatload of communication for a lot of participants, especially since you'd still run this over tor to hide the inputting parties IPs. This means that you probably have to have all parties online and communicating in realtime... if people are only logging on once per day, an 8 party operation would take 10 days I think. (log2^2(N))
* The MPC implementation in viff only has security against passive attackers e.g. they might snoop but they follow the protocol. VIFF has some code for a different kind of MPC which is secure against active attackers but I've never been able to get it to work before (in particular, it doesn't seem to have a comparison operator... which.. uh. sort really needs).
* Also, this is all expensive enough that it's probably not helpful for preventing DOS even if the activity model does let you detect which party is misbehaving.
Upside: no depending on TOR for hiding the mapping between parties, and stronger fundamental security than tor, to keep players identity secret from each other.
(Also downside will take work to go implement this in an actual system
)