Fast Pseudorandom Functions Based on Expander Graphs

No abstract is available for this paper.

• Publication year

  2016

• Venue

  Theory of Cryptography Conference

• Publication date

  2016-10-31

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-662-53641-4_2
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

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

  2018cited by this paper
• Advances in Cryptology

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

  2016cited by this paper
• Goldreich's PRG: Evidence for Near-Optimal Polynomial Stretch

  2014cited by this paper
• Candidate weak pseudorandom functions in AC0 ○ MOD2

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

  2014cited by this paper
• Bootstrapping Obfuscators via Fast Pseudorandom Functions

  2014cited by this paper
• From average case complexity to improper learning complexity

  2013cited by this paper
• Cryptographic Hardness of Random Local Functions

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

  2012cited by this paper
• Functional Encryption with Bounded Collusions via Multi-party Computation

  2012cited by this paper
• Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs

  2012cited by this paper
• From Non-adaptive to Adaptive Pseudorandom Functions

  2012cited by this paper
• A Dichotomy for Local Small-Bias Generators

  2012cited by this paper
• Pseudorandom Functions and Lattices

  2012cited by this paper
• Pseudorandom generators with long stretch and low locality from random local one-way functions

  2012cited by this paper
• Input Locality and Hardness Amplification

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

  2011cited by this paper
• Algebraic pseudorandom functions with improved efficiency from the augmented cascade

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

  2010cited by this paper
• Efficient pseudorandom functions from the decisional linear assumption and weaker variants

  2009cited by this paper
• Notions of Weak Pseudorandomness and GF (2 n )-Polynomials

  2009cited by this paper
• Cryptography with constant computational overhead

  2008cited by this paper
• Cryptographic Hardness for Learning Intersections of Halfspaces

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

  2006cited by this paper
• Constant-Round Multiparty Computation Using a Black-Box Pseudorandom Generator

  2005cited by this paper
• Simple permutations mix well

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

  2004cited by this paper
• Simple permutations mix even better

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

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

  2003cited by this paper
• Pseudo-random functions and factoring (extended abstract)

  2000cited by this paper
• Algorithms for Exponentiation in Finite Fields

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

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

  1997cited by this paper
• An Almost m-wise Independent Random Permutation of the Cube

  1996cited by this paper
• Synthesizers and their application to the parallel construction of pseudo-random functions

  1995cited by this paper
• Natural proofs

  1994cited by this paper
• Cryptographic hardness of distribution-specific learning

  1993cited by this paper
• Cryptographic Primitives Based on Hard Learning Problems

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

  1990cited by this paper
• A hard-core predicate for all one-way functions

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

  1989cited by this paper
• Reductions among prediction problems: on the difficulty of predicting automata

  1988cited by this paper
• The complexity of Boolean functions

  1987cited by this paper
• How to construct random functions

  1986cited by this paper
• The Bit Extraction Problem of t-Resilient Functions (Preliminary Version)

  1985cited by this paper
• The bit extraction problem or t-resilient functions

  1985cited by this paper
• A theory of the learnable

  1984cited by this paper
• An 0(n log n) sorting network

  1983cited by this paper
• O(n LOG n) SORTING NETWORK.

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

  1982cited by this paper
• Theory and Applications of Trapdoor Functions (Extended Abstract)

  1982cited by this paper
• Parallel Prefix Computation

  1980cited by this paper
• Relations Among Complexity Measures

  1979cited by this paper
• Bounds to Complexities of Networks for Sorting and for Switching

  1975cited by this paper

• BitGC Made (More) Efficient

  2025cites this paper
• Strong Pseudorandom Functions in AC0[2] in the Bounded-Query Setting

  2025cites this paper
• A New Approach for LPN-Based Pseudorandom Functions: Low-Depth and Key-Homomorphic

  2025cites this paper
• Fast Pseudorandom Correlation Functions from Sparse LPN

  2025cites this paper
• SoK: On Shallow Weak PRFs A Common Symmetric Building Block for MPC Protocols

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

  2024influential citation
• Structured-Seed Local Pseudorandom Generators and their Applications

  2024cites this paper
• QuietOT: Lightweight Oblivious Transfer with a Public-Key Setup

  2024cites this paper
• Structural Lower Bounds on Black-Box Constructions of Pseudorandom Functions

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

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

  2023cites this paper
• Fast pseudorandom quantum state generators via inflationary quantum gates

  2023cites this paper
• Derandomization with Minimal Memory Footprint

  2023cites this paper
• Extremely efficient constructions of hash functions, with applications to hardness magnification and PRFs

  2022cites this paper
• Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs

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

  2022cites this paper
• From Local Pseudorandom Generators to Hardness of Learning

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

  2021cites this paper
• Low-Complexity Weak Pseudorandom Functions in $\mathtt {AC}0[\mathtt {MOD}2]$

  2021cites this paper
• On the Query Complexity of Constructing PRFs from Non-adaptive PRFs

  2020cites this paper
• Correlated Pseudorandom Functions from Variable-Density LPN

  2020influential citation
• Transforming Pseudorandomness and Non-malleability with Minimal Overheads

  2020cites this paper
• Exploring Crypto Dark Matter: - New Simple PRF Candidates and Their Applications

  2018influential citation
• Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)

  2018cites this paper
• Expander-Based Cryptography Meets Natural Proofs

  2018influential citation
• 18 : 2 Expander-Based Cryptography Meets Natural Proofs

  2018cites this paper
• 5Gen-C: Multi-input Functional Encryption and Program Obfuscation for Arithmetic Circuits

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

  2017influential citation
• On Compressing Non-Additive Correlations

  year unknowncites this paper