# How to recycle random bits

@article{Impagliazzo1989HowTR, title={How to recycle random bits}, author={Russell Impagliazzo and David Zuckerman}, journal={30th Annual Symposium on Foundations of Computer Science}, year={1989}, pages={248-253} }

It is shown that modified versions of the linear congruential generator and the shift register generator are provably good for amplifying the correctness of a probabilistic algorithm. More precisely, if r random bits are needed for a BPP algorithm to be correct with probability at least 2/3, then O(r+k/sup 2/) bits are needed to improve this probability to 1-2/sup -k/. A different pseudorandom generator that is optimal, up to a constant factor, in this regard is also presented. It uses only O(r… Expand

#### Topics from this paper

#### 416 Citations

Impossibility results for recycling random bits in two-prover proof systems

- Mathematics, Computer Science
- STOC '95
- 1995

The great success enjoyed by general techniques for recycling random bits in other contexts meets its limits when MIP(2, 1) proof systems are concerned, and parallel repetition using pseudo- random bits cannot reduce the error below a constant, regardless of the nature of the pseudo-random source. Expand

Deterministic extractors for bit-fixing sources and exposure-resilient cryptography

- Mathematics, Computer Science
- 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.
- 2003

An efficient deterministic algorithm which extracts almost-random bits from sources where n/sup 1/2 + /spl gamma// of the n bits are uniformly random and the rest are fixed in advance is given. Expand

How to Privatize Random Bits

- Mathematics
- 1996

This paper investigates the extent to which a public source of random bits can be used to obtain private random bits that can be safely used in cryptographic protocols. We consider two cases: (a) the… Expand

Randomness-optimal oblivious sampling

- Computer Science
- Random Struct. Algorithms
- 1997

This work presents the first efficient oblivious sampler that uses an optimal number of random bits, up to an arbitrary constant factor bigger than 1, and gives applications to constructive leader election and reducing randomness in interactive proofs. Expand

Randomness-optimal sampling, extractors, and constructive leader election

- Computer Science
- STOC '96
- 1996

A constructive O(log n) round protocol for leader election in the full information model that is resilient against any coalition of size /3n for any constant ~ < 1/2 and gives two applications of these tools. Expand

On the Power of the Randomized Iterate

- Computer Science, Mathematics
- CRYPTO
- 2005

This paper revisits a technique that was used in to give a construction of pseudorandom generators from regular one-way functions and uses the randomized iterate to replace the basic building block of the [HILL99] construction. Expand

Recycling random bits in parallel

- Computer Science
- Proceedings of the Twenty-Eighth Annual Hawaii International Conference on System Sciences
- 1995

Shows that r pseudo-random bits can be obtained by concatenating t blocks of r/t pseudo-random bits, where the blocks are generated in parallel. This can be considered as a parallel version of R.… Expand

Deterministic amplification of space-bounded probabilistic algorithms

- Computer Science, Mathematics
- Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat.No.99CB36317)
- 1999

It is proved that any black-box amplification method that uses O(r) random bits and makes at most p parallel simulations reduces the error to at most /spl epsiv//sup O(p)/. Expand

Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography

- Mathematics, Computer Science
- SIAM J. Comput.
- 2007

An efficient deterministic algorithm is given that extracts almost-random bits from sources where n of the bits are uniformly random and the rest are fixed in advance, improving upon previous constructions. Expand

A pseudorandom generator construction based on randomness extractors and combinatorial designs

- Mathematics
- 2006

Nisan and Wigderson in their seminal work introduced a new (conditional) pseudorandom generator construction which since then has been extensively used in con~plexity theory and has led to extensive… Expand

#### References

SHOWING 1-10 OF 40 REFERENCES

How to generate cryptographically strong sequences of pseudo random bits

- Mathematics, Computer Science
- 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982)
- 1982

A general algorithmic scheme for constructing polynomial-time deterministic algorithms that stretch a short secret random input into a long sequence of unpredictable pseudo-random bits is presented. Expand

Realistic analysis of some randomized algorithms

- Computer Science, Mathematics
- STOC
- 1987

The results below apply to sequences generated by iteratively applying functions of the form ƒ = &agr;&khgr; + &bgr; (mod p) to a randomly chosen seed x, and estimate the probability that a predetermined number of trials of an algorithm will fail. Expand

Deterministic simulation in LOGSPACE

- Computer Science, Mathematics
- STOC
- 1987

In this paper we show that a wide class of probabilistic algorithms can be simulated by deterministic algorithms. Namely if there is a test in LOGSPACE so that a random sequence of length (log n)2 /… Expand

Pseudo-random generation from one-way functions

- Mathematics, Computer Science
- STOC '89
- 1989

From one-way functions of type (1) or (2) it is shown how to construct pseudo-random generators secure against small circuits or fast algorithms, respectively, and vice-versa. Expand

On Using Deterministic Functions to Reduce Randomness in Probabilistic Algorithms

- Mathematics, Computer Science
- Inf. Comput.
- 1987

Abstract We show the existence of nonuniform schemes for the following sampling problem: Given a sample space with n points, an unknown set of size n 2 , and s random points, it is possible to… Expand

Randomized algorithms and pseudorandom numbers

- Mathematics, Computer Science
- STOC '88
- 1988

This work assumes that a (small) random seed is available to start up a simple pseudorandom number generator which is then used for the randomized algorithm. Expand

Linear Congruential Generators Do Not Produce Random Sequences

- Computer Science, Mathematics
- FOCS
- 1984

This paper discusses the predictability of the sequence given only a constant proportion /spl alpha/ of the leading bits of the first few numbers generated, and shows that the rest of the sequences is predictable in polynomial time, almost always. Expand

Universal Classes of Hash Functions

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 1979

An input independent average linear time algorithm for storage and retrieval on keys that makes a random choice of hash function from a suitable class of hash functions. Expand

Dispersers, deterministic amplification, and weak random sources

- Computer Science, Mathematics
- 30th Annual Symposium on Foundations of Computer Science
- 1989

The use of highly expanding bipartite multigraphs (called dispersers) to reduce greatly the error of probabilistic algorithms at the cost of few additional random bits is treated. Explicit… Expand

Efficiency considerations in using semi-random sources

- Computer Science
- STOC
- 1987

Randomness is an important computational resource, and has found application in such diverse computational tasks as combinatorial algorithms, synchronization and deadlock resolution protocols,… Expand