Randomness is linear in space
From MaRDI portal
Publication:1915503
DOI10.1006/jcss.1996.0004zbMath0846.68041OpenAlexW2060474153MaRDI QIDQ1915503
Publication date: 16 July 1996
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/838bfb3c88643b333dd64175c120fd41a9e1077d
Related Items
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error ⋮ Short leakage resilient and non-malleable secret sharing schemes ⋮ Leakage-resilient \textsf{IBE}/\textsf{ABE} with optimal leakage rates from lattices ⋮ Speak much, remember little: cryptography in the bounded storage model, revisited ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Nonmalleable digital lockers and robust fuzzy extractors in the plain model ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Extractor Lower Bounds, Revisited ⋮ On the parallel approximability of a subclass of quadratic programming. ⋮ Pseudorandom generators without the XOR lemma ⋮ The communication complexity of pointer chasing ⋮ Four-state non-malleable codes with explicit constant rate ⋮ Coalgebraic tools for randomness-conserving protocols ⋮ Adaptive extractors and their application to leakage resilient secret sharing ⋮ Robustly reusable fuzzy extractor with imperfect randomness ⋮ Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries ⋮ Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources ⋮ Zero-Fixing Extractors for Sub-Logarithmic Entropy ⋮ No time to hash: on super-efficient entropy accumulation ⋮ Extractors for weak random sources and their applications ⋮ Leakage-resilient cryptography from minimal assumptions ⋮ From Indifferentiability to Constructive Cryptography (and Back) ⋮ Reproducible Circularly-Secure Bit Encryption: Applications and Realizations ⋮ Shannon Entropy Versus Renyi Entropy from a Cryptographic Viewpoint ⋮ A generic construction of fuzzy signature ⋮ Adaptive-secure identity-based inner-product functional encryption and its leakage-resilience ⋮ Fooling Polytopes ⋮ Deterministic extractors for affine sources over large fields ⋮ Derandomized constructions of \(k\)-wise (almost) independent permutations ⋮ The entropy of a distributed computation random number generation from memory interleaving ⋮ Pseudorandomness via the Discrete Fourier Transform ⋮ Extracting Computational Entropy and Learning Noisy Linear Functions ⋮ A modular framework for quantum-proof randomness extractors ⋮ Authentication in the bounded storage model ⋮ Our Data, Ourselves: Privacy Via Distributed Noise Generation ⋮ Derandomized parallel repetition theorems for free games ⋮ Instantiability of RSA-OAEP under chosen-plaintext attack ⋮ Simulating BPP using a general weak random source ⋮ Privacy amplification from non-malleable codes ⋮ Unifying Leakage Classes: Simulatable Leakage and Pseudoentropy ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Deterministic Randomness Extraction from Generalized and Distributed Santha--Vazirani Sources ⋮ When Are Fuzzy Extractors Possible? ⋮ Constant time parallel sorting: An empirical view. ⋮ Smooth projective hashing and two-message oblivious transfer ⋮ Unnamed Item ⋮ Reproducible circularly secure bit encryption: applications and realizations ⋮ Expander graphs and their applications ⋮ Simple Optimal Hitting Sets for Small-Success RL ⋮ Unnamed Item ⋮ Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs ⋮ How to get more mileage from randomness extractors ⋮ Quasi chain rule for min-entropy ⋮ Weak derandomization of weak algorithms: explicit versions of Yao's lemma ⋮ Bounded-Retrieval Model with Keys Derived from Private Data ⋮ Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs ⋮ Computational fuzzy extractors ⋮ Secure and Private, yet Lightweight, Authentication for the IoT via PUF and CBKA ⋮ An Improved Robust Fuzzy Extractor ⋮ Increasing the Output Length of Zero-Error Dispersers ⋮ Deterministic extractors for small-space sources ⋮ Randomness buys depth for approximate counting ⋮ Improved Extractors for Recognizable and Algebraic Sources ⋮ Bounded Independence Plus Noise Fools Products ⋮ Preserving Randomness for Adaptive Algorithms ⋮ An Introduction to Randomness Extractors ⋮ Incremental deterministic public-key encryption ⋮ The communication complexity of addition ⋮ Optimal Coin Flipping ⋮ Simpler session-key generation from short random passwords ⋮ On extractors and exposure‐resilient functions for sublogarithmic entropy ⋮ Privacy amplification with asymptotically optimal entropy loss ⋮ Lower bounds for non-black-box zero knowledge ⋮ Extractors from Reed-Muller codes ⋮ Extracting Kolmogorov complexity with applications to dimension zero-one laws ⋮ New approach to practical leakage-resilient public-key cryptography ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Continuous leakage-resilient certificate-based encryption ⋮ A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval ⋮ Explicit list-decodable codes with optimal rate for computationally bounded channels ⋮ On derandomized composition of Boolean functions ⋮ Reusable fuzzy extractors for low-entropy distributions ⋮ Extracting all the randomness and reducing the error in Trevisan's extractors ⋮ Reusable fuzzy extractor from the decisional Diffie-Hellman assumption ⋮ Pseudorandom generators from regular one-way functions: new constructions with improved parameters ⋮ A unified approach to deterministic encryption: new constructions and a connection to computational entropy ⋮ Extractors and Lower Bounds for Locally Samplable Sources ⋮ On the tight security of TLS 1.3: theoretically sound cryptographic parameters for real-world deployments ⋮ Key Agreement from Close Secrets over Unsecured Channels ⋮ Extracting randomness from extractor-dependent sources ⋮ How to extract useful randomness from unreliable sources ⋮ On Constructing 1-1 One-Way Functions ⋮ Bravely, Moderately: A Common Theme in Four Recent Works ⋮ Computational Randomness from Generalized Hardcore Sets ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ Typically-correct derandomization for small time and space ⋮ Better short-seed quantum-proof extractors ⋮ Bit Commitment in the Bounded Storage Model: Tight Bound and Simple Optimal Construction ⋮ Big-Key Symmetric Encryption: Resisting Key Exfiltration ⋮ Explicit two-source extractors and resilient functions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Synthesizers and their application to the parallel construction of pseudo-random functions ⋮ Increasing the output length of zero-error dispersers ⋮ Perfect $L_p$ Sampling in a Data Stream ⋮ On hitting-set generators for polynomials that vanish rarely ⋮ Non-malleability against polynomial tampering ⋮ Quantum Authentication and Encryption with Key Recycling
