Home // International Journal On Advances in Networks and Services, volume 4, numbers 1 and 2, 2011 // View article

Unifom Generators and Combinatorial Designs

Authors:
Alexis Bonnecaze
Pierre Liardet

Keywords: Random Generator; Design; k-out-of-n Algorithms; Markov Chain; Random Algorithms;

Abstract:
The concept of randomness is fundamental in many domains and in particular in cryptography. Intuitively, a system, which is unpredictable is more difficult to attack and as a consequence, creating sequences that look like random represents a major issue. In this paper, we first study theoretically how a source of symbols with positive entropy can be turned into a true random generator called Bernoulli. We concentrate on a special type of generators, which consists in randomly choosing k elements out of n elements. After studying some existing algorithms, which are of Las Vegas type, we introduce new constructions from a binary generator taken as a primary random source of symbols. Our method is based on combinatorial block designs and we construct algorithms of Monte Carlo type involving random walks. We analyze in detail properties of our general method. Several explicit constructions of k-out-of-n generators are given. We show that the speed of convergence to the uniform distribution is better than any known method using algorithms with bounded running times.

Pages: 107 to 118

Copyright: Copyright (c) to authors, 2011. Used with permission.

Publication date: September 15, 2011

Published in: journal

ISSN: 1942-2644