Games for extracting randomness

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: (i) results in experimental psychology indicate that humans are able to behave quite randomly when engaged in competitive games in which a mixed strategy is optimal, and (ii) people have an affection for games, and this leads to longer play yielding more entropy overall. 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.

REFERENCES

• 1: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, ACM Computing Surveys (CSUR), v.28 n.1, p.33-37, March 1996 [doi>10.1145/234313.234327]
• 2: Oded Goldreich , R. L. Graham , B. Korte, Modern Cryptography, Probabilistic Proofs, and Pseudorandomness, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 3: S. Rajasekaran, Handbook of Randomized Computing. Kluwer Academic Publishers, 2001.
• 4: J. Gentle, Random Number Generation and Monte Carlo Methods. Springer, 2003.
• 5: A. Ferrenberg, D. Landau, and Y. Wong, "Monte carlo simulations: Hidden errors from "good" random number generators," Phys. Rev. Lett., vol. 69, pp. 3382--3384, Dec 1992.
• 6: I. Goldberg and D. Wagner, "Randomness and the netscape browser," Dr. Dobb's, pp. 66--70, January 1996.
• 7: Zvi Gutterman , Benny Pinkas , Tzachy Reinman, Analysis of the Linux Random Number Generator, Proceedings of the 2006 IEEE Symposium on Security and Privacy, p.371-385, May 21-24, 2006 [doi>10.1109/SP.2006.5]
• 8: H. Shacham and B. Enright, "The debian openssl bug and its effect on ssl." http://www.usenix.org/events/sec08/wips.html, 2008.
• 9: F. Weimer, "New openssl packages fix predictable random number generator." http://lists.debian.org/debian-security-announce/2008/msg00152.html.
• 10: P. Zimmermann, "Pgp(tm) user's guide." ftp://ftp.pgpi.org/pub/pgp/2.x/doc/pgpdoc1.txt.
• 11: Dawn Xiaodong Song , David Wagner , Xuqing Tian, Timing analysis of keystrokes and timing attacks on SSH, Proceedings of the 10th conference on USENIX Security Symposium, p.25-25, August 13-17, 2001, Washington, D.C.
• 12: Theo de Raadt , Niklas Hallqvist , Artur Grabowski , Angelos D. Keromytis , Niels Provos, Cryptography in OpenBSD: an overview, Proceedings of the annual conference on USENIX Annual Technical Conference, p.33-33, June 06-11, 1999, Monterey, California
• 13: Leo Dorrendorf , Zvi Gutterman , Benny Pinkas, Cryptanalysis of the windows random number generator, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315304]
• 14: M. Haahr, "Random.org - true random number service." http://www.random.org.
• 15: G. Bernstein and M. Lieberman, "Secure random number generation using chaotic circuits," Circuits and Systems, IEEE Transactions on, vol. 37, no. 9, pp. 1157--1164, 1990.
• 16: L. Noll, R. Mende, S. Sisodiya, et al., "Method for seeding a pseudo-random number generator with a cryptographic hash of a digitization of a chaotic system." US Patent 5,732,138, 1998.
• 17: W. Wagenaar, "Generation of random sequences by human subjects: A critical survey of literature," Psychological Bulletin, vol. 77, pp. 65--72, 1972.
• 18: D. Munger, "Is 17 the "most random" number?." scienceblogs.com, specifically http://scienceblogs.com/cognitivedaily/2007/02/index.php?page=3, Feburary 2007.
• 19: R. Falk and C. Konold, "Making sense of randomness: Implicit encoding as a basis for judgment," Psychological Review, vol. 104, pp. 301--318, April 1997.
• 20: B. Burns and B. Corpus, "Randomness and induction from streaks: "gambler's fallacy" versus "hot hand"," Psychonomic Bulletin and Review, vol. 11, pp. 179--184, 2004.
• 21: A. Tversky and T. Gilovich, "The "Hot Hand": Statistical Reality or Cognitive Illusion?," Preference, Belief, and Similarity: Selected Writings, 2004.
• 22: A. Rapoport and D. Budescu, "Randomization in individual choice behavior," Psychological Review, vol. 104, no. 1, pp. 603--617, 1997.
• 23: M. Figurska, M. Stańczyk, and K. Kulesza, "Humans cannot consciously generate random numbers sequences: Polemic study," Medical Hypotheses, vol. 70, no. 1, pp. 182--185, 2008.
• 24: D. Green, "Testing Randomness," Teaching Mathematics and its Applications, vol. 1, no. 3, pp. 95--100, 1982.
• 25: A. Rapoport and D. Budescu, "Generation of random series in two-person strictl competitive games," Journal of Experimental Psychology: General, vol. 121, no. 3, pp. 352--363, 1992.
• 26: K. Eliaz and A. Rubinstein, "Edgar Allen Poe's Riddle: Do Guessers Outperform Misleaders in a Repeated Matching Pennies Game?." http://arielrubinstein.tau.ac.il/papers/poe.pdf, Feb. 2008.
• 27: Luis von Ahn, Games with a Purpose, Computer, v.39 n.6, p.92-94, June 2006 [doi>10.1109/MC.2006.196]
• 28: Boaz Barak , Shai Halevi, A model and architecture for pseudo-random generation with applications to /dev/random, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102148]
• 29: J. von Neumann, "Various techniques used in connection with random digits," Applied Math Series, vol. 12, pp. 36--38, 1951.
• 30: R. Shaltiel, "Recent developments in explicit constructions of extractors," Current Trends in Theoretical Computer Science: The Challenge of the New Century, 2004.
• 31: B. Barak, R. Shaltiel, and E. Tromer, "True random number generators secure in a changing environment." Cryptographic Hardware and Embedded Systems - proc. CHES 2003, LNCS 2779, 166--180, Springer, 2003.
• 32: Peter Bro Miltersen , Troels Bjerre Sørensen, A near-optimal strategy for a heads-up no-limit Texas Hold'em poker tournament, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329357]
• 33: J. Schaeffer, N. Burch, Y. Bjornsson, A. Kishimoto, M. Muller, R. Lake, P. Lu, and S. Sutphen, "Checkers Is Solved," Science, vol. 317, no. 5844, p. 1518, 2007.
• 34: P. Ayton and R. Falk, "Subjective Randomness in Hide-and-Seek Games," Book of Abstracts of the 15th Bi-annual Conference on Subjective Probability, Utility and Decision-Making, p. 37, 1995.
• 35: A. Rubinstein, A. Tversky, and D. Heller, "Naive strategies in competitive games," Understanding Strategic Interaction - Essays in Honor of Reinhard Selten, W. Guth et al. (editors), pp. 394--402, 1996.
• 36: G. Costikyan, "I have no words and i must design." Interactive Fantasy vol. 2 (1994), available at http://www.costik.com/nowords.html.
• 37: Yves Guiard , Michel Beaudouin-Lafon, Preface: Fitts' law 50 years later: Applications and contributions from human-computer interaction, International Journal of Human-Computer Studies, v.61 n.6, p.747-750, December 2004 [doi>10.1016/j.ijhcs/2004.09.003]
• 38: R. corp., "A million random digits with 100,000 normal deviates." http://www.rand.org/pubs/monograph_reports/MR1418/ (Accessed October 2008), 1955.
• 39: G. Marsaglia, "DIEHARD: A Battery of Tests of Randomness," See http://statf.su.edu/~geo/diehard.html, 1996.
• 40: Luis von Ahn , Laura Dabbish, Labeling images with a computer game, Proceedings of the SIGCHI conference on Human factors in computing systems, p.319-326, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985733]
• 41: D. Kirovski, M. Sinclair, and D. Wilson, "The Martini Synch," tech. rep., Technical report MSR-TR-2007-123, Microsoft Research, 2007.
• 42: Rene Mayrhofer , Hans Gellersen, Shake Well Before Use: Intuitive and Secure Pairing of Mobile Devices, IEEE Transactions on Mobile Computing, v.8 n.6, p.792-806, June 2009 [doi>10.1109/TMC.2009.51]
• 43: Shumin Zhai , Jing Kong , Xiangshi Ren, Speed-accuracy tradeoff in Fitts' law tasks: on the equivalency of actual and nominal pointing precision, International Journal of Human-Computer Studies, v.61 n.6, p.823-856, December 2004 [doi>10.1016/j.ijhcs.2004.09.007]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.8 PERSONAL COMPUTING
      K.8.0 General
          Subjects: Games

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Design