A dichotomy for local small-bias generators

DOI10.1007/978-3-642-28914-9_34zbMATH Open1304.68041OpenAlexW2165364253MaRDI QIDQ2891508FDOQ2891508

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

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

zbMATH Keywords

local functionsdichotomysmall-bias generatorNC\(^0\)

Mathematics Subject Classification ID

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

Cited In (12)

• On the Complexity of Random Satisfiability Problems with Planted Solutions
• Non-interactive zero-knowledge from non-interactive batch arguments
• On ε‐biased generators in NC⁰
• Indistinguishability obfuscation
• Cryptographic hardness of random local functions. Survey
• Indistinguishability obfuscation from simple-to-state hard problems: new assumptions, new techniques, and simplification
• Fast Pseudorandom Functions Based on Expander Graphs
• Algebraic Attacks against Random Local Functions and Their Countermeasures
• Lossy cryptography from code-based assumptions
• On the algebraic immunity -- resiliency trade-off, implications for Goldreich's pseudorandom generator
• Locally computable UOWHF with linear shrinkage
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)

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)