Games for Extracting Randomness

Ran Halprin         Moni Naor

In this page you can download Pseudo-Random Generator which uses human game play as its only source of entropy. The PRG outputs pseudo-random strings of 128 bits each, represented as 32 hexadecimal digits. To start the system you should play the Mice and Elephant game. Afterwards, you can obtain as many strings as needed.

Download here: (15MB) - Standard ZIP format
or here: MAE-PRG.7z (9MB) - 7zip format (7-zip is a free open source archiver).

After downloading, unzip into a folder and run MAE-START.BAT to launch the system.

Note that this system requires Java Runtime Enviornment version 1.5 or above

The goal of this work is to provide a user the power to create pseudo-random strings for any purpose, including Cryptographic ones (mainly keys for encryption), without relying on their Operating System to provide them with good entropy. This system is a simplified version of the system described in our paper Games for Extracting Randomness (PDF).

The idea is to use observations from Experimental Psychology indicating humans are able to behave in at least somewhat random fashion when engaged in competitive games where such behavior is required. While the human biases in random play are considered large by experimental psychologists, we show that the combinatorial tools known as strong Randomness Extractor are suitable for smoothing out those biases, even in the sensitive cryptographic context.

While any game can potentially be used for extracting randomness, we would prefer games that provoke players to be as random as possible. For instance, a game such as Tetris which rewards very specifics types of moves is less suitable for this purpose. This game used must be very simple so that it would be suitable for any user, yet it has to be somewhat entertaining as to not bore the user. Also, since the systems for which randomness is needed are not always strong desktop computers, the game should also require no extensive resources (i.e. CPU power or graphic adapters).

The Pseudo-Random Generator is based on the Barak-Halevi robust PRG architecture (PDF), where AES is used to implement the Cryptographic Pseudo-Random Generator at the heart of the system. The extractor is based on a pairwise independent hash function. We have the following guarantees on this system:

Combining the outputs generated by this system with other sequences, such as strings generated by the Operating System, can only increase security, and is therefore encouraged.

Empirical tests and theoretical analysis show that users who play the required amount of points in this game generate enough entropy to extract 128 bits that are 2-64-close to random.