A dichotomy for local small-bias generators

DOI10.1007/978-3-642-28914-9_34MaRDI QIDQ2891508zbMATH OpenOpenAlexFDO

Authors Benny Applebaum, Andrej Bogdanov, Alon Rosen

Publication date 15 June 2012

Published in Theory of Cryptography (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-28914-9_34

zbMATH Keywords

dichotomylocal functionsNC\(^0\)small-bias generator

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25)

Recommendations

• A dichotomy for local small-bias generators
• Algebraic attacks against random local functions and their countermeasures
• Algebraic attacks against random local functions and their countermeasures
• On ε‐biased generators in NC⁰
• Small bias requires large formulas

Cited in

(18)

• Indistinguishability obfuscation from simple-to-state hard problems: new assumptions, new techniques, and simplification
• Locally computable UOWHF with linear shrinkage
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• A dichotomy for local small-bias generators
• Fast pseudorandom functions based on expander graphs
• Cryptographic hardness of random local functions. Survey
• On the complexity of random satisfiability problems with planted solutions
• Algebraic attacks against random local functions and their countermeasures
• Small bias requires large formulas
• Algebraic attacks against random local functions and their countermeasures
• On ε‐biased generators in NC⁰
• On the algebraic immunity -- resiliency trade-off, implications for Goldreich's pseudorandom generator
• Non-interactive zero-knowledge from non-interactive batch arguments
• Indistinguishability obfuscation
• Lossy cryptography from code-based assumptions
• Indistinguishability obfuscation from well-founded assumptions
• Improved search-to-decision reduction for random local functions
• Attacks on Goldreich's pseudorandom generators by grouping and solving

This page was built for publication: A dichotomy for local small-bias generators

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