How to Generate Cryptographically Strong Sequences of Pseudorandom Bits

DOI10.1137/0213053zbMath0547.68046OpenAlexW2164284862WikidataQ55918694 ScholiaQ55918694MaRDI QIDQ3339289

Publication date: 1984

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0213053

zbMATH Keywords

cryptography randomness unpredictability pseudo-random number generation pseudo-random bit generator random self-reducibility

Mathematics Subject Classification ID

Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Random number generation in numerical analysis (65C10)

Related Items (only showing first 100 items - show all)

A New Pseudorandom Generator from Collision-Resistant Hash Functions ⋮ Plaintext-Checkable Encryption ⋮ An information-theoretic treatment of random-self-reducibility ⋮ Randomness Tests: Theory and Practice ⋮ The self-power map and collecting all residue classes ⋮ All Bits in ax + b mod p are Hard ⋮ Sub-computable Bounded Pseudorandomness ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Sparse pseudorandom distributions ⋮ Pseudorandom sources for BPP ⋮ Reconstructive dispersers and hitting set generators ⋮ Enhancements of trapdoor permutations ⋮ Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs ⋮ Uniform derandomization from pathetic lower bounds ⋮ Balancing Output Length and Query Bound in Hardness Preserving Constructions of Pseudorandom Functions ⋮ On constructing one-way permutations from indistinguishability obfuscation ⋮ Asymptotically efficient lattice-based digital signatures ⋮ The Chain Rule for HILL Pseudoentropy, Revisited ⋮ RSA and Elliptic Curve Least Significant Bit Security ⋮ Secure commitment against a powerful adversary ⋮ The complexity of graph connectivity ⋮ Two Comments on Targeted Canonical Derandomizers ⋮ Pairs of \(r\)-primitive and \(k\)-normal elements in finite fields ⋮ Non-adaptive universal one-way hash functions from arbitrary one-way functions ⋮ PFLM: privacy-preserving federated learning with membership proof ⋮ Beyond the Csiszár-Körner bound: best-possible wiretap coding via obfuscation ⋮ Cliptography: Clipping the Power of Kleptographic Attacks ⋮ Primitive normal values of rational functions over finite fields ⋮ Inverses of \(r\)-primitive \(k\)-normal elements over finite fields ⋮ An ultrafast cryptographically secure pseudorandom number generator ⋮ One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions ⋮ When messages are keys: is HMAC a dual-PRF? ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Universally composable symbolic security analysis ⋮ Unnamed Item ⋮ Simple constructions from (almost) regular one-way functions ⋮ Privacy-preserving and verifiable protocols for scientific computation outsourcing to the cloud ⋮ Revisiting the Security Proof of QUAD Stream Cipher: Some Corrections and Tighter Bounds ⋮ Cryptography and cryptographic protocols ⋮ The index calculus method using non-smooth polynomials ⋮ Secure and efficient off-line digital money (extended abstract) ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ On pseudorandomness in families of sequences derived from the Legendre symbol ⋮ ON GENERIC COMPLEXITY OF THE QUADRATIC RESIDUOSITY PROBLEM ⋮ The reactive simulatability (RSIM) framework for asynchronous systems ⋮ Построение генераторов случайных чисел с помощью вероятностных автоматов и “односторонних” функций ⋮ Gauss periods: orders and cryptographical applications ⋮ Efficient Error-Correcting Codes for Sliding Windows ⋮ NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES ⋮ The Monte Carlo Algorithm with a Pseudorandom Generator ⋮ Practical construction and analysis of pseudo-randomness primitives ⋮ Quantum attacks on pseudorandom generators ⋮ Logics for reasoning about cryptographic constructions ⋮ Unnamed Item ⋮ Natural proofs ⋮ Pseudorandom generators without the XOR lemma ⋮ QUAD: A Practical Stream Cipher with Provable Security ⋮ Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles ⋮ A New Attack on the LEX Stream Cipher ⋮ Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier? ⋮ Unnamed Item ⋮ Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier? ⋮ Asymptotically Efficient Lattice-Based Digital Signatures ⋮ Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions ⋮ Pseudo-random generators for all hardnesses ⋮ On Constructing One-Way Permutations from Indistinguishability Obfuscation ⋮ Contention in Cryptoland: Obfuscation, Leakage and UCE ⋮ Pseudorandom generators from regular one-way functions: new constructions with improved parameters ⋮ Computational sample complexity and attribute-efficient learning ⋮ On the complexity of constructing pseudorandom functions (especially when they don't exist) ⋮ A unified approach to deterministic encryption: new constructions and a connection to computational entropy ⋮ Fine-grained cryptography revisited ⋮ Bit Security of the CDH Problems over Finite Fields ⋮ An Average Case NP-complete Graph Colouring Problem ⋮ An Efficient Encapsulation Scheme from Near Collision Resistant Pseudorandom Generators and Its Application to IBE-to-PKE Transformations ⋮ Practical Chosen Ciphertext Secure Encryption from Factoring ⋮ Minicrypt primitives with algebraic structure and applications ⋮ On Constructing 1-1 One-Way Functions ⋮ In a World of P=BPP ⋮ Three XOR-Lemmas — An Exposition ⋮ Randomness and Computation ⋮ On Security Preserving Reductions – Revised Terminology ⋮ Another Motivation for Reducing the Randomness Complexity of Algorithms ⋮ Generation of solved instances of Multiconstraint Knapsack problem and its applications to Private Key Cipher ⋮ Typically-correct derandomization for small time and space ⋮ Fine-Grained Cryptography ⋮ Multiple encryption with minimum key ⋮ A Hardcore Lemma for Computational Indistinguishability: Security Amplification for Arbitrarily Weak PRGs with Optimal Stretch ⋮ On Related-Secret Pseudorandomness ⋮ Finding Collisions in Interactive Protocols---Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments ⋮ Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace ⋮ Universal test for quantum one-way permutations ⋮ Unnamed Item ⋮ How to Exchange Half a Bit ⋮ Pseudorandom Functions: Three Decades Later ⋮ The Many Entropies in One-Way Functions ⋮ A Note on Perfect Correctness by Derandomization ⋮ Weak Zero-Knowledge beyond the Black-Box Barrier ⋮ Quantum cryptography. II: How to re-use a one-time pad safely even if \(\mathrm P=\mathrm{NP}\)

This page was built for publication: How to Generate Cryptographically Strong Sequences of Pseudorandom Bits