On basing size-verifiable one-way functions on NP-hardness

DOI10.1007/978-3-662-46494-6_1MaRDI QIDQ5261621zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

Recommendations

• On basing one-way functions on NP-hardness
• Erratum for: ``On basing one-way functions on NP-hardness
• On hardness of one-way functions
• scientific article; zbMATH DE number 3990863
• One-way functions and circuit complexity

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
• scientific article; zbMATH DE number 7758317 (Why is no real title available?)
• 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)