Cryptography and Draw of Lots

Recently, I was told of a very ingenious and effective way to manipulate the draw of lots even though the lots were drawn in the old fashioned way in the presence of all stakeholders. Even if the person who is drawing the lots is bribed, it might appear that it is difficult to manipulate the outcome. The lots have to be drawn from a closed container into which only the hand can be inserted, and it is not possible to read the token before it is drawn. Any attempt to make the tokens recognizable before they are drawn (say by changing their shape or size) would be obvious to those present. Even if participants do not detect the manipulation during the draw, the altered shape or size could still be detected during any inspection or audit even after the draw.

I was informed of an alleged instance of successful manipulation of draw of lots where the manipulator resorted to the simple expedient of keeping the desired tokens in a refrigerator before the draw. The person drawing the lots was bribed to feel the tokens carefully and draw the cold tokens. Even if people get suspicious and try to inspect the container and the tokens after the draw, the fraud cannot be detected after the lapse of some time as the refrigerated tokens would quickly return to room temperature. (Perhaps, this warming process could also be accelerated by vigorous handling of the token).

In some contexts (lotteries for example), machines have replaced the traditional draw of lots, but these machines are vulnerable to manipulation by the manufacturer and the operator. Computers can draw random numbers to simulate the draw of lots, but then one would have to trust the programmer and the computer operator who can also be bribed.

How can one have a secure draw of lots? The critical idea is that it is not enough for every stakeholder to observe the draw of lots; it is necessary for everyone to actively participate in drawing the lot. Consider a very different problem – that of cutting a cake fairly. A complete solution to this problem was presented more than half a century ago (Dubins, Lester E., and Edwin H. Spanier. “How to cut a cake fairly.” American Mathematical Monthly (1961): 1-17.). To divide a cake between two people, the solution is for “one to cut, the other to choose”. With more than two people, the solution is a little more complex, but the core idea is still that of letting everybody participate in the division:

A knife is slowly mоνed at соnstаnt speed parallel to itself оνer the top of the саke. At each instant, the knife is poised so that it соuld сut а unique slice of the саke. As time goes by, the potential slice increases monotonely frоm nothing until it becomes the entire саke. The first person to indicate satisfaction with the slice then determined by the position of the knife receiνes that slice аnd is eliminated from further distribution of the cake. … The process is repeated with the оthеr n-1 participants аnd with whаt remains of the cake.

The idea of letting everybody participate in the draw of lots would work as follows. The tokens are numbered from 0 to n, and each person writes a number from 0 to n secretly on a piece of paper, folds it and drops it into an open receptacle. This ensure that each person chooses the number without knowing the choices of anybody else. When everybody has done this, all the pieces of paper are take out and unfolded, the numbers are read out and totalled. The resulting total is divided by n to determine the remainder. The token corresponding to this remainder is selected.

Put in a dash of cryptography, and this method can be scaled up to operate with any number of participants spread across the globe. Instead of hiding the number by folding it, participants compute a cryptographic hash of their chosen number (with some additional salt).

The ideal cryptographic hash function has four main properties:

  1. it is easy to compute the hash value for any given message
  2. it is infeasible to generate a message from its hash
  3. it is infeasible to modify a message without changing the hash
  4. it is infeasible to find two different messages with the same hash.

Instead of putting the pieces of paper into a receptacle, everybody publicly announces the hash of their chosen number. After everybody has done this, each person reveals the chosen number and everybody can verify that the hash announced earlier is correct. The numbers can then be totalled and divided by n to find the remainder.

As usual, cryptography is a powerful tool and can accomplish many things. We just need to use it creatively.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s