A dichotomy for local small-bias generators

DOI10.1007/S00145-015-9202-8zbMATH Open1348.94031OpenAlexW2142458674MaRDI QIDQ315550FDOQ315550

Authors: Benny Applebaum, Andrej Bogdanov, Alon Rosen 

Publication date: 21 September 2016

Published in: Journal of Cryptology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00145-015-9202-8

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 functionsdichotomyNC0small-bias generator

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Cryptography (94A60)

Cites Work

• Small-Bias Probability Spaces: Efficient Constructions and Applications
• New Algorithms for Learning in Presence of Errors
• Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Pseudorandomness for network algorithms
• Cryptography with constant input locality
• Input locality and hardness amplification
• Short proofs are narrow -- resolution made simple
• Public-key cryptography from different assumptions
• Pseudorandom bits for polynomials
• Candidate one-way functions based on expander graphs
• Three XOR-lemmas -- an exposition
• Cryptography with constant computational overhead
• Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
• Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
• On the security of Goldreich's one-way function
• Pseudorandom Generators in Propositional Proof Complexity
• Title not available (Why is that?)
• Bounded Independence Fools Halfspaces
• Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions
• On ε‐biased generators in NC⁰
• Pseudorandomness for Read-Once Formulas
• Cryptography in $NC^0$
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• On pseudorandom generators with linear stretch in \(\mathrm{NC}^{0}\)

Cited In (8)

• Expander-Based Cryptography Meets Natural Proofs
• Oblivious transfer with constant computational overhead
• Title not available (Why is that?)
• Public-key encryption, local pseudorandom generators, and the low-degree method
• Expander-based cryptography meets natural proofs
• A dichotomy for local small-bias generators
• Fast public-key silent OT and more from constrained Naor-Reingold
• On the algebraic immunity -- resiliency trade-off, implications for Goldreich's pseudorandom generator

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 Q315550)