On basing size-verifiable one-way functions on NP-hardness
DOI10.1007/978-3-662-46494-6_1zbMATH Open1339.68110OpenAlexW151682908MaRDI QIDQ5261621FDOQ5261621
Authors: 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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (18)
- On building fine-grained one-way functions from strong average-case hardness
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
- On basing one-way functions on NP-hardness
- On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
- On constructing one-way permutations from indistinguishability obfuscation
- On basing search SIVP on \(\mathbf{NP}\)-hardness
- On basing private information retrieval on NP-hardness
- On constructing one-way permutations from indistinguishability obfuscation
- On nonadaptive reductions to the set of random strings and its dense subsets
- Title not available (Why is that?)
- Fine-Grained Cryptography
- 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
- Structure versus hardness through the obfuscation lens
- Capturing one-way functions via NP-hardness of meta-complexity
- Erratum for: ``On basing one-way functions on NP-hardness
This page was built for publication: On basing size-verifiable one-way functions on NP-hardness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5261621)
