Fast Pseudorandom Functions Based on Expander Graphs

DOI10.1007/978-3-662-53641-4_2zbMath1351.94022OpenAlexW2538326345MaRDI QIDQ3179351

Benny Applebaum, Pavel Raykov

Publication date: 21 December 2016

Published in: Theory of Cryptography (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-53641-4_2

Mathematics Subject Classification ID

Cryptography (94A60)

Related Items (5)

Expander-based cryptography meets natural proofs ⋮ Exploring crypto dark matter: new simple PRF candidates and their applications ⋮ Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)] ⋮ Fast Pseudorandom Functions Based on Expander Graphs ⋮ Expander-Based Cryptography Meets Natural Proofs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the security of Goldreich's one-way function
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Algorithms for exponentiation in finite fields
• Input locality and hardness amplification
• From non-adaptive to adaptive pseudorandom functions
• Cryptographic hardness for learning intersections of halfspaces
• Simple permutations mix well
• On the One-Way Function Candidate Proposed by Goldreich
• Public-key cryptography from different assumptions
• A Dichotomy for Local Small-Bias Generators
• Pseudorandom Functions and Lattices
• Functional Encryption with Bounded Collusions via Multi-party Computation
• Bootstrapping Obfuscators via Fast Pseudorandom Functions
• On the Complexity of Random Satisfiability Problems with Planted Solutions
• Candidate weak pseudorandom functions in AC ⁰ ○ MOD ₂
• Candidate One-Way Functions Based on Expander Graphs
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Constant depth circuits, Fourier transform, and learnability
• Fast Pseudorandom Functions Based on Expander Graphs
• Pseudo-random functions and factoring (extended abstract)
• Simple permutations mix even better
• A theory of the learnable
• Parallel Prefix Computation
• Bounds to Complexities of Networks for Sorting and for Switching
• Relations Among Complexity Measures
• A Pseudorandom Generator from any One-way Function
• An Almost m-wise Independent Random Permutation of the Cube
• Cryptographic Hardness of Random Local Functions–Survey
• Cryptographic hardness of distribution-specific learning
• From average case complexity to improper learning complexity
• Algebraic attacks against random local functions and their countermeasures
• Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions
• Constant-Round Multiparty Computation Using a Black-Box Pseudorandom Generator
• Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs
• Natural proofs

This page was built for publication: Fast Pseudorandom Functions Based on Expander Graphs