Pseudorandom generators without the XOR lemma
From MaRDI portal
The paper deals with pseudorandom generators based on complexity considerations (good generators are characterized via some abstract computation or circuit complexity properties called hardness) rather than on the probabilistic investigations. It contains mainly the results of the authors presented on several conferences and requires knowledge of many papers mentioned in the introduction.NEWLINENEWLINENEWLINEAfter a quite long discussion of known results the authors show that the pseudorandom generators using the XOR lemma allowing hardness amplification [cf. \textit{N. Nissan} and \textit{A. Widgerson}, J.Comput. Syst. Sci. 49, No.~2, 149-167 (1994; Zbl 0821.68057)] can be modified via the application of pseudoentropy generators introduced by the authors. The authors are able to find a new type of pseudorandom generators based on the concept of hardness and to find new results and new proofs of known ones (e.g. the connection between the hardness amplification and a list decoding algorithm for error correcting codes and the derivation of a list correcting algorithm for error correcting codes based on multivariate polynomials). NEWLINENEWLINENEWLINEThe paper is very technical and is based on the results of more than fifty papers. It contains no computer programs of the discussed algorithms and no statistical tests of the proposed generators. It is not too clear whether the generators presented in the paper are easily implementable and/or usable.
Recommendations
- An efficient pseudo-random generator provably as secure as syndrome decoding
- scientific article; zbMATH DE number 17389
- The unified theory of pseudorandomness
- scientific article; zbMATH DE number 1670863
- scientific article; zbMATH DE number 176069
- A primer on pseudorandom generators
- Pseudorandomness
- Constant-error pseudorandomness proofs from hardness require majority
- Pseudorandom sequences
Cites work
- BPP has subexponential time simulations unless EXPTIME has publishable proofs
- A Pseudorandom Generator from any One-way Function
- A theory of the learnable
- Advances in cryptology -- CRYPTO '85. Proceedings. (A Conference on the Theory and Application of Cryptographic techniques held at the University of California, Santa Barbara, August 18--22, 1985)
- Computing with Very Weak Random Sources
- Construction of extractors using pseudo-random generators (extended abstract)
- Decoding of Reed Solomon codes beyond the error-correction bound
- Extracting randomness: A survey and new constructions
- Extractors and pseudo-random generators with optimal seed length
- Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
- Hardness vs randomness
- Highly resilient correctors for polynomials
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- scientific article; zbMATH DE number 4191094 (Why is no real title available?)
- scientific article; zbMATH DE number 4213418 (Why is no real title available?)
- scientific article; zbMATH DE number 3960854 (Why is no real title available?)
- scientific article; zbMATH DE number 4012495 (Why is no real title available?)
- scientific article; zbMATH DE number 107482 (Why is no real title available?)
- scientific article; zbMATH DE number 1256667 (Why is no real title available?)
- scientific article; zbMATH DE number 1304313 (Why is no real title available?)
- scientific article; zbMATH DE number 1306886 (Why is no real title available?)
- scientific article; zbMATH DE number 1104167 (Why is no real title available?)
- scientific article; zbMATH DE number 1097580 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- scientific article; zbMATH DE number 1559564 (Why is no real title available?)
- Improved decoding of Reed-Solomon and algebraic-geometry codes
- Modern cryptography, probabilistic proofs and pseudo-randomness
- Natural proofs
- On the hardness of computing the permanent of random matrices
- On the power of two-point based sampling
- Probabilistic encryption
- Pseudorandom generators without the XOR lemma (extended abstract)
- Random-Self-Reducibility of Complete Sets
- Randomness is linear in space
- Randomness vs time: Derandomization under a uniform assumption
- Reconstructing Algebraic Functions from Mixed Data
- Simulating BPP using a general weak random source
- Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
Cited in
(70)- Isolation, matching, and counting uniform and nonuniform upper bounds
- On building fine-grained one-way functions from strong average-case hardness
- Local algorithms for sparse spanning graphs
- Mining circuit lower bound proofs for meta-algorithms
- Reconstructive dispersers and hitting set generators
- Can we locally compute sparse connected subgraphs?
- List-decoding Barnes-Wall lattices
- On derandomizing Yao's weak-to-strong OWF construction
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
- Computational Randomness from Generalized Hardcore Sets
- General pseudo-random generators from weaker models of computation
- Pseudorandom generators for combinatorial checkerboards
- The inverse conjecture for the Gowers norm over finite fields in low characteristic
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma
- Complexity of hard-core set proofs
- Symmetric LDPC codes and local testing
- Local property reconstruction and monotonicity
- Foundations of homomorphic secret sharing
- On some computations on sparse polynomials
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- Quantified Derandomization: How to Find Water in the Ocean
- Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
- Erasures vs. errors in local decoding and property testing
- Typically-correct derandomization for small time and space
- scientific article; zbMATH DE number 7561748 (Why is no real title available?)
- Worst-Case to Average-Case Reductions for Subclasses of P
- Local list recovery of high-rate tensor codes and applications
- Amplification and Derandomization without Slowdown
- Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
- Symmetric LDPC codes and local testing
- A combination of testability and decodability by tensor products
- Direct sum testing
- scientific article; zbMATH DE number 7650107 (Why is no real title available?)
- scientific article; zbMATH DE number 7650135 (Why is no real title available?)
- Hardness amplification within NP
- Pseudo-random generators for all hardnesses
- On locally decodable codes, self-correctable codes, and \(t\)-private PIR
- Erasures versus errors in local decoding and property testing
- scientific article; zbMATH DE number 7758312 (Why is no real title available?)
- scientific article; zbMATH DE number 7758317 (Why is no real title available?)
- Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes
- Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?
- Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings
- Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
- Paradigms for Unconditional Pseudorandom Generators
- Singleton-type bounds for list-decoding and list-recovery, and related results
- Hardness amplification within NP against deterministic algorithms
- Indistinguishability obfuscation, range avoidance, and bounded arithmetic
- Nearly optimal pseudorandomness from hardness
- A direct PRF construction from Kolmogorov complexity
- Hardness along the boundary: towards one-way functions from the worst-case hardness of time-bounded Kolmogorov complexity
- Reconstruction of depth-4 multilinear circuits
- Nondeterministic quasi-polynomial time is average-case hard for \textsf{ACC} circuits
- Collapsing and separating completeness notions under average-case and worst-case hypotheses
- On solving sparse polynomial factorization related problems
- Leakage resilience, targeted pseudorandom generators, and mild derandomization of Arthur-Merlin protocols
- One-way functions and pKt complexity
- On exponential-time hypotheses, derandomization, and circuit lower bounds
- Two combinatorial MA-complete problems
- Leakage-resilient hardness equivalence to logspace derandomization
- Majority vs. approximate linear sum and average-case complexity below NC^1
- Locally computing edge orientations
- Polynomial-time pseudodeterministic construction of primes
- Eigenvalue bounds for symmetric Markov chains on multislices with applications
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
- Improved hardness amplification in NP
This page was built for publication: Pseudorandom generators without the XOR lemma
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5943089)
