On hardness of one-way functions

DOI10.1016/0020-0190(88)90071-3MaRDI QIDQ1097693zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

hardness of one-way functionspolynomial lowness

Mathematics Subject Classification ID

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

Recommendations

• Publication:4205082
• A survey of one-way functions in complexity theory
• One-way functions and circuit complexity
• Absolute results concerning one-way functions and their applications
• On basing one-way functions on NP-hardness

Cites work

• scientific article; zbMATH DE number 4007728 (Why is no real title available?)
• scientific article; zbMATH DE number 3596249 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A low and a high hierarchy within NP
• A note on the complexity of cryptography (Corresp.)
• Complete sets and the polynomial-time hierarchy
• Every Prime Has a Succinct Certificate
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On some natural complete operators
• Relative complexity of checking and evaluating
• The polynomial-time hierarchy

Cited in

(22)

• On characterizing the existence of partial one-way permutations
• On polynomial time one-truth-table reducibility to a sparse set
• Provably Hard Zero-Way Functions
• On continuous one-way functions
• Limitations of the upward separation technique
• On basing one-way functions on NP-hardness
• One-way permutations and self-witnessing languages
• scientific article; zbMATH DE number 709841 (Why is no real title available?)
• On basing size-verifiable one-way functions on NP-hardness
• Tight lower bounds on the ambiguity of strong, total, associative, one-way functions
• A second step towards complexity-theoretic analogs of Rice's Theorem
• 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
• scientific article; zbMATH DE number 4125016 (Why is no real title available?)
• 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

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)