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

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Cryptography (94A60)

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

(23)

• On basing search SIVP on \(\mathbf{NP}\)-hardness
• On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
• 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
• On basing private information retrieval on NP-hardness
• On constructing one-way permutations from indistinguishability obfuscation
• Fine-Grained Cryptography
• Erratum for: ``On basing one-way functions on NP-hardness
• On basing one-way functions on NP-hardness
• ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
• On nonadaptive reductions to the set of random strings and its dense subsets
• Structure versus hardness through the obfuscation lens
• scientific article; zbMATH DE number 7758317 (Why is no real title available?)
• Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
• Capturing one-way functions via NP-hardness of meta-complexity
• On building fine-grained one-way functions from strong average-case hardness
• A meta-complexity characterization of quantum cryptography
• One-way functions and pKt complexity
• On the structure of learnability beyond \textsf{P/poly}
• On basing auxiliary-input cryptography on NP-hardness via nonadaptive black-box reductions
• Towards PNP from extended Frege lower bounds

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)