Some consequences of the existnce of pseudorandom generators
From MaRDI portal
Publication:1822961
DOI10.1016/0022-0000(89)90021-4zbMath0679.68069OpenAlexW2069035846MaRDI QIDQ1822961
Publication date: 1989
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(89)90021-4
securityprobabilistic algorithmsKolmogorov complexitypseudorandom generatorcomplexity theoryextendersone way functions
Analysis of algorithms and problem complexity (68Q25) Random number generation in numerical analysis (65C10)
Related Items
Large sets in \(\mathrm{AC}^{0}\) have many strings with low Kolmogorov complexity, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity, Almost everywhere high nonuniform complexity, On polynomial-time Turing and many-one completeness in PSPACE, Avoiding simplicity is complex, Symmetry of information and one-way functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Probabilistic encryption
- On the notion of infinite pseudorandom sequences
- One way functions and pseudorandom generators
- Computation times of NP sets of different densities
- Complexity of Presburger arithmetic with fixed quantifier dimension
- Sets with small generalized Kolmogorov complexity
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Bi-immune sets for complexity classes
- Randomness conservation inequalities; information and independence in mathematical theories
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- A Theory of Program Size Formally Identical to Information Theory
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Separating Nondeterministic Time Complexity Classes
- P-Printable Sets
- On the Length of Programs for Computing Finite Binary Sequences
