3 ms·
But in many cases, you want all parties to be able to confirm fair play. In this example, if any of ‘everyone’ can see all the other n-bit random numbers befor
by Someone 6y ago
But in many cases, you want all parties to be able to confirm fair play.
In this example, if any of ‘everyone’ can see all the other n-bit random numbers before broadcasting their n-bit number, that party had complete control over the result of step 2.
One way to solve that is by appointing a party P to do step 2, have all parties communicate their number to P in private, and then have P do the XOR.
Problem with that is that you have to trust party P. Even if you require it to not only report the result of step 2, but also all the numbers generated in step 1, P can collude with one of them to generate any result those two parties want to generate, and all parties can claim they didn’t send P the number P says they sent him if they’re not happy with the result of step 2.
A better approach:
- each party picks a random encryption key
- each party encrypts their n-bit number with that key
- each party broadcasts the encrypted number to the world
- once a party knows that all parties have seen all encrypted numbers (how to know that is left as an exercise for the reader), it broadcasts its encryption key.
- eventually, all parties will have seen all encryption keys.
- once a party has all encryption keys, it can decrypt the encrypted n-bit numbers and XOR the results.
Even ignoring the exercise for the reader, the above likely has holes. I’m not an expert in this field.
https://en.wikipedia.org/wiki/Byzantine_fault https://en.wikipedia.org/wiki/Byzantine_fault probably is a better starting point for this kind of problem (but doesn’t give a solution to this specific problem)