Pseudorandom generators with long stretch and low locality from random local one-way functions

No abstract is available for this paper.

• Publication year

  2012

• Venue

  Symposium on the Theory of Computing

• Publication date

  2012-05-19

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/2213977.2214050
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Handbook of Satisfiability

  2021cited by this paper
• Cryptography in Constant Parallel Time

  2013cited by this paper
• On the security of Goldreich’s one-way function

  2012cited by this paper
• Computational complexity and information asymmetry in financial products

  2011cited by this paper
• Candidate One-Way Functions Based on Expander Graphs

  2011cited by this paper
• Input Locality and Hardness Amplification

  2011cited by this paper
• Cryptography by Cellular Automata or How Fast Can Complexity Emerge in Nature?

  2010cited by this paper
• Efficiency improvements in constructing pseudorandom generators from one-way functions

  2010influential reference
• Pseudorandomness against Depth-2 Circuits and Analysis of Goldreich's Candidate One-Way Function

  2010cited by this paper
• Detecting High Log-Densities – an O ( n 1 / 4 ) Approximation for Densest k -Subgraph

  2010cited by this paper
• Lower Bound on Average-Case Complexity of Inversion of Goldreich’s Function by Drunken Backtracking Algorithms

  2010cited by this paper
• Public-key cryptography from different assumptions

  2010influential reference
• Goldreich ’ s One-Way Function Candidate and Drunken Backtracking Algorithms

  2010cited by this paper
• Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms

  2009influential reference
• Random Constraint Satisfaction Problems

  2009cited by this paper
• Handbook of satisfiability

  2009cited by this paper
• Random Planted 3-SAT

  2008cited by this paper
• Cryptography with constant computational overhead

  2008cited by this paper
• Cryptography with Constant Input Locality

  2007cited by this paper
• On ε‐biased generators in NC0

  2006cited by this paper
• On Pseudorandom Generators with Linear Stretch in NC0

  2006cited by this paper
• COMPUTATIONALLY PRIVATE RANDOMIZING POLYNOMIALS AND THEIR APPLICATIONS

  2005cited by this paper
• On constructing parallel pseudorandom generators from one-way functions

  2005cited by this paper
• Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas

  2004cited by this paper
• Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique

  2004cited by this paper
• Cryptography in NC0

  2004cited by this paper
• On /spl epsiv/-biased generators in NC/sup 0/

  2003cited by this paper
• On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators

  2003cited by this paper
• More on Average Case vs Approximation Complexity

  2003influential reference
• Relations between average case complexity and approximation complexity

  2002influential reference
• Foundations of Cryptography: Basic Tools

  2002cited by this paper
• An Improved Pseudorandom Generator Based on Hardness of Factoring

  2002cited by this paper
• On pseudorandom generators in NC 0 ⋆

  2001cited by this paper
• An Experimental Evaluation of Goldreich ' s One-Way FunctionSaurabh

  2001cited by this paper
• The Dense k -Subgraph Problem

  2001cited by this paper
• On the Minimal Hardware Complexity of Pseudorandom Function Generators

  2001cited by this paper
• On Pseudorandom Generators in NC

  2001cited by this paper
• Pseudorandom generators without the XOR lemma

  1999cited by this paper
• A Pseudorandom Generator from any One-way Function

  1999cited by this paper
• The Relationship Between Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms

  1999cited by this paper
• Number-theoretic constructions of efficient pseudo-random functions

  1997cited by this paper
• On Yao's XOR-Lemma

  1995cited by this paper
• Space lower-bounds for pseudorandom-generators

  1994cited by this paper
• Pubic Randomness in Cryptography

  1992cited by this paper
• Public Randomness in Cryptography "

  1992cited by this paper
• Small-bias probability spaces: efficient constructions and applications

  1990cited by this paper
• Constant depth circuits, Fourier transform, and learnability

  1989cited by this paper
• Efficient cryptographic schemes provably as secure as subset sum

  1989cited by this paper
• Hardness vs. randomness

  1988cited by this paper
• The influence of variables on Boolean functions

  1988cited by this paper
• Diffie-Hellman is as Strong as Discrete Log for Certain Primes

  1988cited by this paper
• On the existence of pseudorandom generators

  1988cited by this paper
• One-Way Permutations in NC0

  1987cited by this paper
• One-way functions and pseudorandom generators

  1985cited by this paper
• Theory and application of trapdoor functions

  1982influential reference
• A Omitted Proofs

  year unknowncited by this paper

• SoK: On Shallow Weak PRFs A Common Symmetric Building Block for MPC Protocols

  2025cites this paper
• Indistinguishability Obfuscation from Well-Studied Assumptions

  2025cites this paper
• BitGC Made (More) Efficient

  2025cites this paper
• Improved Search-to-Decision Reduction for Random Local Functions

  2025influential citation
• Lossy Cryptography from Code-Based Assumptions Dense-Sparse LPN: A New Subexponentially Hard LPN Variant in SZK

  2025cites this paper
• Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy 𝑘-LIN over Expanders

  2025cites this paper
• Authenticated BitGC for Actively Secure Rate-One 2PC

  2025cites this paper
• Structured-Seed Local Pseudorandom Generators and their Applications

  2024cites this paper
• Garbled Circuits with 1 Bit per Gate

  2024influential citation
• How to Simulate Random Oracles with Auxiliary Input

  2024cites this paper
• Algorithms for Sparse LPN and LSPN Against Low-noise (extended abstract)

  2024cites this paper
• Batched Distributed Point Function from Sparse LPN and Homomorphic Secret Sharing

  2024cites this paper
• Efficiently Learning Neural Networks: What Assumptions May Suffice?

  2023influential citation
• On the algebraic immunity—resiliency trade-off, implications for Goldreich’s pseudorandom generator

  2023cites this paper
• Covercrypt: an Efficient Early-Abort KEM for Hidden Access Policies with Traceability from the DDH and LWE

  2023cites this paper
• Non-Interactive Zero-Knowledge from Non-Interactive Batch Arguments

  2023cites this paper
• New Baselines for Local Pseudorandom Number Generators by Field Extensions

  2023cites this paper
• Oblivious Transfer with Constant Computational Overhead

  2023cites this paper
• Detection of Dense Subhypergraphs by Low‐Degree Polynomials

  2023cites this paper
• Worst-Case Subexponential Attacks on PRGs of Constant Degree or Constant Locality

  2023cites this paper
• Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy

  2023cites this paper
• Robustness of average-case meta-complexity via pseudorandomness

  2022cites this paper
• Learning Versus Pseudorandom Generators in Constant Parallel Time

  2022cites this paper
• Distribution of Fee between Blockchain Nodes and the Rule of their Motivation

  2022cites this paper
• Classifier Construction Under Budget Constraints

  2022cites this paper
• A characterization of approximability for biased CSPs

  2022cites this paper
• Revisiting the Concrete Security of Goldreich’s Pseudorandom Generator

  2021cites this paper
• Low-Complexity Weak Pseudorandom Functions in AC 0[ MOD 2]

  2021cites this paper
• Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity

  2021cites this paper
• Efficient Online Learning for Dynamic k-Clustering

  2021influential citation
• From Local Pseudorandom Generators to Hardness of Learning

  2021influential citation
• A Parameterized Approximation Scheme for Min $k$-Cut

  2020cites this paper
• The Strongish Planted Clique Hypothesis and Its Consequences

  2020cites this paper
• A time-sensitive network scheduling algorithm based on improved ant colony optimization

  2020cites this paper
• Indistinguishability obfuscation from well-founded assumptions

  2020influential citation
• Indistinguishability Obfuscation from Simple-to-State Hard Problems: New Assumptions, New Techniques, and Simplification

  2020cites this paper
• Pattern Masking for Dictionary Matching: Theory and Practice

  2020cites this paper
• Aggregated Deletion Propagation for Counting Conjunctive Query Answers

  2020cites this paper
• Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG

  2020cites this paper
• Improved Filter Permutators: Combining Symmetric Encryption Design, Boolean Functions, Low Complexity Cryptography, and Homomorphic Encryption, for Private Delegation of Computations

  2019cites this paper
• Sampling Graphs without Forbidden Subgraphs and Almost-Explicit Unbalanced Expanders

  2019influential citation
• Balancing spreads of influence in a social network

  2019cites this paper
• Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error

  2019influential citation
• Simplifying Constructions and Assumptions for iO

  2019cites this paper
• Improved Filter Permutators for Efficient FHE: Better Instances and Implementations

  2019cites this paper
• Pseudorandom Constructions: Computing in Parallel and Applications to Edit Distance Codes

  2019cites this paper
• Secure Multi-Party Computation and Privacy

  2019cites this paper
• XOR Codes and Sparse Learning Parity with Noise

  2019cites this paper
• Personal and Password-Based Cryptography

  2018cites this paper
• On the Concrete Security of Goldreich's Pseudorandom Generator

  2018cites this paper
• . The Densest $k$-Subhypergraph Problem. SIAM Journal on Discrete Mathematics , 32 (2),

  2018influential citation
• University of Birmingham On the Complexity of Random Satisfiability Problems with Planted Solutions

  2018cites this paper
• Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)

  2018cites this paper
• Compressing Vector OLE

  2018cites this paper
• Secure Arithmetic Computation with Constant Computational Overhead

  2017cites this paper
• The Complexity of Public-Key Cryptography Boaz Barak April 27 , 2017

  2017cites this paper
• Refutation of random constraint satisfaction problems using the sum of squares proof system

  2017cites this paper
• Indistinguishability Obfuscation from Trilinear Maps and Block-Wise Local PRGs

  2017influential citation
• Twister Generator of Arbitrary Uniform Sequences

  2017cites this paper
• Hybrid fully homomorphic framework

  2017cites this paper
• Homomorphic Secret Sharing: Optimizations and Applications

  2017cites this paper
• Indistinguishability Obfuscation from SXDH on 5-Linear Maps and Locality-5 PRGs

  2017cites this paper
• Полное факториальное моделирование равномерных последовательностей целых случайных величин

  2017cites this paper
• The Complexity of Public-Key Cryptography

  2017cites this paper
• Exponentially-Hard Gap-CSP and Local PRG via Local Hardcore Functions

  2017cites this paper
• Improved approximation algorithm for the Dense-3-Subhypergraph Problem

  2017cites this paper
• The Densest k-Subhypergraph Problem

  2016cites this paper
• Fast Pseudorandom Functions Based on Expander Graphs

  2016cites this paper
• Randomness Extraction in AC0 and with Small Locality

  2016influential citation
• Improved OT Extension for Transferring Short Secrets and Application to Secure Multi-Party Computation

  2016cites this paper
• Algebraic attacks against random local functions and their countermeasures

  2016influential citation
• On Refutation of Random Constraint Satisfaction Problems Thesis Proposal

  2016cites this paper
• Ubiquitous Authentication : Definitions , Attacks , and Constructions

  2016cites this paper
• Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover

  2016cites this paper
• A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs

  2016cites this paper
• Privacy and the Complexity of Simple Queries

  2016cites this paper
• Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion

  2016cites this paper
• Breaking the Circuit Size Barrier for Secure Computation Under DDH

  2016cites this paper
• The Computational Benefit of Correlated Instances

  2015cites this paper
• VSS and Efficient UC

  2014cites this paper
• Goldreich's PRG: Evidence for Near-Optimal Polynomial Stretch

  2014cites this paper
• Subsampled Power Iteration: a New Algorithm for Block Models and Planted CSP's

  2014cites this paper
• Compact VSS and Efficient Homomorphic UC Commitments

  2014cites this paper
• Improved Region-Growing and Combinatorial Algorithms for k-Route Cut Problems (Extended Abstract)

  2014cites this paper
• On the One-Way Function Candidate Proposed by Goldreich

  2014cites this paper
• Towards Optimally Efficient Secret-Key Authentication from PRG

  2014cites this paper
• Global Stability of Financial Networks: Measures, Evaluations and Policy Implications

  2014cites this paper
• Cryptographic Hardness of Random Local Functions

  2013influential citation
• Privacy and the Complexity of Simple Queries

  2013cites this paper
• Locally Computable UOWHF with Linear Shrinkage

  2013influential citation
• On linear-size pseudorandom generators and hardcore functions

  2013influential citation
• Robust Pseudorandom Generators

  2013cites this paper
• Improved OT Extension for Transferring Short Secrets

  2013cites this paper
• On the Complexity of Random Satisfiability Problems with Planted Solutions

  2013cites this paper
• The Computational Complexity of Randomness

  2013cites this paper
• A Dichotomy for Local Small-Bias Generators

  2012cites this paper
• 2 The Banking Network Model 2 . 1 Rationale Behind the Model

  2012cites this paper
• Answering n{2+o(1)} counting queries with differential privacy is hard

  2012cites this paper
• Efficient Secure Computation and Randomness

  2012influential citation
• Extractors and Lower Bounds for Locally Samplable Sources

  2011influential citation