2026-08-06T13:43:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19578 2024-03-06T11:04:23Z ddc:004 open_access

One-Way Functions vs. TFNP: Simpler and Improved Folwarczný, Lukáš Göös, Mika Hubáček, Pavel Maystre, Gilbert Yuan, Weiqiang TFNP One-Way Functions Oracle Separation Black-Box Simon (1998) proved that it is impossible to construct collision-resistant hash functions from one-way functions using a black-box reduction. It is conjectured more generally that one-way functions do not imply, via a black-box reduction, the hardness of any total NP search problem (collision-resistant hash functions being just one such example). We make progress towards this conjecture by ruling out a large class of "single-query" reductions. In particular, we improve over the prior work of Hubáček et al. (2020) in two ways: our result is established via a novel simpler combinatorial technique and applies to a broader class of semi black-box reductions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lukáš Folwarczný and Mika Göös and Pavel Hubáček and Gilbert Maystre and Weiqiang Yuan 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.50 urn:nbn:de:0030-drops-195788 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.50 eng https://creativecommons.org/licenses/by/4.0/legalcode