Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions

DOI10.1137/120884857zbMath1317.94081OpenAlexW2082618810MaRDI QIDQ5396954

Benny Applebaum

Publication date: 4 February 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/120884857

zbMATH Keywords

cryptographypseudorandomnessconstant-depth circuits\(\text{NC}^0\)densest-subgraph

Mathematics Subject Classification ID

Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Random number generation in numerical analysis (65C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (15)

On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)] ⋮ The Densest $k$-Subhypergraph Problem ⋮ A dichotomy for local small-bias generators ⋮ Fast Pseudorandom Functions Based on Expander Graphs ⋮ Cryptographic hardness of random local functions. Survey ⋮ Locally computable UOWHF with linear shrinkage ⋮ Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error ⋮ Algebraic Attacks against Random Local Functions and Their Countermeasures ⋮ Indistinguishability obfuscation ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the One-Way Function Candidate Proposed by Goldreich ⋮ Unnamed Item

This page was built for publication: Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions