A dichotomy for local small-bias generators

DOI10.1007/978-3-642-28914-9_34MaRDI QIDQ2891508zbMATHOpenAlexFDO

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

local functionsdichotomysmall-bias generatorNC\(^0\)

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

(15)

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

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)