Sparse pseudorandom distributions
Authors:
- 1 January 1992
- journal article
- Published by Wiley in Random Structures & Algorithms
- Vol. 3 (2) , 163-174
Abstract
The existence of sparse pseudorandom distributions is proved. These are probability distributions concentrated in a very small set of strings, yet it is infeasible for any polynomial‐time algorithm to distinguish between truly random coins and coins selected according to these distributions. It is shown that such distributions can be generated by (nonpolynomial) probabilistic algorithms, while probabilistic polynomial‐time algorithms cannot even approximate all the pseudorandom distributions. Moreover, we show the existence of evasive pseudorandom distributions which are not only sparse, but also have the property that no polynomial‐time algorithm may find an element in their support, except for a negligible probability. All these results are proved independently of any intractability assumption.Keywords
This publication has 12 references indexed in Scilit:
- A note on computational indistinguishabilityInformation Processing Letters, 1990
- Pseudo-random generators under uniform assumptions1990
- Pseudo-random generation from one-way functions1989
- How to Construct Pseudorandom Permutations from Pseudorandom FunctionsSIAM Journal on Computing, 1988
- Homogeneous measures and polynomial time invariants1988
- On the existence of pseudorandom generators1988
- One way functions and pseudorandom generatorsCombinatorica, 1987
- How to Generate Cryptographically Strong Sequences of Pseudorandom BitsSIAM Journal on Computing, 1984
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952