How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
From MaRDI portal
Publication:3339289
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
cryptographyrandomnessunpredictabilitypseudo-random number generationpseudo-random bit generatorrandom self-reducibility
Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Random number generation in numerical analysis (65C10)
Related Items
Quantum cryptography. II: How to re-use a one-time pad safely even if \(\mathrm P=\mathrm{NP}\), The power of adaptiveness and additional queries in random-self- reductions, Hardness vs randomness, Practical isogeny-based key-exchange with optimal tightness, Generating quasi-random sequences from semi-random sources, Linear complexity of the \(x^{2} \bmod p\) orbits, One-message zero knowledge and non-malleable commitments, Reductions among number theoretic problems, A brief and understandable guide to pseudo-random number generators and specific models for security, On the notion of infinite pseudorandom sequences, MPC-friendly symmetric cryptography from alternating moduli: candidates, protocols, and applications, On using deterministic functions to reduce randomness in probabilistic algorithms, On solving hard problems by polynomial-size circuits, One-way functions and circuit complexity, Garbling XOR gates ``for free in the standard model, More efficient DDH pseudorandom generators, Fast generation of prime numbers and secure public-key cryptographic parameters., A note on perfect correctness by derandomization, Generic complexity of Presburger arithmetic, One way functions and pseudorandom generators, On the hardness of computing the permanent of random matrices, A counterexample to the chain rule for conditional HILL entropy, Unprovable security of perfect NIZK and non-interactive non-malleable commitments, Expanders, randomness, or time versus space, Zeta functions, one-way functions, and pseudorandom number generators., One-way permutations in NC 0, Paillier's trapdoor function hides \(\Theta(n)\) bits, Performance improvement for the GGM-construction of pseudorandom functions, Mathematical problems in cryptology, A survey on delegated computation, An unpredictability approach to finite-state randomness, Pseudorandom bit sequence generator for stream cipher based on elliptic curves, On the power of two-point based sampling, A study of password security, Optimal bounds for the approximation of Boolean functions and some applications, Wavelet-based image watermarking with visibility range estimation based on HVS and neural networks, Improving classical authentication over a quantum channel, Pseudorandom generators against advised context-free languages, One-way functions using algorithmic and classical information theories, Practical chosen ciphertext secure encryption from factoring, Computational indistinguishability between quantum states and its cryptographic application, Cryptanalysis of the stream cipher LEX, A note on computational indistinguishability, A discrete logarithm implementation of perfect zero-knowledge blobs, Polynomial interpolation and identity testing from high powers over finite fields, Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds, Weak derandomization of weak algorithms: explicit versions of Yao's lemma, Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs, Immunity and pseudorandomness of context-free languages, A random number generator based on elliptic curve operations, Random languages for nonuniform complexity classes, Local randomness in pseudorandom sequences, An introduction to randomized algorithms, Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification, Almost everywhere high nonuniform complexity, When can limited randomness be used in repeated games?, Small-bias is not enough to hit read-once CNF, Bounds on tradeoffs between randomness and communication complexity, Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs, Pseudorandom generators for space-bounded computation, Algorithmic rationality: game theory with costly computation, The complexity of explicit constructions, Secure remote state estimation against linear man-in-the-middle attacks using watermarking, A uniform-complexity treatment of encryption and zero-knowledge, Fourier concentration from shrinkage, Simple extractors via constructions of cryptographic pseudo-random generators, Bounds on the efficiency of black-box commitment schemes, Realistic analysis of some randomized algorithms, One-way permutations on elliptic curves, Traceable ring signatures: general framework and post-quantum security, QUAD: A multivariate stream cipher with provable security, On linear-size pseudorandom generators and hardcore functions, A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm, Single-to-multi-theorem transformations for non-interactive statistical zero-knowledge, Reducing complexity assumptions for statistically-hiding commitment, Some consequences of the existnce of pseudorandom generators, Resource bounded randomness and computational complexity, Cryptography with constant input locality, Synthesizers and their application to the parallel construction of pseudo-random functions, Protecting data privacy in private information retrieval schemes, Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly, Improved algorithms via approximations of probability distributions, Probabilistic encryption, Universal tests for nonuniform distributions, A short proof for explicit formulas for discrete logarithms in finite fields, On the existence of pairs of primitive normal elements over finite fields, Constant-round perfect zero-knowledge computationally convincing protocols, Bit commitment using pseudorandomness, The discrete logarithm modulo a composite hides \(O(n)\) bits, Pseudorandom bits for constant depth circuits, Self-testing/correcting with applications to numerical problems, Randomness vs time: Derandomization under a uniform assumption, Efficient, perfect polynomial random number generators, Mining circuit lower bound proofs for meta-algorithms, Unifying known lower bounds via geometric complexity theory, A comparison of two approaches to pseudorandomness, \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs, Randomness in interactive proofs, Provably good pattern generators for a random pattern test, The vulnerability of geometric sequences based on fields of odd characteristic, Paradigms for Unconditional Pseudorandom Generators, Beyond the Csiszár-Korner bound: best-possible wiretap coding via obfuscation, To label, or not to label (in generic groups), The price of verifiability: lower bounds for verifiable random functions, Bet-or-pass: adversarially robust Bloom filters, r -primitive k -normal elements in arithmetic progressions over finite fields, 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
