On hardness of one-way functions

DOI10.1016/0020-0190(88)90071-3zbMath0635.68037OpenAlexW1985764593MaRDI QIDQ1097693

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

zbMATH Keywords

hardness of one-way functionspolynomial lowness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items (12)

One-way permutations and self-witnessing languages ⋮ Tight lower bounds on the ambiguity of strong, total, associative, one-way functions ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ Limitations of the upward separation technique ⋮ On continuous one-way functions ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions ⋮ On polynomial time one-truth-table reducibility to a sparse set ⋮ The robustness of LWPP and WPP, with an application to graph reconstruction ⋮ A second step towards complexity-theoretic analogs of Rice's Theorem ⋮ Quasi-injective reductions ⋮ On characterizing the existence of partial one-way permutations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A low and a high hierarchy within NP
• On some natural complete operators
• Relative complexity of checking and evaluating
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Every Prime Has a Succinct Certificate
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• A note on the complexity of cryptography (Corresp.)

This page was built for publication: On hardness of one-way functions