On ε‐biased generators in NC0

DOI10.1002/RSA.20112MaRDI QIDQ5486308zbMATH OpenOpenAlexFDO

Authors Elchanan Mossel, Amir Shpilka, Luca Trevisan

Publication date 6 September 2006

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20112

zbMATH Keywords

pseudorandom generator

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Combinatorial probability (60C05)

Recommendations

• scientific article; zbMATH DE number 1834654
• Cryptography in $NC^0$
• Constructions of low-degree and error-correcting -biased generators
• On pseudorandom generators with linear stretch in \(\mathrm{NC}^{0}\)
• A dichotomy for local small-bias generators

Cites work

• scientific article; zbMATH DE number 3651315 (Why is no real title available?)
• scientific article; zbMATH DE number 1304082 (Why is no real title available?)
• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• scientific article; zbMATH DE number 1775444 (Why is no real title available?)
• scientific article; zbMATH DE number 1834654 (Why is no real title available?)
• Cryptographic hardness of distribution-specific learning
• Extractors

Cited in

(28)

• Actively secure garbled circuits with constant communication overhead in the plain model
• On the complexity of random satisfiability problems with planted solutions
• Expander-Based Cryptography Meets Natural Proofs
• Pseudorandom generators for combinatorial checkerboards
• Some limitations of the sum of small-bias distributions
• scientific article; zbMATH DE number 7758323 (Why is no real title available?)
• Expander-based cryptography meets natural proofs
• Public-key encryption, local pseudorandom generators, and the low-degree method
• Towards breaking the exponential barrier for general secret sharing
• Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
• A dichotomy for local small-bias generators
• scientific article; zbMATH DE number 1834654 (Why is no real title available?)
• On the security of Goldreich's one-way function
• Local expanders
• Randomness-Efficient Sampling Within NC 1
• On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions
• Non-interactive zero-knowledge from non-interactive batch arguments
• Improved bounds on the an-complexity of \(O(1)\)-linear functions
• Cryptographic hardness of random local functions. Survey
• Fine-Grained Cryptography
• A dichotomy for local small-bias generators
• Cryptography with constant input locality
• Constructions of low-degree and error-correcting -biased generators
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error
• Fast Correlation Attacks: Methods and Countermeasures
• Randomness extraction in \(\mathsf{AC}^0\) and with small locality
• Matrix rigidity of random Toeplitz matrices

This page was built for publication: On ε‐biased generators in NC⁰

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5486308)