Candidate One-Way Functions Based on Expander Graphs
From MaRDI portal
Publication:3088178
DOI10.1007/978-3-642-22670-0_10zbMath1306.94056OpenAlexW2172366597MaRDI QIDQ3088178
Publication date: 19 August 2011
Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_10
Applications of graph theory (05C90) Cryptography (94A60) Structural characterization of families of graphs (05C75)
Related Items (48)
On the fast algebraic immunity of threshold functions ⋮ Expander-based cryptography meets natural proofs ⋮ Counterexamples to new circular security assumptions underlying iO ⋮ Exploring crypto dark matter: new simple PRF candidates and their applications ⋮ On the Power of Learning from k-Wise Queries ⋮ Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)] ⋮ MPC-friendly symmetric cryptography from alternating moduli: candidates, protocols, and applications ⋮ A dichotomy for local small-bias generators ⋮ Fast Pseudorandom Functions Based on Expander Graphs ⋮ Towards breaking the exponential barrier for general secret sharing ⋮ Cryptographic hardness of random local functions. Survey ⋮ A Survey on some Applications of Graph Theory in Cryptography ⋮ Local expanders ⋮ Asymptotically quasi-optimal cryptography ⋮ Indistinguishability obfuscation from LPN over \(\mathbb{F}_p\), DLIN, and PRGs in \(NC^0\) ⋮ Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization ⋮ Locally computable UOWHF with linear shrinkage ⋮ Improved filter permutators for efficient FHE: better instances and implementations ⋮ Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms ⋮ Non-adaptive universal one-way hash functions from arbitrary one-way functions ⋮ Towards case-optimized hybrid homomorphic encryption. Featuring the \textsf{Elisabeth} stream cipher ⋮ Worst-case subexponential attacks on PRGs of constant degree or constant locality ⋮ Oblivious transfer with constant computational overhead ⋮ Algebraic Attacks against Random Local Functions and Their Countermeasures ⋮ Non-interactive zero-knowledge from non-interactive batch arguments ⋮ Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN ⋮ On the security of Goldreich's one-way function ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Boolean Functions for Homomorphic-Friendly Stream Ciphers ⋮ The Complexity of Inversion of Explicit Goldreich’s Function by DPLL Algorithms ⋮ New Algorithms for Learning in Presence of Errors ⋮ Minimizing locality of one-way functions via semi-private randomized encodings ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ Perfect Structure on the Edge of Chaos ⋮ Unnamed Item ⋮ A Candidate Counterexample to the Easy Cylinders Conjecture ⋮ Non-interactive zero-knowledge in pairing-free groups from weaker assumptions ⋮ Indistinguishability obfuscation from simple-to-state hard problems: new assumptions, new techniques, and simplification ⋮ Expander graphs based on GRH with an application to elliptic curve cryptography ⋮ Expander-Based Cryptography Meets Natural Proofs ⋮ On the One-Way Function Candidate Proposed by Goldreich ⋮ Cryptography with constant input locality ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ On succinct arguments and witness encryption from groups ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Complexity of Public-Key Cryptography
Cites Work
- Unnamed Item
- Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Ramanujan graphs
- Explicit constructions of linear-sized superconcentrators
- Hardness vs randomness
- Public-key cryptography from different assumptions
- Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
- On the Security of Goldreich’s One-Way Function
- Pseudorandom Generators in Propositional Proof Complexity
- Cryptography in $NC^0$
This page was built for publication: Candidate One-Way Functions Based on Expander Graphs
