Expander-based cryptography meets natural proofs

DOI10.1007/s00037-022-00220-xOpenAlexW4220862946WikidataQ113906239 ScholiaQ113906239MaRDI QIDQ2125080

Roei Tell, Rahul Santhanam, Igor C. Oliveira

Publication date: 12 April 2022

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

Full work available at URL: https://doi.org/10.1007/s00037-022-00220-x

zbMATH Keywords

circuit complexitypseudorandom generatorsexpandersone-way functions

Mathematics Subject Classification ID

Cryptography (94A60) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The average sensitivity of bounded-depth circuits
• A dichotomy for local small-bias generators
• Cryptographic hardness of random local functions. Survey
• More on average case vs approximation complexity
• On the security of Goldreich's one-way function
• Cryptography in constant parallel time
• On approximate majority and probabilistic time
• Boolean function complexity. Advances and frontiers.
• Pseudorandom bits for constant depth circuits
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Hardness vs randomness
• Input locality and hardness amplification
• Threshold circuits of bounded depth
• Lossless condensers, unbalanced expanders, and extractors
• Extremal properties of polynomial threshold functions
• The Complexity of DNF of Parities
• On the One-Way Function Candidate Proposed by Goldreich
• Public-key cryptography from different assumptions
• On the Complexity of Random Satisfiability Problems with Planted Solutions
• Certifying polynomials for AC^0(parity) circuits, with applications
• Candidate weak pseudorandom functions in AC ⁰ ○ MOD ₂
• Candidate One-Way Functions Based on Expander Graphs
• Constant depth circuits, Fourier transform, and learnability
• Fast Pseudorandom Functions Based on Expander Graphs
• Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
• Randomness conductors and constant-degree lossless expanders
• Algebraic Attacks against Random Local Functions and Their Countermeasures
• On the Correlation of Parity and Small-Depth Circuits
• Learning algorithms from natural proofs
• Extractors and pseudorandom generators
• On ε‐biased generators in NC⁰
• Cryptography in $NC^0$
• Computational Complexity
• Natural proofs

This page was built for publication: Expander-based cryptography meets natural proofs