On pseudorandom generators with linear stretch in \(\mathrm{NC}^{0}\)

DOI10.1007/s00037-007-0237-6zbMath1242.94016OpenAlexW2110761203MaRDI QIDQ937192

Eyal Kushilevitz, Benny Applebaum, Yuval Ishai

Publication date: 20 August 2008

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-007-0237-6

zbMATH Keywords

cryptographypseudorandom generatorsconstant depth circuits\(\mathrm{NC}^{0}\)

Mathematics Subject Classification ID

Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (14)

A dichotomy for local small-bias generators ⋮ Cryptographic hardness of random local functions. Survey ⋮ Asymptotically quasi-optimal cryptography ⋮ Actively secure arithmetic computation and VOLE with constant computational overhead ⋮ Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error ⋮ On the algebraic immunity -- resiliency trade-off, implications for Goldreich's pseudorandom generator ⋮ Algebraic Attacks against Random Local Functions and Their Countermeasures ⋮ Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN ⋮ Unnamed Item ⋮ Computational fuzzy extractors ⋮ Innovative approaches for security of small artefacts ⋮ On the complexity of constructing pseudorandom functions (especially when they don't exist) ⋮ Fine-grained cryptography revisited ⋮ On linear-size pseudorandom generators and hardcore functions

This page was built for publication: On pseudorandom generators with linear stretch in \(\mathrm{NC}^{0}\)