On Basing Size-Verifiable One-Way Functions on NP-Hardness

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

Mathematics Subject Classification ID

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