On linear-size pseudorandom generators and hardcore functions

DOI10.1016/J.TCS.2014.06.013zbMATH Open1384.94032OpenAlexW2043814918MaRDI QIDQ744085FDOQ744085

Authors Joshua Baron, Yuval Ishai, Rafail Ostrovsky 

Publication date 6 October 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.06.013

zbMATH Keywords

cryptographycircuit complexityone-way functionspseudorandom generators

Mathematics Subject Classification ID

Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Pseudo-random numbers; Monte Carlo methods (11K45)

Recommendations

• On linear-size pseudorandom generators and hardcore functions
• Theory of Cryptography
• The complexity of constructing pseudorandom generators from hard functions
• Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions
• The randomized iterate, revisited -- almost linear seed length PRGs from a broader class of one-way functions

Cites work

• scientific article; zbMATH DE number 1676656 (Why is no real title available?)
• A Pseudorandom Generator from any One-way Function
• Advances in Cryptology – CRYPTO 2004
• Characterizing pseudoentropy and simplifying pseudorandom generator constructions
• Cryptography in $NC^0$
• Cryptography with constant computational overhead
• Efficiency improvements in constructing pseudorandom generators from one-way functions
• Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Foundations of Cryptography
• Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• On pseudorandom generators with linear stretch in \(\mathrm{NC}^{0}\)
• On the Existence of Pseudorandom Generators
• On the Power of the Randomized Iterate
• On the Power of the Randomized Iterate
• On the Security of Goldreich’s One-Way Function
• Pseudorandom generators with long stretch and low locality from random local one-way functions
• Theory of Cryptography

Cited in

(16)

• Fast pseudorandom functions based on expander graphs
• How to recover a secret with \(O(n)\) additions
• A new pseudorandom generator from collision-resistant hash functions
• The complexity of constructing pseudorandom generators from hard functions
• scientific article; zbMATH DE number 1689047 (Why is no real title available?)
• On linear-size pseudorandom generators and hardcore functions
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• Ligero: lightweight sublinear arguments without a trusted setup
• Characterizing pseudoentropy and simplifying pseudorandom generator constructions
• Pseudorandom generators with long stretch and low locality from random local one-way functions
• A remark on one-wayness versus pseudorandomness
• Oblivious transfer with constant computational overhead
• scientific article; zbMATH DE number 1722686 (Why is no real title available?)
• Robust pseudorandom generators
• Pseudo-random generators for all hardnesses
• Asymptotically quasi-optimal cryptography

This page was built for publication: On linear-size pseudorandom generators and hardcore functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744085)