On Basing Size-Verifiable One-Way Functions on NP-Hardness
From MaRDI portal
Publication:5261621
DOI10.1007/978-3-662-46494-6_1zbMath1339.68110OpenAlexW151682908MaRDI QIDQ5261621
Andrej Bogdanov, Christina Brzuska
Publication date: 6 July 2015
Published in: Theory of Cryptography (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-46494-6_1
Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)
Related Items (13)
On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \) ⋮ On basing search SIVP on \(\mathbf{NP}\)-hardness ⋮ On building fine-grained one-way functions from strong average-case hardness ⋮ On the complexity of collision resistant hash functions: new and old black-box separations ⋮ Statistical difference beyond the polarizing regime ⋮ On constructing one-way permutations from indistinguishability obfuscation ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Unnamed Item ⋮ On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets ⋮ Structure Versus Hardness Through the Obfuscation Lens ⋮ On Basing Private Information Retrieval on NP-Hardness ⋮ On Constructing One-Way Permutations from Indistinguishability Obfuscation ⋮ Fine-Grained Cryptography
This page was built for publication: On Basing Size-Verifiable One-Way Functions on NP-Hardness