Local randomness in pseudorandom sequences (Q1180515)

The authors deal with the problem of cryptographic security for a pseudorandom number generator. It is assumed that the enemy can obtain only a limited number of ciphertext bits, and is not limited by computation time. The authors introduce the concept of a perfect local randomizer, i.e. a sequence generator that stretches a binary random sequence of length \(k\) to a pseudorandom sequence of length \(n\) such that every subset of \(e\) or less bits of the generated sequence is a set of independent random bits. The existence of perfect local randomizers is proved, providing \(e\leq k/\log(n)\). Next the concept of a locally randomized generator of degree \(e\) is introduced, i.e. of a generator which has the property that any sequence of \(e\) bits taken from the generator output cannot be practically distinguished from a random sequence. It is proved that if a generator stretches \(k\) bits into \(n\) bits, the degree of the generator cannot be greater than \(k\). It is shown that it can be made arbitrary close to \(k\). The authors discuss some extensions of the concept of local randomization. Some potential practical applications of properties of perfect local randomness are also mentioned.