Games for Extracting Randomness

July 17, 2009 by Richard Conlan

http://cups.cs.cmu.edu/soups/2009/proceedings/a12-halprin.pdf
Ran Halprin and Moni Naor

Random number generation is important for many security tasks - especially cryptography.  And yet getting good random numbers is notoriously difficult in practice.  Sources of randomness traditionally include “secret” data such as MAC addresses; real-time data such as hard-disk access and click timing; physical sources such as lava lamps, cloud patterns, and atmospheric noise; and requesting the user do something randomish like striking a bunch of keyboard keys.

How can we safely ask the user?  Humans aren’t very good at recognizing randomness, let along generating it.  This study proposed involving the user in a competitive game on the idea that the user behavior will behave erratically during the game and that the user will be accepting of such a technique of gathering randomness.  The study proposed a game, “Mice and Elephants,” which was designed to be easy to play, not require much in the way of resources, and encourage users to employ strategies with high entropy.  The gameplay instructs the player to hide r mice on an grid after which the computer moves the mouse around the board trying to crush the user’s mice.  To provide variety and encourage diverse placement, each board has obstacles added that obstruct a number of spaces.  It is presumed to be safe to use system-generated randomness to build the board and move the elephant since these are used merely to prompt randomness in the user’s response.  Further, the implmentation uses an extractor to smooth out any patterns in the user’s selections and incorporate the result into a robust PRNG.  The game continues until the user has generated enough entropy.

The study included 482 players who played a total of 24,008 clicks.  The participants did not know the experiment’s objective.  They showed a bias towards corners and edges, and tended to hide multiple mice along the same axis.  Still, it was found that there were generally ~10 bits of min-entropy generated per mouse hidden.  Going forward the researchers would like to explore different types of games, such as those based on the camera or accelerometer, and have to compare the net effort, acceptability, and results to the total quality of non-game inputs.