On basing one-way functions on NP-hardness

DOI10.1145/1132516.1132614zbMath1302.68132OpenAlexW2161714146MaRDI QIDQ2931429

Dana Moshkovitz, Shafi Goldwasser, Oded Goldreich, Adi Akavia

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1132516.1132614

zbMATH Keywords

reductionsinteractive proof systemsaverage-case complexityone-way functionsadaptive versus non-adaptive machines

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 (19)

On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \) ⋮ On basing search SIVP on \(\mathbf{NP}\)-hardness ⋮ Towards Non-Black-Box Separations of Public Key Encryption and One Way Function ⋮ Computational barriers to estimation from low-degree polynomials ⋮ Unprovable security of perfect NIZK and non-interactive non-malleable commitments ⋮ 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 ⋮ Dynamic full quantum one-way function based on quantum circuit mapping ⋮ Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Unnamed Item ⋮ 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 ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification ⋮ Fine-Grained Cryptography

This page was built for publication: On basing one-way functions on NP-hardness