A group of n people (assume they are numbered 1,2,...,n) want to
jointly, and randomly, choose a leader.  That is, ideally everyone
should have the same probability of being chosen (even if a person is
not popular at all, that person's probability should be 1/n). Design a
protocol for achieving this.  Your protocol should be resistant to
collusion (collusion is when a subset of the n people is dishonest and
conspires against the others), including the case when n-1 people
collude against one person (but you do not need to consider the case
when all n of them collude - in that case they do not need a protocol
of the kind considered here). Make sure you give a proof that everyone
has probability 1/n of being leader, and discuss why your protocol is
resistant to collusion.

Hi eksolutions,

I presume you want a protocol that is capable of being implemented on
a computer. But first, let's consider how we would achieve the same
objective using a manual protocol.

Here's how it could work:

The candidates (whom we will number 1, 2, ..., n) sit around a table.
One person, whom we will call Joe, writes a number in the range 0..n-1
on a piece of paper, then inserts that paper into an envelope and
seals the envelope. That person places the envelope on the table in
front of them.

Each of the other candidates around the table, in turn (let's say
proceeding clockwise), moves the envelope around the table a number of
places, from zero to n-1, according to their choice.

After everyone else has moved the envelope, Joe opens it and shows
everyone the number written on the paper that was sealed inside the
envelope. Joe then moves the envelope a further number of places
according to what was written on the paper.

There is no scope for cheating by collusion. If the colluders include
Joe, they have no way to know what to write on the paper that goes
into the envelope - because they don't know how many places the
non-colluder(s) will move the envelope around the table. If the
colluders do not include Joe, they have no way to know how many places
to move the envelope around the table because they don't know how many
further moves will need to be made after the envelope is opened.

We can adapt this protocol for a computer by noting that a
cryptographic checksum can be calculated for any message. Although a
checksum can be easily calculated for a given message, it is
computationally infeasible (i.e. takes an impractically long time) to
compute a message that would generate a given checksum. Therefore, if
we are presented with a checksum, and later with a message from which
that checksum can be generated, we can be certain that the checksum
was indeed generated from that message. (But see the discussion later
about a problem with very short message lengths.)

Here's how the protocol would work:

The candidates are numbered from 0 to n-1 (arbitrarily).

Each of the 'n' candidates chooses a number randomly, in the range
0..n-1. To this number they append some random text to produce a
message of a reasonable length, then they generate the checksum of
that message.

Everyone then presents their checksum to the others. After everyone
has seen everyone else's checksum, everyone presents their message to
the others, who verify that the messages match their checksums.

Everyone's chosen random number is added together, and the remainder
modulo 'n' represents the number of the winning candidate.

Everyone has an equal chance of winning, and even with collusion it is
not possible to force a winner because there is no way to know what
random number will be presented by the non-colluding candidate(s). And
no-one can change the chosen random number embedded in their message
after the checksums have been distributed, because the change would be
detected when the other candidates test the checksum of the message.

In this protocol, it is necessary to pad the message to a reasonable
length because the message content is very short - just a single
number in the range 0..n-1. If the message was not padded, others
could generate a complete list of checksums for all messages
containing just a single number in the range 0..n-1. That would enable
the last candidate to know the "random votes" of all the preceding
candidates, and to adjust their own "random vote" to force their
desired outcome. But as soon as the message is long enough this
brute-force attack is no longer feasible.

As an alternative, public key cryptography and digital message signing
could be used instead of checksums (for this protocol and for your
"protocol2" example), but the rest of the protocol would remain
unchanged.


An example of a cryptographic checksum algorithm is MD5 - the "Message
Digest Algorithm, Version 5":

RSA MD5 Cryptographic Checksum Using DES
http://www.freesoft.org/CIE/RFC/1510/82.htm


Google search strategy:

"cryptographic checksum"
://www.google.com/search?q=%22cryptographic%20checksum%22


Regards,
eiffel-ga