Games for Extracting Randomness

Two computer scientists have created a video game about mice and elephants that can make computer encryption properly secure—as long as you play it randomly. By Ran Halprin and Moni Naor DOI: 10.1145/1869086.1869101

People have been sending messages in code almost since writing began—and others have been trying to crack those codes. The study of the design and breaking of codes is known as cryptography. With the advent of computers, the scope of cryptography has expanded significantly to now deal with methods for ensuring the secrecy, integrity, and
functionality of computer and communication systems in face of an adversary.

Randomness is essential for addressing the main problems of cryptography (encryption, identification and authentication). When designing a code, one has to select its architecture—the mathematical method behind it. It is commonly assumed in cryptography that your adversary will know or find out the architecture of your code. The assumption is referred to as Kerckhoffs’ principle. The part assumed to be unknown by the adversary, at least initially, is called the key. It should be selected from a large space of possible keys.

THE PROBLEM WITH RANDOMNESS
When designing random algorithms
and cryptographic systems, the avail-
ability of a source of pure randomness
is assumed, but such a perfect source of
randomness is not known to exist. The
most common solution is to find a source
assumed to be somewhat random (often
denoted “entropy source”), or at least
unpredictable from the point of view of
an adversary, and then apply some hash
(mixing) function to it. The randomness
source usually consists of a combination
of information assumed to be unknown
to an adversary (e.g., components manu-
facturer ID) combined with information
assumed to be difficult to predict (e.g.,
exact system time or mouse position or
movement). This process is called ran-
domness extraction.