On hardness of one-way functions
From MaRDI portal
DOI10.1016/0020-0190(88)90071-3zbMATH Open0635.68037OpenAlexW1985764593MaRDI QIDQ1097693FDOQ1097693
Authors: Osamu Watanabe 
Publication date: 1988
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(88)90071-3
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Complexity of proofs (03F20)
Cites Work
- Title not available (Why is that?)
- The polynomial-time hierarchy
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- A note on the complexity of cryptography (Corresp.)
- A low and a high hierarchy within NP
- Relative complexity of checking and evaluating
- Complete sets and the polynomial-time hierarchy
- Title not available (Why is that?)
- Title not available (Why is that?)
- On some natural complete operators
- Every Prime Has a Succinct Certificate
Cited In (22)
- Provably Hard Zero-Way Functions
- Limitations of the upward separation technique
- On continuous one-way functions
- On basing one-way functions on NP-hardness
- One-way permutations and self-witnessing languages
- Title not available (Why is that?)
- On basing size-verifiable one-way functions on NP-hardness
- A second step towards complexity-theoretic analogs of Rice's Theorem
- Tight lower bounds on the ambiguity of strong, total, associative, one-way functions
- On the Cryptographic Complexity of the Worst Functions
- The robustness of LWPP and WPP, with an application to graph reconstruction
- Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions
- Quasi-injective reductions
- Security-preserving hardness-amplification for any regular one-way function
- Fault-tolerance and complexity (extended abstract)
- Poly-Many Hardcore Bits for Any One-Way Function and a Framework for Differing-Inputs Obfuscation
- Title not available (Why is that?)
- Non-interactive secure computation from one-way functions
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets
- Erratum for: ``On basing one-way functions on NP-hardness
- On characterizing the existence of partial one-way permutations
- On polynomial time one-truth-table reducibility to a sparse set
This page was built for publication: On hardness of one-way functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1097693)
