Games for Extracting Randomness

 Ran Halprin      Moni Naor

Abstract:

Randomness is a necessary ingredient in various computational tasks and especially in Cryptography, yet many existing mechanisms for obtaining randomness suffer from numerous problems. We suggest utilizing the behavior of humans while playing competitive games as an entropy source, in order to enhance the quality of the randomness in the system. This idea has two motivations:

While the resulting strings are not perfectly random, we show how to integrate such a game into a robust pseudo-random generator that enjoys backward and forward security.

We construct a game suitable for randomness extraction, and test users playing patterns. The results show that in less than two minutes a human can generate 128 bits that are $2^{-64}$-close to random, even on a limited computer such as a PDA that might have no other entropy source.

As proof of concept, we supply a complete working software for a robust PRG. It generates random sequences based solely on human game play, and thus does not depend on the Operating System or any external factor.

Paper: PDF. Slides: ppt.  Demo of the game:

(Somewhat) Related On-Line Papers:

Back to: On-Line Publications,  Recent Papers

Back Home