Global Sales Contact List

Contact   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

RSA Laboratories

How to Turn Loaded Dice into Fair Coins

A. Juels, M Jakobsson, E. Shriver, and B. Hillyer

Citation: A. Juels, M. Jakobsson, E. Shriver, and B. Hillyer. How to Turn Loaded Dice into Fair Coins. IEEE Transactions on Information Theory 46(3) 911-921, May 2000.

Abstract: We present a new technique for simulating fair coin flips using a biased, stationary source of randomness. Sequences of random numbers are of pervasive importance in cryptography and vital to many other computing applications. Many sources of randomness, such as radioactive or quantum mechanical sources, possess the property of stationarity. In other words, they produce independent outputs over fixed probability distributions. The output of such sources may be viewed as the result of rolling a biased or loaded die. While a biased die may be a good source of entropy, many applications require input in the form of unbiased bits, rather than biased ones. For this reason, almost fifty years ago, von Neumann presented a now well known and extensively investigated technique for using a biased coin to simulate a fair coin. We describe a new generalization of von Neumann's algorithm distinguished by its high level of practicality and amenability to analysis. In contrast to previous efforts, we are able to prove our algorithm optimally efficient, in the sense that it simulates the maximum possible number of fair coin flips for a given number of die rolls. In fact, we are able to prove that in an asymptotic sense our algorithm extracts the full entropy of its input. Moreover, we demonstrate experimentally that our algorithm achieves a high level of computational and output efficiency in a practical setting.

Click here for paper

Full Publication List

Notes:
Connect with EMCConnect with EMC
Need help immediately? EMC Sales Specialists are standing by to answer your questions real time.
Use Live Chat for fast, direct access to EMC Customer Service Professionals to resolve your support questions.
Explore and compare EMC products in the EMC Store, and get a price quote from EMC or an EMC partner.
We're here to help. Send us your sales inquiry and an EMC Sales Specialist will get back to you within one business day.
Want to talk? Call us to speak with an EMC Sales Specialist live.